Representing piecewise linear functions minimally

  • Jayden Wang (University of Texas, Austin, USA)
E1 05 (Leibniz-Saal)


Piecewise linear functions are ubiquitous in tropical geometry, convex geometry, and machine learning. Every Piecewise Linear function can be represented as a tropical rational function (difference of max-affine functions), whereas not much has been done to define minimal representations. We propose two minimality concepts, induced by the so-called monomial length and factorization length of tropical polynomials. We will demonstrate that in practice, factorization length is better behaved in terms of solving the minimal representation of a piecewise linear function, due to the nice properties it satisfies, while the monomial length is related to extremal problems of equivalence classes of polytope pairs. The difference of those two concepts is controlled by arrangements of tropical hypersurfaces. We obtain a different proof of the lower bound by Tseran and Montúfar for the number of regions cut out by general tropical hypersurfaces and, as a byproduct, a lower bound for the number of vertices of Minkowski sums of polytopes.

Katharina Matschke

Max Planck Institute for Mathematics in the Sciences Contact via Mail

Guido Montúfar

Max Planck Institute for Mathematics in the Sciences