Representing Piecewise Linear Functions by Functions with Small Arity
This addresses a theoretical problem in mathematical optimization and machine learning for researchers, providing foundational insights into function representations, though it is incremental as it builds on prior conjectures.
The paper tackles the representation of piecewise linear functions by showing that every such function can be expressed as a linear combination of max-functions with at most n+1 arguments, and provides an algorithm for this computation, while also proving that the function max(0, x1, ..., xn) requires at least n+1 arguments, confirming a 2005 conjecture.
A piecewise linear function can be described in different forms: as an arbitrarily nested expression of $\min$- and $\max$-functions, as a difference of two convex piecewise linear functions, or as a linear combination of maxima of affine-linear functions. In this paper, we provide two main results: first, we show that for every piecewise linear function there exists a linear combination of $\max$-functions with at most $n+1$ arguments, and give an algorithm for its computation. Moreover, these arguments are contained in the finite set of affine-linear functions that coincide with the given function in some open set. Second, we prove that the piecewise linear function $\max(0, x_{1}, \ldots, x_{n})$ cannot be represented as a linear combination of maxima of less than $n+1$ affine-linear arguments. This was conjectured by Wang and Sun in 2005 in a paper on representations of piecewise linear functions as linear combination of maxima.