PaperlayerView exact revision on arXiv

Source-linked AI summary

Persistence Meets Resistance: Doubling Down on Hardness

Benedikt Kolbe, Tim Mayr

arXiv:2608.27269v1math.ATcs.CCcs.CG

TL;DR

The paper asks how efficiently stable invariants of metric-space filtrations can be approximated and combines geometric approximation schemes with fine-grained hardness reductions. It obtains linear-time one-parameter approximations, constant-time-in-n probabilistic results for selected normalized bifiltrations, and matrix-rank reductions establishing hardness boundaries.

  • Problem

    Efficient approximation of stable barcodes and multifiltration invariants remains limited, while the existence of subquadratic barcode approximations and lower bounds is unclear.

  • Method

    The paper combines greedy-permutation and uniform-sampling approximations with reductions embedding matrix-rank constructions into VR or Čech filtrations.

  • Results

    The paper gives linear-time additive approximations for stable barcodes, constant-time-in-n probabilistic approximations for selected normalized measure bifiltrations, and additive and multiplicative hardness results.

  • Takeaways & Limitations

    Approximation is tractable under controlled geometric growth but becomes hard without doubling-dimension control or for sufficiently exact additive and constant-factor multiplicative goals.

  • Takeaways & Limitations

    The practical relevance of the upper bounds and whether they improve state-of-the-art implementations remain open questions.

Abstract

from arXiv · show

We present results on the approximate computation of stable invariants for filtrations of finite metric spaces in the context of persistent homology. We establish novel approximation algorithms in the setting of $n$-point metric spaces where the growth of the doubling dimension is in $o(\log n)$ and the diameter is bounded. In the $1$-parameter case, by revisiting known techniques (greedy permutations) in a new way, we derive the first linear-time algorithms for the problem of computing additive $\varepsilon$-approximations of any stable barcode. By deriving bounds on the convergence rate and the approximation quality of uniform samples, we extend the approach to selected multiparameter filtrations. We show that for normalized measure bifiltrations, including the multicover and subdivision-Rips bifiltration, any stable invariant can be probabilistically approximated in time constant in $n$. The constants in the running times of our algorithms depend on the doubling dimension, the diameter and the success probability. We further study the problem through the lens of fine-grained complexity and show that computing the rank of a matrix reduces to that of approximating the barcode of the Vietoris--Rips or Čech filtration. We present two variants of the reduction, one for sufficiently good additive approximations and the other for any constant factor multiplicative approximations.

1 Introduction

The paper studies when stable persistence invariants can be approximated efficiently and establishes both geometric upper bounds and matrix-rank-based hardness results.

  • Motivation: Persistent homology offers interpretable multiscale summaries, but persistence computations remain a major scalability obstacle.The computational bottleneck has motivated proxy filtrations, approximation, probabilistic algorithms, and restricted settings.
  • Research questions: The paper asks whether VR and Čech barcodes admit subquadratic approximations under bounded doubling dimension and diameter.It also asks whether stable invariants of multifiltrations can be approximated efficiently.
  • Upper bounds: Bounded doubling dimension and diameter yield deterministic linear-time additive ε-approximations for any stable barcode.The algorithms use greedy permutations to build hierarchical nets and their running time depends on the doubling dimension.
  • Upper bounds: Uniform subsampling gives constant-time probabilistic ε-approximations for normalized measure bifiltrations, including multicover and subdivision-Rips filtrations.The approach adapts classical statistical convergence results to multiparameter persistence.
  • Lower bounds: Matrix rank reduces to sufficiently accurate additive or constant-factor multiplicative approximation of VR or Čech barcodes.The multiplicative hardness result persists even when the doubling dimension is small.
  • Conclusion: The results identify low doubling-dimension growth as exploitable, while logarithmic growth makes subquadratic approximation unlikely.The paper concludes that stability alone is insufficient for efficient approximation.

2 Preliminaries

The preliminaries define the metric, filtration, persistence, stability, and measure-bifiltration concepts used to analyze Vietoris–Rips, Čech, and subdivision-Rips constructions.

  • Metric geometry: The doubling dimension is the smallest δ such that every radius-r ball is coverable by floor(2^δ) balls of radius r/2.The diameter records the largest scale of the metric space.
  • One-parameter persistence: The Vietoris–Rips complex includes simplices whose vertex sets have diameter at most 2t.Varying t produces a filtration, and homology yields a one-parameter persistence module.
  • One-parameter persistence: The Čech complex replaces the diameter condition with the requirement that the corresponding balls intersect in the ambient space.For Euclidean data, the ambient space is usually R^d with its Euclidean metric.
  • Stability: An ε-interleaving compares persistence modules through natural transformations shifted by ε, and the interleaving distance is the infimum of such ε.The same framework extends to filtered topological spaces and multifiltrations.
  • Stability: Hausdorff and Gromov–Hausdorff distances measure metric-space proximity, with Hausdorff stability transferring proximity to VR and Čech filtrations.For compact spaces, d_GH(X,Y) ≤ ε implies VR interleaving distance at most ε; the Čech analogue uses Hausdorff distance.
  • Multiparameter persistence: The measure bifiltration is defined for probability measures, while normalized multicover and subdivision-Rips bifiltrations arise as related constructions.Finite metric spaces correspond to uniform probability measures, making measure-based constructions applicable to them.
  • Multiparameter persistence: The subdivision-Rips bifiltration is built from chains of nested simplices, and its full complex at level 1 is the barycentric subdivision.For finite X, the number of j-simplices is Θ((j + 2)|X|).

3 Approximations from small doubling dimension

The paper develops approximation schemes for stable invariants using metric-space sampling and controlled doubling dimension. Greedy permutations yield linear-time one-parameter approximations, while random sampling yields constant-in-n probabilistic approximations for selected multiparameter filtrations.

  • Bounded diameter is essential for fixing the relative scale of additive approximation error in the considered metric spaces.
  • 3.1 Revisiting greedy permutations: Greedy permutations approximate an n-point metric space in Gromov–Hausdorff distance, producing barcode guarantees on a sparse sample and culminating in a linear-time algorithm.The approach uses covering and packing properties of the permutation together with decay bounds for the m-center radius.
  • 3.1 Revisiting greedy permutations: For ϕ(n) = o(log n), every Hausdorff continuous algorithm admits an ε-approximation on FinMetϕ with a running time determined by f and ψ(4/ε).For bounded doubling dimension and f(n) = n^q, the resulting dependence is expressed through ψ(y) = y^c.
  • 3.1 Revisiting greedy permutations: For Vietoris–Rips barcodes in fixed homological dimension, bounded diameter and bounded doubling dimension imply ε-approximation algorithms with the runtime stated in Corollary 27.
  • 3.2 Random Subsampling: Uniform empirical measures provide the convergence bounds underlying randomized approximation schemes for measure and subdivision-Rips bifiltrations.Theorem 36 gives a randomized ε-approximation for Prokhorov continuous algorithms on FinMetϕ, with success probability 1 − p.
  • 3.2 Random Subsampling: For subdivision-Rips bifiltrations, fixed-dimensional homology admits a randomized additive ε-approximation whose runtime is constant in |X| for fixed success probability.The general finite-metric-space scheme has high exponential dependence on ε^-1 and p^-1 because the filtration can contain Θ((j + 2)|X|) j-dimensional simplices.

4 When are approximations hard?

The paper establishes hardness results for approximating Vietoris–Rips and Čech barcodes by reducing matrix-rank computation to barcode approximation. The reductions cover sufficiently small additive errors and arbitrary constant-factor multiplicative approximations, including low-dimensional embeddings.

  • The reductions target both additive and constant-factor multiplicative barcode approximations for Vietoris–Rips and Čech filtrations.They extend earlier reductions from matrix rank to Betti-number computation.
  • Additive approximations: The additive reduction constructs a geometric embedding of an EP-complex whose persistent homology recovers the matrix-dependent second Betti number.A dense sampled subset preserves the relevant homology, while a neighborhood deformation retraction connects the embedded complex to its filtration.
  • Additive approximations: Matrix rank reduces to sufficiently accurate additive barcode approximation with the same O(m^q) running time.For finite metric spaces with constant-time distance oracles and diameter at most 1, an O(|X|^q)-time approximator yields an O(m^q)-time rank algorithm.
  • Scope of the reduction: The additive theorem requires sufficiently small ε; a crude lower bound for the admissible value is 0.0005.This threshold is stated as a rough bound for the theorem’s ε condition.
  • Multiplicative approximations: For any α ≥ 1, an O(n^q)-time α-approximation in Euclidean R^(2d+3) gives matrix-rank computation in O(m^(q(1+3/d))) time, ignoring factors depending only on α or d.The result also extends to q = 1 with an additional log m factor.
  • Geometric construction: The construction samples O(m/s^2) points, supports a constant-time distance oracle, and has a diameter bound independent of the matrix.These properties make the embedded reduction compatible with barcode approximation algorithms.

5 On the hardness of multiplicative approximations

The section proves hardness for multiplicative barcode approximations by embedding matrix-rank instances into Euclidean EP-complexes and extracting rank from sampled VR or Čech barcodes.

  • The best known compressed-filtration approach still yields ˜O(|X|^ω) time for constant-factor approximation, while improvement is unlikely for sufficiently large doubling dimension.The bound ignores ε-dependent factors; the hardness result applies in the large-doubling-dimension regime.
  • A multiplicative approximation running in O(n^q) yields a matrix-rank algorithm running in O(mq(1+3/d)), ignoring factors depending only on α or d.The reduction uses a sample of size O(m1+3/dα8), and the barcode intervals determine rank M.
  • The same reasoning adapts to multiplicative approximations of Čech barcodes.
  • The reduction embeds an EP-complex encoding a matrix into R2d+3 and recovers rank from the barcode of a subsample of its surface.The construction uses circles for columns and connected row structures for nonzero entries.
  • A separated point set on the unit sphere and a grid path connect row-associated circles while controlling the embedding and sample size.The sphere points have minimum distance at least C · m−1/d, and the grid path visits selected vertices with bounded travel between them.
  • The construction admits a neighborhood deformation retraction only up to tm = Cm−1/d, which depends on the matrix’s number of nonzero entries.Unlike the additive construction, the homology is not guaranteed to persist for a time independent of M.

6 Discussion

The discussion frames the paper’s upper and lower bounds as complementary complexity results, while identifying open questions about practical performance, other filtrations, and partial barcode approximation.

  • The paper establishes upper bounds for additive invariant approximations and reduces matrix rank to VR or Čech barcode approximation for lower bounds.
  • In the multiparameter setting, measure-bifiltration invariants on bounded-diameter doubling spaces can be probabilistically analyzed from samples independent of input size.
  • The one-parameter results separate regimes where multiplicative approximations are feasible from regimes where additive approximations become easier to compute.
  • The lower bounds show that multiplicative approximations are generally expensive, while sufficiently exact additive approximations become expensive without doubling-dimension control.
  • Open questions concern practical gains over state-of-the-art implementations, more efficient filtrations, other multifiltrations, and partial approximation of long barcode intervals.

7 Hardness of approximating barcodes—missing proofs for generalities for both cases

The proofs establish homological equivalences between Čech and Vietoris–Rips constructions using deformation retractions, natural maps, subdivision, and linear homotopies.

  • A neighborhood deformation retraction from Xt0 onto an embedded metric space X supplies the geometric basis for maps from Čech complexes to X.
  • The induced maps are natural under inclusions of Čech complexes, and their homology isomorphism follows by subdividing cycles into sufficiently small simplices.
  • Under natural homology-equivalence maps from Čech complexes to X, the inclusion between Čech and Vietoris–Rips complexes induces homology isomorphisms for the relevant scales.
  • The proof uses barycentric subdivision to place simplices inside small balls, then transfers the resulting subdivisions between Čech and Vietoris–Rips chain complexes.
  • The t-normal bundle consists of normal vectors of norm at most t, while nearest-neighbor retraction moves each point linearly to its unique nearest point in A.
  • For manifolds with boundary, tangent spaces are defined through differentiable extensions, and t-neighborhoods combine normal neighborhoods with boundary neighborhoods.

8 Missing proofs for reductions from matrix rank

The reduction constructs embedded complexes with controlled geometry, enabling deformation retractions, efficient sampling, and distance queries needed to transfer matrix-rank information to filtration barcodes.

  • Deformation retractions: A parameter t0 independent of M gives a t0-neighborhood deformation retraction Kt0 → K for the embedded EP-complex.The proof combines partial retractions with a continuous nearest-neighbor deformation retraction.
  • Local geometric control: For 0 < t0 < r0, canonical maps from neighborhoods of triple junctions, L-arms, and caps are injective.This supports unique nearest-neighbor constructions on individual components.
  • Local geometric control: Normal bundles remain separated because triple junctions, L-arms, and caps have controlled pairwise distances and compatible intersections at shared boundaries.The relevant bounds are r0/2 for several component pairs and r0 for triple-junction attachments.
  • Efficient discretization: A subset S of O(m/s2) points with dH(S, K) ≤ s can be found in O(m/s2) time, while K has a constant-time distance oracle and M-independent diameter.These properties make the geometric reduction computationally manageable.
  • Efficient discretization: The construction can be rescaled to diameter at most 1, using the bound that points of K have at most 8 nonzero coordinates, each bounded by 11r0.The stated rescaling factor is 1/√88r0.
  • Multiplicative hardness construction: For tm = Cm^-1/d, the EP-complex admits a tm-neighborhood deformation retraction, and a finite point set can be computed in O(m1+3/d log(m)α8) time.The point set has size O(m1+3/dα8) and uses an ambient-Euclidean constant-time distance oracle.
Loading 2608.27269v1…