Sparse Approximate Solutions to Max-Plus Equations with Application to Multivariate Convex Regression
This addresses the problem of efficient and sparse approximation in max-plus algebra for researchers in optimization and convex analysis, with incremental improvements in computational methods.
The paper tackles the problem of finding sparse approximate solutions to matrix max-plus equations efficiently in polynomial time for any ℓ_p error, and applies this to propose a novel method for piecewise-linear fitting of convex multivariate functions with optimality guarantees and an approximately minimum number of affine regions.
In this work, we study the problem of finding approximate, with minimum support set, solutions to matrix max-plus equations, which we call sparse approximate solutions. We show how one can obtain such solutions efficiently and in polynomial time for any $\ell_p$ approximation error. Based on these results, we propose a novel method for piecewise-linear fitting of convex multivariate functions, with optimality guarantees for the model parameters and an approximately minimum number of affine regions.