Sparse Approximate Solutions to Max-Plus Equations with Application to Multivariate Convex Regression

R { } is equipped with the standard maximum and sum operations, respectively. It has been used to represent various nonlinear processes, in areas such as scheduling and synchronization [2], [6], [9], geometry [22], control theory and optimization [1], [4], morphological image and signal analysis [15], [24], [28], and machine learning [7], [8], [29], [32], [33]. Max-plus algebra is obtained from the conventional linear algebra if we replace addition with maximum and multiplication with addition, as an extension of the max-plus semiring to multiple dimensions. Hence, many of the aforementioned nonlinear processes enjoy some linear-like properties when described in terms of the max-plus algebra. In this paper we are interested in sparse max-plus representations, i.e. vectors which consist of as many uninformative () elements as possible.