Tropical Fréchet Means: a polyhedral approach to exact optimization
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908898415345664 |
|---|---|
| author | Ferry, Kamillo Lin, Bo Améndola, Carlos Monod, Anthea Yoshida, Ruriko |
| author_facet | Ferry, Kamillo Lin, Bo Améndola, Carlos Monod, Anthea Yoshida, Ruriko |
| contents | 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,\ldots,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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_05322 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tropical Fréchet Means: a polyhedral approach to exact optimization Ferry, Kamillo Lin, Bo Améndola, Carlos Monod, Anthea Yoshida, Ruriko Optimization and Control Combinatorics Metric Geometry Statistics Theory 14T90, 62R01, 62R20, 90C24 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,\ldots,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. |
| title | Tropical Fréchet Means: a polyhedral approach to exact optimization |
| topic | Optimization and Control Combinatorics Metric Geometry Statistics Theory 14T90, 62R01, 62R20, 90C24 |
| url | https://arxiv.org/abs/2502.05322 |