Sparsity in Max-Plus Algebra and Applications in Multivariate Convex Regression

Nikos Tsilivis; Anastasios Tsiamis; Petros Maragos

ICASSP 2021accepted0 citations

Sparsity in Max-Plus Algebra and Applications in Multivariate Convex Regression

Nikos Tsilivis, Anastasios Tsiamis, Petros Maragos

Abstract

In this paper, we study concepts of sparsity in the max-plus algebra and apply them to the problem of multivariate convex regression. We show how to efficiently find sparse (containing many −∞ elements) approximate solutions to max-plus equations by leveraging notions from submodular optimization. Subsequently, we propose a novel method for piecewise-linear surface fitting of convex multivariate functions, with optimality guarantees for the model parameters and an approximately minimum number of affine regions.

BibTeX

@inproceedings{icassp2021_sparsityinmaxplu,
  title = {Sparsity in Max-Plus Algebra and Applications in Multivariate Convex Regression},
  author = {Nikos Tsilivis and Anastasios Tsiamis and Petros Maragos},
  booktitle = {ICASSP 2021},
  year = {2021}
}