PaperlayerView exact revision on arXiv

Source-linked AI summary

Computing medians and means in Hadamard spaces

Miroslav Bacak

arXiv:1210.2145v3math.MGq-bio.QM

TL;DR

The paper addresses unavailable algorithms for Fréchet means and medians in Hadamard spaces. It develops a splitting proximal point method and a law-of-large-numbers approach, with examples in BHV tree space and applications to broader optimization problems.

  • Problem

    BHV tree space had no available algorithm for computing the Fréchet mean, although average evolutionary trees are desirable in phylogenetics.

  • Method

    The paper uses a splitting proximal point algorithm and derives an approximation algorithm for the Fréchet mean from the law of large numbers.

  • Results

    The weighted average method yields w ∈[0, z] with d(0, w) = 5, while the Fréchet mean has d(0, Ξ) = 1 and Birkhoff’s or centroid methods produce d(0, c) > 5.

  • Takeaways & Limitations

    Hadamard spaces include BHV tree space and settings relevant to phylogenetics, diffusion tensor imaging, and consensus algorithms.

  • Takeaways & Limitations

    The approach retains a local compactness assumption because compactness of finite-set closed convex hulls is unknown in general Hadamard spaces.

Abstract

from arXiv · show

The geometric median as well as the Frechet mean of points in an Hadamard space are important in both theory and applications. Surprisingly, no algorithms for their computation are hitherto known. To address this issue, we use a split version of the proximal point algorithm for minimizing a sum of convex functions and prove that this algorithm produces a sequence converging to a minimizer of the objective function, which extends a recent result of D. Bertsekas (2001) into Hadamard spaces. The method is quite robust and not only does it yield algorithms for the median and the mean, but it also applies to various other optimization problems. We moreover show that another algorithm for computing the Frechet mean can be derived from the law of large numbers due to K.-T. Sturm (2002). In applications, computing medians and means is probably most needed in tree space, which is an instance of an Hadamard space, invented by Billera, Holmes, and Vogtmann (2001) as a tool for averaging phylogenetic trees. It turns out, however, that it can be also used to model numerous other tree-like structures. Since there now exists a polynomial-time algorithm for computing geodesics in tree space due to M. Owen and S. Provan (2011), we obtain efficient algorithms for computing medians and means, which can be directly used in practice.

1. Introduction

The paper introduces algorithms for medians and means in Hadamard spaces, addressing computational gaps with splitting proximal-point methods and a law-of-large-numbers approach. BHV tree space provides a practically important application because geodesics can be computed efficiently.

  • The BHV tree space and statistical biology.: BHV tree space models phylogenetic trees and other tree-like structures, making means and medians relevant to computational phylogenetics and related applications.
  • The paper’s goal is to introduce algorithms for computing medians and means in Hadamard spaces.
  • In a three-ray Hadamard space, the true Fréchet mean lies at distance 1 from the origin, whereas two earlier methods produce a point at distance greater than 5.
  • A splitting proximal-point algorithm applies to both medians and means and extends Bertsekas’ convergence results to locally compact Hadamard spaces.The method applies component resolvents in cyclic or random order.
  • A second method approximates the Fréchet mean using the law of large numbers.
  • The BHV tree space and statistical biology.: Polynomial-time geodesic algorithms in BHV tree space make the paper’s median and mean algorithms directly applicable in practice.

On the objective function.

The objective-function framework represents medians, means, and broader convex optimization problems as sums of convex functions in Hadamard spaces. Splitting proximal-point methods then connect these objectives to resolvents, projections, and gradient-flow approximations.

  • The framework also covers distance functions, displacement functions, Busemann functions, energy functionals, and constrained problems via indicator functions.Indicator functions convert minimization over a closed convex set into unconstrained minimization over the whole space.
  • For f(x)=Σ_n w_n d(x,a_n)^p, p=1 gives the geometric median objective and p=2 gives the Fréchet mean objective.The mean is equivalently the barycenter of the corresponding discrete probability measure.
  • With indicator functions, the same method becomes cyclic or random projections and converges to a point in the intersection of the closed convex sets.
  • The nonlinear Lie-Trotter-Kato formula approximates the gradient-flow semigroup of the sum using resolvents of its component functions.

The law of large numbers in Hadamard space.

The law of large numbers provides an alternative algorithm for computing Fréchet means in Hadamard spaces. The section situates this approach within the geometry and optimization framework used throughout the paper.

  • The probabilistic viewpoint enables an alternative algorithm for computing the Fréchet mean.The paper compares this algorithm with proximal-point-based methods.
  • The paper’s main results include cyclic and random-order proximal point algorithms that converge to minimizers.These algorithms are applied to means and medians before the law-of-large-numbers method is treated separately.
  • Hadamard spaces are complete CAT(0) spaces in which every two points are connected by a unique geodesic.Their defining inequality controls squared distances along geodesics.
  • The framework includes BHV tree space, Euclidean spaces, hyperbolic spaces, nonpositively curved manifolds, Euclidean buildings, R-trees, and CAT(0) complexes.The main theorems assume local compactness, but the Section 5 algorithm does not.
  • In Hadamard spaces, geodesic interpolation defines convex sets and convex functions, while metric projections onto closed convex sets are unique and nonexpansive.Convex lower-semicontinuous coercive functions have minimizers.

Means.

The Fréchet mean is the unique minimizer of the weighted squared-distance objective in a Hadamard space. It satisfies a variance inequality and coincides with the weighted arithmetic mean in Euclidean space.

  • A finite weighted Fréchet mean is defined as the minimizer of the weighted sum of squared distances.The weights are positive and sum to 1.
  • Nonpositive curvature guarantees existence and uniqueness of the Fréchet mean.Theorem 2.4 also establishes its variance inequality.
  • In Euclidean space, the Fréchet mean coincides with the usual weighted arithmetic mean.The displayed expression gives w1a1 + ··· + wNaN.

Medians.

The geometric median minimizes a weighted sum of distances in a Hadamard space, but unlike the Fréchet mean it need not be unique. The paper’s convergence results support its computation through proximal methods.

  • The weighted geometric median is defined as a minimizer of the weighted sum of distances to the input points.
  • The median objective is convex, continuous, and coercive, so it has a minimizer.
  • Medians may contain more than one point in general, unlike means.A median is also an optimal solution to the Fermat-Weber facility-location problem.
  • The paper’s convergence proofs use a supermartingale convergence theorem and a deterministic variant.These results underpin the proximal algorithms developed for the optimization problems.

3. The proximal point algorithm

The paper adapts the proximal point algorithm to minimize sums of convex lower-semicontinuous functions in Hadamard spaces. Instead of computing the full objective’s resolvent, it successively applies component resolvents, yielding convergent cyclic or random-order schemes.

  • The proximal point algorithm finds minimizers of convex lower-semicontinuous functions, and its convergence extends from Euclidean spaces to Hadamard spaces.
  • Under local compactness, attainment of the minimum, and Σλk = ∞, the PPA sequence converges to a minimizer.The sequence starts from an arbitrary point x0 and uses positive step parameters.
  • For sums f = Σfn, component resolvents are used because they are often easier to compute than the resolvent of f itself.This applies in particular to median and mean objectives.
  • The component resolvents can be applied either in a fixed cyclic order or by randomly selecting a component at each step.
  • The resulting splitting proximal point method extends a Euclidean convergence result of Bertsekas to Hadamard spaces.

Cyclic order version.

The cyclic proximal point algorithm applies component resolvents in a fixed order and, under stated assumptions, produces a sequence converging to a minimizer.

  • Cyclic order version.: The algorithm applies marginal resolvents cyclically, using a step size that remains constant throughout each cycle.The procedure is defined from an arbitrary starting point and a positive step-size sequence.
  • Cyclic order version.: The convergence theorem assumes a locally compact Hadamard space, a nonempty minimizer set, and a uniform Lipschitz-type bound.Under these conditions, the generated sequence converges to a minimizer of f.
  • Cyclic order version.: The proof establishes a squared-distance inequality over each cycle, combining objective decrease with an error term controlled by the step size.The inequality is then used to show boundedness and convergence properties of the iterates.
  • Cyclic order version.: The sequence of cycle endpoints is shown to be Cauchy and converges to a minimizer, after which the entire sequence converges to the same point.Continuity and lower semicontinuity arguments identify the limit as a minimizer.

Random order version.

The random-order proximal point algorithm selects component resolvents independently and uniformly at random, and under the stated assumptions converges almost surely to a minimizer.

  • Random order version.: At each iteration, the randomized algorithm independently selects one component resolvent according to the uniform distribution.The resulting sequence is defined on the product probability space of these random selections.
  • Random order version.: The proof uses an almost-supermartingale property together with conditional expectations and a supermartingale convergence theorem.This establishes convergence of distances and objective values along the randomized sequence.
  • Random order version.: The random-order convergence theorem assumes a locally compact Hadamard space, a nonempty minimizer set, and the required Lipschitz condition.It concludes almost-sure convergence of the iterates to a minimizer.
  • Random order version.: The cyclic and random algorithms apply in particular when the component functions are Lipschitz or when the objective has the form used for means and medians.For the latter objectives, boundedness follows from containment in the closed convex hull of the input points.
  • Random order version.: The general convergence result relies on local compactness because compactness of finite-point closed convex hulls is unknown in arbitrary Hadamard spaces.This prevents simply dropping the local compactness assumption in the stated generality.

4. Computing medians and means

The general proximal point results yield practical algorithms for weighted means in Hadamard spaces by reducing multidimensional minimization to successive one-dimensional geodesic updates.

  • 4. Computing medians and means: The algorithms can be applied directly to compute means and medians in locally compact Hadamard spaces.They convert the multidimensional optimization problem into a sequence of one-dimensional minimizations.
  • 4. Computing medians and means: For the weighted mean, the objective is the weighted sum of squared distances from a variable point to the input points.The minimizer exists uniquely by the preceding Hadamard-space result.
  • 4. Computing medians and means: Each cyclic mean update minimizes a component proximal objective and therefore lies on the geodesic joining the current iterate to the corresponding data point.The update coefficient is determined explicitly from the weight and step size.
  • 4. Computing medians and means: The cyclic mean algorithm converges to the weighted mean, as follows from the cyclic proximal point convergence theorem.With uniform weights, the update coefficients are independent of the selected data-point index.
  • 4. Computing medians and means: The randomized mean algorithm selects data points uniformly at random and also converges to the weighted mean.Its convergence follows from the random-order proximal point theorem.

Algorithms for computing medians.

The same proximal point framework produces cyclic and randomized algorithms for weighted geometric medians, with convergence guaranteed under the paper’s Hadamard-space assumptions.

  • Algorithms for computing medians.: For weighted medians, the objective is the weighted sum of distances from a variable point to the input points.The component functions are Lipschitz, satisfying the assumptions required by both convergence theorems.
  • Algorithms for computing medians.: Each median proximal update lies on the geodesic from the current iterate to the selected data point.The associated coefficient belongs to [0, 1] and is determined separately for cyclic and randomized updates.
  • Algorithms for computing medians.: The cyclic median algorithm converges to the weighted median of the input points.This follows from the cyclic-order convergence theorem.
  • Algorithms for computing medians.: The randomized median algorithm chooses indices uniformly at random and converges to the median.Its convergence follows from the random-order convergence theorem.
  • Algorithms for computing medians.: The framework also covers minimizing weighted sums of distances to convex closed subsets, provided at least one subset is bounded.The random algorithm uses metric projections and converges to a minimizer.

5. Computing means via the law of large numbers

This section presents a law-of-large-numbers approach for approximating the Fréchet mean and derives a convergent randomized algorithm. It also compares this method with Algorithm 4.2, showing how weighting changes the sampling distribution or update coefficients.

  • The alternative Fréchet-mean algorithm is based on the law of large numbers and does not require the Hadamard space to be locally compact.The section also compares it with Algorithm 4.2.
  • Sturm’s nonlinear law of large numbers applies to independent, identically distributed H-valued random variables and provides pointwise convergence.The variables are distributed according to π, and the theorem is stated for Hadamard spaces.
  • The induced approximation algorithm takes points and positive weights as input and generates iterates sk converging to the desired Fréchet mean Ξ.At each iteration, it randomly selects an input point according to the weight distribution.
  • In the unweighted case, algorithm (35) and Algorithm 4.2 produce the same sequence when λk := 1/(2k), making algorithm (35) a special case of Algorithm 4.2.Both methods select points uniformly in this setting.
  • With weights, algorithm (35) changes the point-selection probability, whereas Algorithm 4.2 keeps uniform sampling and changes the update coefficients.Thus the two algorithms differ for weighted Fréchet means.

Final remarks.

The algorithms require geodesic computation at every iteration, and the Owen–Provan algorithm provides a polynomial-time way to perform this step in BHV tree space.

  • Every presented algorithm requires finding a geodesic, or a point on one, at each iteration.Algorithm 4.4, for example, computes xk+1 on the geodesic [xk, ark].
  • In BHV tree space, the Owen–Provan algorithm computes the required geodesic point in polynomial time.
Loading 1210.2145v3…