Tropical Fréchet Means: a polyhedral approach to exact optimization

Abstract

The Fréchet mean is a fundamental notion of central tendency defined as a minimizer of a sum of squared distances in a general metric space. In this paper, we study Fréchet means in tropical geometry -- a piecewise linear, combinatorial, and polyhedral variant of algebraic geometry -- by formulating and solving the associated tropical quadratic optimization problem. We give a geometric characterization of the collection of all tropical Fréchet means as a bounded set that is simultaneously tropically and classically convex, hence a polytrope. We establish the existence of positivity certificates for maxima of finitely many quadratic polynomials in $\mathbb{R}[x_1,\dots ,x_n]$ whose homogeneous quadratic components are sums of squares, which provides a symbolic framework for exact optimization. Using this structure, we develop algorithms for computing tropical Fréchet means and the associated Fréchet mean polytrope. We further describe a combinatorial type decomposition of the objective function induced by braid arrangements, yielding a piecewise quadratic representation and a fully symbolic method for exact computation.

26 pages. 8 figures. v3: Added Section 5. Extended version as to appear in the special issue for the International Symposium on Symbolic and Algebraic Computation ISSAC 2025