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

2020/11/06 by Nikos Tsilivis, Tsilivis, Nikos, Anastasios Tsiamis +3
Computer Science · Engineering · Mathematics · #Control Systems and Identification #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Rings and Algebras (math.RA) #Sparse and Compressive Sensing Techniques #cs.LG #math.OC #math.RA #stat.ML

paper · pdf · doi:10.48550/arxiv.2011.04468

20 pages, 5 figures, 5 tables. Introduction revision and typos correction

openalex publication_date 2020/11/06 · openalex created_date 2020/11/23 · arxiv created 2020/12/21 · arxiv updated 2020/12/22 · openalex updated_date 2026/07/28

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 ℓ_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.

Citations

• Sparse Approximate Solutions to Linear Systems
• Stable signal recovery from incomplete and inaccurate measurements
• A Tropical Approach to Neural Networks with Piecewise Linear Activations
• Max-Plus Matching Pursuit for Deterministic Markov Decision Processes
• Max-plus Linear Inverse Problems: 2-norm regression and system\n identification of max-plus linear dynamical systems with Gaussian noise

Related

• Sparse Max-Affine Regression
• An Efficient Minimax Optimal Estimator For Multivariate Convex Regression
• Sparse PCA: Convex Relaxations, Algorithms and Applications
• Max-Linear Regression by Convex Programming
• Optimal Solutions for Sparse Principal Component Analysis