Representing Piecewise Linear Functions by Functions with Small Arity
Christoph Koutschan Bernhard Moser Anton Ponomarchuk Josef Schicho
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.