Representing piecewise linear functions by functions with small arity

A piecewise linear function can be described in different forms: as a 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 f : R-n -> R, 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),., 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 (IEEE Trans Inf Theory 51:4425-4431, 2005) in a paper on representations of piecewise linear functions as linear combination of maxima.