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

Abstract

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.

arXiv comment20 pages, 5 figures, 5 tables. Introduction revision and typos correction

References in corpus (7)

• Curse of dimensionality reduction in max-plus based approximation methods: theoretical estimates and improved pruning algorithms
• Tropical Geometry of Deep Neural Networks
• A Tropical Approach to Neural Networks with Piecewise Linear Activations
• Multivariate convex regression with adaptive partitioning
• Tropical Polynomial Division and Neural Networks
• Max-Plus Matching Pursuit for Deterministic Markov Decision Processes
• Max-plus Linear Inverse Problems: 2-norm regression and system identification of max-plus linear dynamical systems with Gaussian noise