Source-linked AI summary
Fréchet Means for Distributions of Persistence diagrams
Katharine Turner, Yuriy Mileyko, Sayan Mukherjee, John Harer
TL;DR
Computing Fréchet means for persistence diagrams lacked a procedure despite the existence of a probabilistic framework and established existence results. The paper introduces an algorithm that computes empirical local minima, proves convergence and a weak law of large numbers under finite Dirac-mixture distributions, and identifies important scope limitations.
Problem
A procedure was missing for computing Fréchet means and variances of persistence diagrams, although their probabilistic formulation and existence had been established.
Method
The paper uses a gradient-descent-based algorithm for Fréchet means, leveraging the Alexandrov-space structure of the L2-Wasserstein persistence-diagram space.
Results
The algorithm computes empirical local minima and satisfies a weak law of large numbers for iid samples from finite combinations of Dirac masses.
Takeaways & Limitations
The work provides a constructive method for estimating Fréchet means of persistence diagrams within the L2-Wasserstein setting.
Takeaways & Limitations
The results are restricted to finite Dirac-mixture measures and depend strongly on the L2-Wasserstein metric; broader measures and other Wasserstein metrics remain to be addressed.
Abstract
from arXiv · showhide
Given a distribution $ρ$ on persistence diagrams and observations $X_1,...X_n \stackrel{iid}{\sim} ρ$ we introduce an algorithm in this paper that estimates a Fréchet mean from the set of diagrams $X_1,...X_n$. If the underlying measure $ρ$ is a combination of Dirac masses $ρ= \frac{1}{m} \sum_{i=1}^m δ_{Z_i}$ then we prove the algorithm converges to a local minimum and a law of large numbers result for a Fréchet mean computed by the algorithm given observations drawn iid from $ρ$. We illustrate the convergence of an empirical mean computed by the algorithm to a population mean by simulations from Gaussian random fields.
1. Introduction
This paper addresses the missing procedure for computing Fréchet means and variances of persistence diagrams by introducing an estimation algorithm and analyzing its convergence. For finitely supported distributions, it provides a law of large numbers for algorithmically computed local minima.
- Persistence diagrams support probability distributions and statistical notions including expectations, variances, percentiles, and conditional probabilities.
- The paper fills a computational gap by characterizing Fréchet means and variances of finitely many persistence diagrams and providing an estimation algorithm.Existence had previously been established, but no procedure for computing means and variances was provided.
- The algorithm takes observed persistence diagrams and computes a new diagram that is a local minimum of the empirical Fréchet function.
- For iid samples from a finite combination of Dirac masses, the paper proves a weak law of large numbers for the local minima computed by the algorithm.
2. Persistence diagrams and Alexandrov spaces with curvature bounded from below
The paper develops the L2-Wasserstein framework for persistence diagrams and establishes geometric properties that support Fréchet-mean optimization. In this space, geodesics, curvature, semiconcavity, and supporting vectors provide the foundation for a gradient-descent algorithm.
- Persistence diagrams: Persistence diagrams encode homology classes as birth-death points, with persistence defined by d(α) − b(α), under a finite-persistence restriction.The diagrams are countable multisets in R2 together with infinitely many diagonal copies.
- Metric structure: The paper focuses on the L2-Wasserstein metric because it gives the diagram space a geodesic structure with known geometric properties.Optimal bijections between off-diagonal points and diagonal copies achieve the metric infimum.
- Metric structure: Diagrams can be connected by geodesics that linearly move paired points according to an optimal matching.For paired points x and φ(x), the interpolated location is (1 − t)x + tφ(x).
- Curvature: The diagram space is a non-negatively curved Alexandrov space but is not CAT(k) for any k > 0.The failure of CAT(k) follows from arbitrarily close diagrams having two distinct optimal geodesics.
- Fréchet optimization: For bounded distributions, the Fréchet function is semiconcave, and supporting vectors can be aggregated over the distribution.These supporting vectors serve as analogs of gradients for the optimization procedure.
3. Finding local minima of the Fr´echet function
The section presents a greedy Hungarian-algorithm procedure that updates a candidate diagram by arithmetic means of optimally paired points, and characterizes its local-minimum stopping condition. The procedure terminates because the Fréchet cost decreases across finitely many pairing configurations.
- Pairing subroutine: The Hungarian algorithm supplies optimal pairings by minimizing the total squared Euclidean assignment cost after adding enough diagonal copies.These pairings provide the correspondences used by the arithmetic-mean update.
- Algorithm 1: The algorithm initializes a candidate mean diagram, computes optimal pairings with each input using the Hungarian algorithm, and iteratively updates paired points by arithmetic means.Points may be paired with off-diagonal points or copies of the diagonal; the updated diagram becomes the next estimate unless the stopping condition holds.
- Alternative approach: A brute-force search could recover the complete mean set, but its combinatorial complexity is prohibitive compared with the greedy local-search approach.The brute-force method enumerates possible pairings and computes the arithmetic mean for each.
- Convergence: The greedy search terminates at a local minimum because each iteration decreases the Fréchet cost while using a new pairing configuration, and only finitely many configurations exist.The theorem states that the returned estimate is a local minimum when the algorithm terminates.
- Local-minimum condition: For a local minimum, every off-diagonal point equals the arithmetic mean of its uniquely optimally paired points across the input diagrams.The characterization also requires coincident off-diagonal points in the candidate to have coincident paired points in every input diagram.
4. Law of large numbers for the empirical Fr´echet mean
The section establishes convergence results for empirical Fréchet minima when the population distribution is a finite combination of Dirac masses. It also proves almost-sure convergence of empirical Fréchet mean sets when the population mean is unique, while identifying limits of the general theory.
- Scope and limitations: The paper does not establish comparable local-minimum convergence rates or a law of large numbers for unrestricted underlying measures.The authors also note that adapting general metric-space results to algorithmically computed local minima is unclear.
- Restricted law of large numbers: For a distribution that is a finite combination of Dirac masses, the paper provides a weak law of large numbers for local minima computed from sampled persistence diagrams.The empirical local minimum is constructed from multiplicity-weighted averages of the sampled Dirac-support diagrams.
- Local-minimum convergence: With high probability, empirical local minima lie close to population local minima, and the number of empirical local minima is finite and independent of sample size.The finite bound supports exploring the local-minimum set using multiple random initializations.
- Proof strategy: The proof controls sample multiplicities of the Dirac-support diagrams and constructs a nearby empirical diagram whose paired points are weighted arithmetic means.Hoeffding’s inequality supplies the probability control, while local pairing stability transfers the construction into a local minimum.
- Unique population mean: With probability 1, the Hausdorff distance between empirical and population Fréchet mean sets converges to zero when the population Fréchet function has a unique minimum.This result concerns the empirical mean set obtained from iid samples.
5. Persistence diagrams of random Gaussian fields
The paper uses persistence diagrams from random Gaussian fields to illustrate empirical Fréchet-mean convergence. Means are computed from increasingly large random samples, across dimensions zero and one, with variance summarized in Table 1.
- Simulation setup: Random Gaussian fields generate persistence diagrams whose points are expected to concentrate around the diagonal.The simulation uses fields over the unit square, with a stationary, isotropic, infinitely differentiable Gaussian field and covariance parameter α = 100.
- Observed convergence: As the number of diagrams averaged increases, the mean diagram moves closer to the diagonal, illustrating convergence of the empirical Fréchet means.The authors assess this visually using Figure 1 and quantify concentration by computing variances of distributions of sample Fréchet means.
- Figure 1: Figure 1 shows four differently colored means for each specified sample size, with dimension-zero means in the top rows and dimension-one sample plots below.Each mean uses a different random sample of diagrams.
- Simulation setup: Mean diagrams are computed from samples of 2, 4, 8, 16, 32, 64, and 128 diagrams drawn from 10,000 diagrams.The experiment repeats these sample sizes for both dimensions zero and one.
- Variance analysis: Table 1 reports the variance of the sample Fréchet means.Ten draws are taken for each sample size before the variance is computed.
6. Discussion
The discussion presents the algorithm and its convergence and law-of-large-numbers results as initial progress toward computing Fréchet means of persistence diagrams. It also identifies restrictions involving uniqueness, the underlying distribution, and the metric.
- Contributions: The paper introduces an algorithm for estimating Fréchet means and demonstrates local convergence plus a law of large numbers for finite Dirac-mixture measures.The measure has the form ρ = m^-1 Σ_i=1^m δ_Xi, where Xi are persistence diagrams.
- Open questions: A generic unique global minimum, and therefore a unique Fréchet mean, is conjectured but remains unproved.The discussion explicitly states that this belief still needs to be shown.
- Scope and extensions: The law-of-large-numbers result is restricted to underlying measures that are combinations of Dirac masses.The discussion identifies extending it beyond this class as an important next step.
- Scope and extensions: The results depend strongly on the L2-Wasserstein metric and are not intended to generalize directly to other metrics or algorithm variants.The authors call for a more general formulation using abstract metric spaces and probability theory.
Appendix A.
Appendix A establishes the compactness properties needed for Proposition 2.3. It constructs interpolation paths between persistence diagrams, proves their image set is relatively compact, and uses compactness to show the matching infimum is attained.
- Matching construction: The proof restricts matchings to bijections that do not pair off-diagonal points when matching both to the diagonal is more efficient.This defines the admissible set Φ used to construct paths between diagrams X and Y.
- Matching construction: For each admissible bijection φ, the path γφ(t) linearly interpolates matched points between diagrams X and Y.The collection S contains all such paths for t ∈ [0,1] and φ ∈ Φ.
- Compactness: Relative compactness of S follows by showing that it is bounded, off-diagonally birth-death bounded, and uniform.Theorem 21 states these conditions are equivalent to relative compactness in the relevant persistence-diagram space.
- Compactness: The uniformity argument bounds the number of points above each persistence threshold using the corresponding counts in X ∪ Y.For every Z ∈ S, Nk(Z) ≤ Nk(X ∪ Y).
- Attainment of the infimum: Compactness of the path space via Arzelà–Ascoli yields a convergent subsequence of paths whose limit joins X to Y.Following point correspondences along the limiting path constructs a bijection that achieves the infimum.