Tropical Fermat-Weber points

DOI10.1137/16M1071122MaRDI QIDQ4564885zbMATH OpenFDO

Authors Bo Lin, Ruriko Yoshida

Publication date 7 June 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.04674

zbMATH Keywords

convex polytopesFermat-Weber pointstropical geometryultrametrics

Mathematics Subject Classification ID

Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25) (n)-dimensional polytopes (52B11) General biology and biomathematics (92B05) General biostatistics (92B15)

Abstract: In a metric space, the Fermat-Weber points of a sample are statistics to measure the central tendency of the sample and it is well-known that the Fermat-Weber point of a sample is not necessarily unique in the metric space. We investigate the computation of Fermat-Weber points under the tropical metric on the quotient space $$ with a fixed $ninmathbbN$, motivated by its application to the space of equidistant phylogenetic trees with $N$ leaves (in this case $$) realized as the tropical linear space of all ultrametrics. We show that the set of all tropical Fermat-Weber points of a finite sample is always a classical convex polytope, and we present a combinatorial formula for a key value associated to this set. We identify conditions under which this set is a singleton. We apply numerical experiments to analyze the set of the tropical Fermat-Weber points within a space of phylogenetic trees. We discuss the issues in the computation of the tropical Fermat-Weber points.

Recommendations

• On the Fermat-Weber point of a polygonal chain and its generalizations
• On the Fermat-Weber center of a convex object
• Convexity in tree spaces
• The inverse Fermat-Weber problem
• Tropical convexity

Cites work

• Best approximation in max-plus semimodules
• Convexity in tree spaces
• Duality and separation theorems in idempotent semimodules.
• Geometry of the space of phylogenetic trees
• scientific article; zbMATH DE number 6437647 (Why is no real title available?)
• L-infinity optimization to linear spaces and phylogenetic trees
• Lectures on Polytopes
• polymake: a framework for analyzing convex polytopes
• Shortest connectivity. An introduction with applications in phylogeny.
• The tropical Grassmannian

Cited in

(18)

• Tropical principal component analysis and its application to phylogenetics
• Tropical optimal transport and Wasserstein distances
• Tropical geometric variation of tree shapes
• The distribution of Weierstrass points on a tropical curve
• Information geometry for phylogenetic trees
• L-infinity optimization to Bergman fans of matroids with an application to phylogenetics
• L-infinity optimization to linear spaces and phylogenetic trees
• Convexity in tree spaces
• Tropical medians by transportation
• Classifying tree topology changes along tropical line segments
• Asymmetric tropical distances and power diagrams
• Tropical logistic regression model on space of phylogenetic trees
• Tropical convexity in location problems
• Fréchet mean set estimation in the Hausdorff metric, via relaxation
• Tropical gradient descent
• Variance inequalities for transformed Fréchet means in Hadamard spaces
• Tropical Fréchet means: a polyhedral approach to exact optimization
• Tropical Fréchet means

Describes a project that uses

Uses Software

• ape
• Maple
• polymake

This page was built for publication: Tropical Fermat-Weber points

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4564885)