pith. sign in

arxiv: 1907.05937 · v1 · pith:TE6I2IG2new · submitted 2019-07-12 · 🧮 math.CO · q-bio.PE

Properties for the Frechet Mean in Billera-Holmes-Vogtmann Treespace

Maria Anaya , Olga Anipchenko-Ulaj , Aisha Ashfaq , Joyce Chiu , Mahedi Kaiser , Max Shoji Ohsawa , Megan Owen , Ella Pavlechko
show 4 more authors
Katherine St. John Shivam Suleria Keith Thompson Corrine Yap
This is my paper

Pith reviewed 2026-05-24 22:11 UTC · model grok-4.3

classification 🧮 math.CO q-bio.PE
keywords Frechet meanBHV treespaceweighted treesorthant spacesedge conditionsphylogenetic treesgeodesic distance
0
0 comments X

The pith

Necessary and sufficient conditions for an edge to be in the Frechet mean are inequalities on the weights of the edges.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper derives the first conditions that tell exactly when an edge must appear in the intrinsic average of a set of weighted trees. This average, called the Frechet mean, is the unique point in BHV treespace that minimizes the sum of squared geodesic distances to the given trees. Until now only iterative approximation methods existed, with no way to certify in advance which edges the mean would contain. The new conditions are simple inequalities on edge weights and immediately identify the orthant that must contain the mean, turning an open search into a preprocessing filter. The same style of conditions extends directly to arbitrary orthant spaces.

Core claim

We give the first necessary and sufficient conditions for an edge to be in the Frechet mean. The conditions are in the form of inequalities on the weights of the edges. These conditions provide a pre-processing step for finding the treespace orthant containing the Frechet mean. This work generalizes to orthant spaces.

What carries the argument

The weight inequalities that serve as necessary and sufficient conditions for an edge to belong to the Frechet mean.

If this is right

  • The orthant containing the Frechet mean can be identified before any iterative search begins.
  • The conditions supply a polynomial-time filter that narrows the combinatorial search space for the mean.
  • The same characterization applies verbatim to the Frechet mean in any orthant space.
  • Once the orthant is known, existing approximation algorithms can be restricted to that orthant.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The inequalities may combine with existing solvers to produce exact rather than approximate means in small instances.
  • In phylogenetic applications the conditions could reduce the cost of averaging large sets of evolutionary trees.
  • Analogous weight-based tests may exist for other intrinsic statistics on the same space.

Load-bearing premise

The Frechet mean exists and is unique in BHV treespace.

What would settle it

A collection of trees together with an edge that satisfies the stated weight inequalities yet lies outside the true Frechet mean, or an edge that fails the inequalities yet appears in the mean.

Figures

Figures reproduced from arXiv: 1907.05937 by Aisha Ashfaq, Corrine Yap, Ella Pavlechko, Joyce Chiu, Katherine St. John, Keith Thompson, Mahedi Kaiser, Maria Anaya, Max Shoji Ohsawa, Megan Owen, Olga Anipchenko-Ulaj, Shivam Suleria.

Figure 1
Figure 1. Figure 1: a) Five of the 15 7-dimensional orthants in [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: a) Tree T with common split Y |Z corresponding to edge e = {u, v}. Deleting edge e splits tree T into b) tree T Y with leaves Y ∪ u and c) tree T Z with leaves Z ∪ v. f(T) = Xr i=1 d(T, Ti) 2 (3) where d is the BHV distance. Sturm [33] showed that the Fr´echet mean is unique on globally non-postivively curved spaces, such as the BHV treespace [6]. Baˇc´ak [2] and Miller et al. [22] inde￾pendently adapted S… view at source ↗
Figure 3
Figure 3. Figure 3: (a) An example of three trees with the same topology on 5 leaves, [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: (a) Three trees, T1, T2, and T3, are in three different orthants that share an axis, and one tree, T4, lies on this axis. The translated log maps based at T1, T2, and T3 are shown in (b), (c), and (d), respectively. In each log map, the two orthants not containing the base tree have been identified with each other, and the shared axis is extended in the negative direction. The tangent spaces shown in (b), … view at source ↗
read the original abstract

The Billera-Holmes-Vogtmann (BHV) space of weighted trees can be embedded in Euclidean space, but the extrinsic Euclidean mean often lies outside of treespace. Sturm showed that the intrinsic Frechet mean exists and is unique in treespace. This Frechet mean can be approximated with an iterative algorithm, but bounds on the convergence of the algorithm are not known, and there is no other known polynomial algorithm for computing the Frechet mean nor even the edges present in the mean. We give the first necessary and sufficient conditions for an edge to be in the Frechet mean. The conditions are in the form of inequalities on the weights of the edges. These conditions provide a pre-processing step for finding the treespace orthant containing the Frechet mean. This work generalizes to orthant spaces.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The manuscript derives the first necessary and sufficient conditions, expressed as inequalities involving edge weights, that characterize precisely which edges appear in the (unique) Fréchet mean of a collection of trees in BHV treespace. The argument relies on the orthant geometry of the space and on Sturm's theorem guaranteeing existence and uniqueness of the mean; the conditions are positioned as a preprocessing step that identifies the orthant containing the mean, with a noted generalization to general orthant spaces.

Significance. If the stated conditions are correctly derived and verified, the result supplies an explicit, checkable characterization of the support of the Fréchet mean that was previously unavailable. This would constitute a concrete algorithmic advance over purely iterative approximation methods whose convergence rates remain unknown, and the necessary-and-sufficient form together with the orthant-space generalization strengthens the contribution.

minor comments (1)
  1. [Abstract] The abstract asserts that the conditions are 'necessary and sufficient' and 'in the form of inequalities on the weights of the edges'; the manuscript should include an explicit statement of these inequalities (e.g., as a numbered theorem) together with the proof that they are both necessary and sufficient.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and for recommending acceptance. The referee's summary correctly identifies the main contribution: the first necessary and sufficient conditions, expressed as inequalities on edge weights, that characterize the edges present in the unique Fréchet mean.

Circularity Check

0 steps flagged

No significant circularity; derivation from orthant geometry definition

full rationale

The paper derives necessary and sufficient weight inequalities characterizing edges in the Fréchet mean directly from the definition of the mean in BHV treespace orthant geometry. It invokes Sturm's theorem (an external result on CAT(0) spaces) only for existence and uniqueness of the target object, with no self-citation load-bearing the central claim. No equations reduce by construction to fitted inputs, renamed patterns, or ansatzes smuggled via prior work by the same authors. The result is self-contained against the stated geometric definition.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on Sturm's existence and uniqueness theorem for the Fréchet mean in treespace and on the piecewise-Euclidean orthant structure of BHV space; no free parameters or new entities are introduced in the abstract.

axioms (1)
  • domain assumption The Fréchet mean exists and is unique in BHV treespace
    Invoked from Sturm to guarantee a well-defined mean whose edges can be characterized.

pith-pipeline@v0.9.0 · 5717 in / 1210 out tokens · 25968 ms · 2026-05-24T22:11:29.478680+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages · 2 internal anchors

  1. [1]

    Allen and M

    B. Allen and M. Steel. Subtree transfer operations and their induced metrics on evolutionary trees. Annals of Combinatorics , 5:1–13, 2001

    work page 2001

  2. [2]

    Computing medians and means in hadamard spaces

    Miroslav Bac´ ak. Computing medians and means in hadamard spaces. SIAM Journal on Optimization, 24(3):1542–1566, 2014

    work page 2014

  3. [3]

    The logarithm map, its limits and Fr´ echet means in orthant spaces

    Dennis Barden and Huiling Le. The logarithm map, its limits and Fr´ echet means in orthant spaces. Proceedings of the London Mathematical Society, 117(4):751–789, 2018

    work page 2018

  4. [4]

    Central limit theorems for Fr´ echet means in the space of phylogenetic trees

    Dennis Barden, Huiling Le, and Megan Owen. Central limit theorems for Fr´ echet means in the space of phylogenetic trees. Electronic Journal of Probability, 18(25):1–25, 2013

    work page 2013

  5. [5]

    Limiting behaviour of Fr´ echet means in the space of phylogenetic trees

    Dennis Barden, Huiling Le, and Megan Owen. Limiting behaviour of Fr´ echet means in the space of phylogenetic trees. Annals of the Institute of Statistical Mathematics , pages 1–31, 2016

    work page 2016

  6. [6]

    Billera, S.P

    L.J. Billera, S.P. Holmes, and K. Vogtmann. Geometry of the space of phylogenetic trees. Advances in Applied Mathematics , 27:733–767, 2001

    work page 2001

  7. [7]

    On the computational complexity of the rooted subtree prune and regraft distance

    Magnus Bordewich and Charles Semple. On the computational complexity of the rooted subtree prune and regraft distance. Annals of Combintorics , 8:409–423, 2004

    work page 2004

  8. [8]

    Martin R Bridson and Andr´ e Haefliger.Metric spaces of non-positive curvature, Grundlehren der mathematischen Wissenshaften, vol. 319 . Springer, 1999

    work page 1999

  9. [9]

    Mean and Variance of Phylogenetic Trees

    Daniel G. Brown and Megan Owen. Mean and variance of phylogenetic trees. arXiv preprint arXiv:1708.00294, 2017

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  10. [10]

    Peter Buneman

    O. Peter Buneman. The recovery of trees from measures of dissimilarity. Mathematics in the Archaeological and Historical Sciences, pages 387–395, 1971. 26

    work page 1971

  11. [11]

    On comput- ing the nearest neighbor interchange distance

    Bhaskar DasGupta, Xin He, Tao Jiang, Ming Li, John Tromp, and Louxin Zhang. On comput- ing the nearest neighbor interchange distance. In D.Z. Du, P.M. Pardalos, and J. Wang, editors, Proceedings of the DIMACS Workshop on Discrete Problems with Medical Applications , vol- ume 55 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science , pa...

    work page 2000

  12. [12]

    SageMath, the Sage Mathematics Software System (Version 6.10) , 2015

    The Sage Developers. SageMath, the Sage Mathematics Software System (Version 6.10) , 2015. http://www.sagemath.org

    work page 2015

  13. [13]

    Wille, Laura H

    Aasa Feragen, Megan Owen, Jens Petersen, Mathilde M.W. Wille, Laura H. Thomsen, Asger Dirksen, and Marleen de Bruijne. Tree-space statistics and approximations for large-scale analysis of anatomical trees. In International Conference on Information Processing in Medical Imaging, pages 74–85. Springer, 2013

    work page 2013

  14. [14]

    Geodesic atlas-based labeling of anatomical trees: Application and evaluation on airways extracted from ct

    Aasa Feragen, Jens Petersen, Megan Owen, Pechin Lo, Laura Hohw¨ u Thomsen, Mathilde Marie Winkler Wille, Asger Dirksen, and Marleen de Bruijne. Geodesic atlas-based labeling of anatomical trees: Application and evaluation on airways extracted from ct. IEEE transactions on medical imaging, 34(6):1212–1226, 2015

    work page 2015

  15. [15]

    Les ´ el´ ements al´ eatoires de nature quelconque dans un espace distanci´ e.Ann

    Maurice Fr´ echet. Les ´ el´ ements al´ eatoires de nature quelconque dans un espace distanci´ e.Ann. Inst. H. Poincar´ e, 10(3):215–310, 1948

    work page 1948

  16. [16]

    SPR distance com- putation for unrooted trees

    Glenn Hickey, Frank Dehne, Andrew Rau-Chaplin, and Christian Blouin. SPR distance com- putation for unrooted trees. Evolutionary Bioinformatics, 4:17–27, 2008

    work page 2008

  17. [17]

    Mat- tingly, Ezra Miller, James Nolen, Megan Owen, Vic Patrangenaru, Sean Skwerer, et al

    Thomas Hotz, Stephan Huckemann, Huiling Le, James Stephen Marron, Jonathan C. Mat- tingly, Ezra Miller, James Nolen, Megan Owen, Vic Patrangenaru, Sean Skwerer, et al. Sticky central limit theorems on open books. The Annals of Applied Probability , 23(6):2238–2258, 2013

    work page 2013

  18. [18]

    Sticky central limit theorems at isolated hyperbolic planar singularities

    Stephan Huckemann, Jonathan Mattingly, Ezra Miller, James Nolen, et al. Sticky central limit theorems at isolated hyperbolic planar singularities. Electronic Journal of Probability , 20, 2015

    work page 2015

  19. [19]

    The shape of phylogenetic treespace

    Katherine St John. The shape of phylogenetic treespace. Systematic Biology, 66(1):e83, 2017

    work page 2017

  20. [20]

    Mapping phylogenetic trees to reveal distinct patterns of evolution

    Michelle Kendall and Caroline Colijn. Mapping phylogenetic trees to reveal distinct patterns of evolution. bioRxiv, page 026641, 2015

    work page 2015

  21. [21]

    A simulation comparison of phylogeny algorithms under equal and unequal evolutionary rates

    Mary K Kuhner and Joseph Felsenstein. A simulation comparison of phylogeny algorithms under equal and unequal evolutionary rates. Molecular Biology and Evolution , 11(3):459–468, 1994

    work page 1994

  22. [22]

    Scott Provan

    Ezra Miller, Megan Owen, and J. Scott Provan. Polyhedral computational geometry for aver- aging metric phylogenetic trees. Advances in Applied Mathematics , 68:51–91, 2015

    work page 2015

  23. [23]

    Tom M.W. Nye. Principal components analysis in the space of phylogenetic trees. The Annals of Statistics, pages 2716–2739, 2011

    work page 2011

  24. [24]

    Tom M.W. Nye. An algorithm for constructing principal geodesics in phylogenetic treespace. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 11(2):304–315, 2014. 27

    work page 2014

  25. [25]

    Tom M.W. Nye. Convergence of random walks to Brownian motion in phylogenetic tree-space. arXiv preprint arXiv:1508.02906 , 2015

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  26. [26]

    Principal component analysis and the locus of the Fr´ echet mean in the space of phylogenetic trees

    Tom MW Nye, Xiaoxian Tang, Grady Weyenberg, and Ruriko Yoshida. Principal component analysis and the locus of the Fr´ echet mean in the space of phylogenetic trees. Biometrika, 104(4):901–922, 2017

    work page 2017

  27. [27]

    Distance Computation in the Space of Phylogenetic Trees

    Megan Owen. Distance Computation in the Space of Phylogenetic Trees . PhD thesis, Cornell University, 2008

    work page 2008

  28. [28]

    Computing geodesic distances in tree space

    Megan Owen. Computing geodesic distances in tree space. SIAM Journal on Discrete Math- ematics, 25(4):1506–1529, 2011

    work page 2011

  29. [29]

    Scott Provan

    Megan Owen and J. Scott Provan. A fast algorithm for computing geodesic distances in tree space. IEEE/ACM Transactions on Computational Biology & Bioinformatics, 8:2–13, January 2011

    work page 2011

  30. [30]

    Phylogenetics, volume 24 of Oxford Lecture Series in Mathe- matics and its Applications

    Charles Semple and Mike Steel. Phylogenetics, volume 24 of Oxford Lecture Series in Mathe- matics and its Applications . Oxford University Press, Oxford, 2003

    work page 2003

  31. [31]

    Tree-oriented analysis of brain artery structure

    Sean Skwerer, Elizabeth Bullitt, Stephan Huckemann, Ezra Miller, Ipek Oguz, Megan Owen, Vic Patrangenaru, Scott Provan, and James Stephen Marron. Tree-oriented analysis of brain artery structure. Journal of Mathematical Imaging and Vision , 50(1-2):126–143, 2014

    work page 2014

  32. [32]

    Sean Skwerer, Scott Provan, and J.S. Marron. Relative optimality conditions and algorithms for treespace Fr´ echet means.SIAM Journal on Optimization , 28(2):959–988, 2018

    work page 2018

  33. [33]

    Probability measures on metric spaces of nonpositive curvature

    Karl-Theodor Sturm. Probability measures on metric spaces of nonpositive curvature. In Heat kernels and analysis on manifolds, graphs, and metric spaces (Paris, 2002) , volume 338 of Contemp. Math., pages 357–390. Amer. Math. Soc., Providence, RI, 2003

    work page 2002

  34. [34]

    Geodesics in the space of trees, 2007

    Karen Vogtmann. Geodesics in the space of trees, 2007. Available at http://pi.math. cornell.edu/~vogtmann/papers/TreeGeodesicss/geodesics07.pdf. Last accessed July 31, 2018

    work page 2007

  35. [35]

    Confidence sets for phylogenetic trees

    Amy Willis. Confidence sets for phylogenetic trees. Journal of the American Statistical Asso- ciation, pages 1–10, 2018

    work page 2018

  36. [36]

    Uncertainty in phylogenetic tree estimates

    Amy Willis and Rayna Bell. Uncertainty in phylogenetic tree estimates. Journal of Computa- tional and Graphical Statistics , 27(3):542–552, 2018. 28

    work page 2018