Linear regression over the max-plus semiring: algorithms and applications
For researchers working with max-plus algebra or inverse problems in networks and dynamical systems, this work provides a novel regression framework with concrete algorithmic solutions.
This paper develops theory and algorithms for max-plus semiring regression, demonstrating its use for maximum likelihood estimation in three inverse problems: inferring max-plus linear dynamical systems from noisy time series, estimating network edge lengths from shortest path data, and fitting max-plus polynomial functions.
In this paper we present theory, algorithms and applications for regression over the max- plus semiring. We show how max-plus 2-norm regression can be used to obtain maximum likelihood estimates for three different inverse problems. Namely inferring a max-plus linear dynamical systems model from a noisy time series recording, inferring the edge lengths of a network from shortest path information and fitting a max-plus polynomial function to data.