Adaptive and optimal sampling parameters for certified homology recovery of submanifolds: the deferred parameter theory of Niyogi–Smale–Weinberger (2008)

The 2008 Niyogi–Smale–Weinberger theorem showed that the homology of a compact submanifold $M\subset\mathbb{R}^N$ with condition number $1/\tau$ can be recovered with prescribed confidence $1-\delta$ from $n$ i.i.d. uniform samples by computing the nerve of a union of equal-radius $\epsilon$-balls for any $0<\epsilon<\tau/2$, and extended this to samples from distributions supported near $M$. The paper explicitly deferred three linked parts of the parameter theory: (a) a version of the main probabilistic theorem with point-dependent radii $\epsilon_x=c\,\sigma(x)$ scaled by the local feature size $\sigma$ — the deterministic deformation-retract statement was promised for a later paper and is now available in later literature, but the authors called the probabilistic version 'not obvious'; (b) the complete characterization and optimization of the feasible region of sampling density $s$ and radius $\epsilon$ at fixed noise level $r$ and condition $\tau$, beyond the special cases they worked out; and (c) the joint analysis of statistical sample complexity versus combinatorial complexity of the resulting simplicial complex, which depends on both $s$ and $\epsilon$. Later work established only the deterministic local-feature-size statement (Chazal–Lieutier 2008 and the subsequent mu-reach sampling theory) and built neighboring frameworks — minimax rates, linear-size sparsification, adaptive metrics, density-scaled filtrations, random Čech thresholds — while the precise open core remains: a high-confidence probabilistic homology theorem with local-feature-size-adaptive radii and sample complexity, the completed noisy feasible-region description and its optimization, and the certified statistical–computational complexity tradeoff.

Background

High-dimensional data sets often concentrate near low-dimensional geometric structure. In the manifold-learning setting one assumes that data points $x_1,\dots,x_n$ are drawn independently from a probability distribution supported on (or near) an unknown compact submanifold $M$ of a Euclidean space $\mathbb{R}^N$ — a smooth $k$-dimensional surface-like object of any dimension $k$ and codimension $N-k$, without self-intersections. A basic topological summary of $M$ is its homology: the homology groups $H_0(M),H_1(M),\dots$ are algebraic invariants whose ranks, the Betti numbers, count connected components ($b_0$), independent one-dimensional loops ($b_1$), two-dimensional voids ($b_2$), and so on; the largest degree with nonzero homology recovers the dimension of $M$.

Niyogi, Smale, and Weinberger (2008) — henceforth NSW — asked when the homology of $M$ can be 'learned' from random samples with a high-confidence guarantee, in the style of statistical learning theory. Their framework has two ingredients. First, geometry: $M$ is assumed to have condition number $1/\tau$, where $\tau$ is the reach — the largest radius for which the tubular neighborhood of $M$ (the set of ambient points at distance less than that radius from $M$) embeds without folding in $\mathbb{R}^N$; equivalently, $\tau$ is the distance from $M$ to its medial axis, the closure of the set of ambient points having two or more nearest points on $M$. The reach simultaneously bounds the curvature of $M$ and the separation of its distant sheets. The local feature size $\sigma(x)$ of Amenta–Bern surface-reconstruction theory refines this: $\sigma(x)$ is the distance from $x$ to the medial axis, so $\tau=\inf_{x\in M}\sigma(x)$, and the geometry of $M$ can be far better than the worst case at most points. Second, topology of offsets: for a finite sample $\bar x\subset M$, let $U=\bigcup_{x\in\bar x}B_\epsilon(x)$ be the union of ambient balls of radius $\epsilon$ centered at the sample points. Proposition 3.1 of the paper shows that if $\bar x$ is $(\epsilon/2)$-dense in $M$ (every point of $M$ within $\epsilon/2$ of some sample point) and $\epsilon<\tfrac{3}{5}\tau$, then $U$ deformation retracts onto $M$ — a continuous shrinking of $U$ onto $M$ preserving all homotopy invariants — so $U$ has exactly the homology of $M$. Since intersecting balls are convex, the nerve lemma applies: the Čech complex (the abstract simplicial complex with one simplex for each subset of sample points whose $\epsilon$-balls have a common intersection, a finite combinatorial object) has the same homology as $U$, computable by linear algebra.

The main probabilistic theorem (Theorem 3.1 of the paper) draws the samples i.i.d. from the uniform distribution on $M$ and proves: for any $0<\epsilon<\tau/2$, with probability at least $1-\delta$ the union $U$ has the homology of $M$ as soon as $n>\beta_1(\log\beta_2+\log(1/\delta))$, where $\beta_1,\beta_2$ are explicit in the volume of $M$, the dimension $k$, and $\epsilon,\tau$ (of the order of a covering number of $M$ at scale $\epsilon$). The choices of density and radius are sufficient but were explicitly not claimed optimal.

The paper also treats noise. In its Section 7 model, the sampling measure $\mu$ is supported in the $r$-tubular neighborhood of $M$ and puts not-too-small mass on every ball of each radius $s<r$ centered at a point of $M$. For $s$-dense samples in this model the union of $\epsilon$-balls is homotopy equivalent to $M$ for suitable $(s,\epsilon,r,\tau)$; the authors pose the general question 'what is the feasible space $(s,\epsilon,r,\tau)$ that will guarantee that $U$ is homotopy equivalent to $M$', derive a system of quadratic sufficient conditions (equations (9)–(11)) relating the four parameters, and work out only two special cases: $s=r$ (recovering their earlier inequality (6)) and $r=0$ (recovering a noise-free feasible-region inequality (13), whose sub-case $s=\epsilon/2$ gives $\epsilon<0.96\tau$). They note that the sub-case $s=\epsilon/2$ is 'a choice we made... without any attention to optimality'.

Three issues were left open. First, in a remark after Theorem 3.1 the authors state a local-feature-size version of the deterministic proposition — a union of balls with point-dependent radii $\epsilon_x=c\,\sigma(x)$ deformation-retracts to $M$ when the sample is $(\epsilon_x/2)$-dense and $c<0.21$ (Amenta, Choi, Dey, and Leekha had proved the analogous statement for surfaces in $\mathbb{R}^3$ with $c<0.06$) — which they promised 'in a later paper'; but they add that it is 'not obvious... how to obtain a version of our main theorem in terms of the local feature size', that is, a probabilistic sample-complexity theorem with such adaptive radii. Second, the noisy feasible region was characterized only through special cases: the elimination of the auxiliary variables from equations (9)–(11) into an explicit inequality relating $s,\epsilon,\tau,r$, the shape of the feasible set, and the sample-efficiency-maximizing choice of the density $s$ (their Remark 2) were not carried out. Third, their Remark 3 observes that the total computational complexity of finding homology depends on both the sample size and $\epsilon$ — since $\epsilon$ controls how many balls intersect and hence how many simplices the Čech complex contains — deferring this 'more nuanced complexity analysis', the tradeoff between statistical efficiency and combinatorial complexity, to future consideration.

Later literature transformed the surrounding landscape. The promised deterministic local-feature-size statement was established (not by the authors, whose only follow-up in this direction is a 2011 paper on a different, Gaussian noise model): Chazal and Lieutier (2008) proved reconstruction guarantees for noisy and non-uniform approximations of a manifold using unions of balls whose radii vary with the local level of detail, for submanifolds of arbitrary codimension; Chazal, Cohen-Steiner, and Lieutier (2009) developed a parameterized feature-size (mu-reach) sampling theory for noisy samplings of general compact sets; Attali, Lieutier, and Salinas (2013) gave parameterized sampling conditions under which Čech and Vietoris–Rips complexes of a sample are topologically correct; the theory is consolidated in the monograph of Boissonnat, Chazal, and Yvinec (2018). On the statistical side, Balakrishnan, Rinaldo, Sheehy, Singh, and Wasserman (2012) proved minimax upper and lower bounds for homology inference from noisy samples. On the combinatorial side, Sheehy (2013) constructed $O(n)$-size sparse filtrations approximating Vietoris–Rips persistence diagrams, and Dey, Dong, and Wang (2017) sparsified samples adaptively to the local feature size. Cavanna and Sheehy (2020) related local-feature-size-adaptive samples to uniform samples in a modified path-based metric; Hickok (2021) introduced density-scaled Čech and Vietoris–Rips filtrations with probabilistic guarantees for non-uniform sampling densities; Bobrowski and Weinberger (2016) determined the sharp-threshold behavior of random Čech complexes; further extensions treat ellipsoidal offsets (Kališnik and Lešnik, 2023), manifolds with boundary (Wang and Wang, 2018), local-reach-based sampling of algebraic varieties (Di Rocco, Eklund, and Gäfvert, 2022), variable-bandwidth random Čech complexes (de Kergorlay, 2019), and submanifolds of Riemannian ambient spaces (Mirzaie, 2025). None of these supplies a high-confidence probabilistic homology theorem with local-feature-size-adaptive radii, a completed noisy feasible-region analysis, or a certified joint statistical–computational tradeoff.

Problem Statement

Let $M\subset\mathbb{R}^N$ be a compact $k$-dimensional submanifold with condition number $1/\tau$ (reach $\tau$), and let $\sigma(x)$ denote its local feature size, so $\tau=\inf_{x\in M}\sigma(x)$. Below, $r$ denotes the noise tubular radius of the noisy model and $c\in(0,0.21)$ the dimensionless local-feature-size radius ratio of part (a). The Niyogi–Smale–Weinberger framework computes the homology of $M$ with probability at least $1-\delta$ from $n$ i.i.d. samples by forming the union of $\epsilon$-balls and its Čech complex, with sufficient — explicitly non-optimal — choices $0<\epsilon<\tau/2$, $(\epsilon/2)$-density, and $n>\beta_1(\log\beta_2+\log(1/\delta))$ with $\beta_1,\beta_2$ explicit in $\mathrm{vol}(M),k,\epsilon,\tau$; in the noisy model the sampling measure is supported in the $r$-tubular neighborhood of $M$ with lower mass bounds $\mu(B_s(p))\ge k_s$ on the balls $B_s(p)$ of each radius $0<s<r$ centered at points of $M$. Resolve the deferred parameter theory of this framework, in three linked components that together answer one question — what are the right (adaptive, optimal, computationally efficient) sampling parameters for certified homology recovery:

(a) Adaptive (local) version of the probabilistic theorem. Prove, or disprove, a version of the main probabilistic theorem with point-dependent radii $\epsilon_x=c\,\sigma(x)$ ($0<c<0.21$): give conditions on an i.i.d. sample (uniform or an explicitly specified non-uniform measure) under which $\bigcup_{x\in\bar x}B_{\epsilon_x}(x)$ or its nerve has the homology of $M$ with probability at least $1-\delta$, together with an explicit sample-complexity bound expressed through the function $\sigma$ rather than only through the global $\tau$, reducing to the Niyogi–Smale–Weinberger bound when $\sigma$ is constant. The deterministic deformation-retract statement for such variable-radius unions is already established (Chazal–Lieutier 2008 and subsequent sampling theory), so the open part is precisely the probabilistic sample-complexity statement whose obtention the authors described as not obvious.

(b) Noisy feasible region. Under the Niyogi–Smale–Weinberger noise model, complete the characterization of the feasible set of (density $s$, radius $\epsilon$) for each externally fixed $(\tau,r)$: carry out the elimination of the auxiliary variables from the sufficient equations (9)–(11) of the source paper into an explicit inequality relating $s,\epsilon,\tau,r$; characterize the boundary and shape of the feasible region; and determine the choice of $s$ that maximizes sample efficiency (minimizes the number of samples required for certified homology recovery), as the authors' Remark 2 indicates is necessary. The completed characterization must reproduce the source's verified special cases ($s=r$ recovering inequality (6); $r=0$ recovering inequality (13), whose $s=\epsilon/2$ sub-case gives $\epsilon<0.96\tau$).

(c) Joint complexity tradeoff. Determine how the total computational cost of certified homology recovery — the number of samples drawn together with the combinatorial work in the Čech complex, which depends on both $s$ and $\epsilon$ because $\epsilon$ controls how many balls intersect and hence how many simplices must be formed and tested — scales with the confidence, conditioning, and noise parameters; and characterize the optimal choice of $s$ and $\epsilon$ (or point-dependent $\epsilon_x$) that minimizes the total certified cost at confidence $1-\delta$, including whether the constants in the source theorems can be improved, and establish matching lower bounds (over worst-case manifolds and sampling families) for the claimed optimality.

These components are one coherent objective — the adaptive, noise-aware, complexity-optimal parameter theory of certified homology recovery — viewed along its adaptivity axis (a), its noise axis (b), and its complexity axis (c).

References

1. Partha Niyogi, Stephen Smale, Shmuel Weinberger. Finding the Homology of Submanifolds with High Confidence from Random Samples. Discrete & Computational Geometry 39:419–441 (2008). DOI: 10.1007/s00454-008-9053-2. https://doi.org/10.1007/s00454-008-9053-2
2. Nina Amenta, Marshall Bern. Surface Reconstruction by Voronoi Filtering. Discrete & Computational Geometry 22:481–504 (1999). DOI: 10.1007/PL00009475. https://doi.org/10.1007/pl00009475
3. Nina Amenta, Sunghee Choi, Tamal K. Dey, Naveen Leekha. A simple algorithm for homeomorphic surface reconstruction. International Journal of Computational Geometry & Applications 12(1–2):125–141 (2002). DOI: 10.1142/S0218195902000773. https://doi.org/10.1142/S0218195902000773
4. Frédéric Chazal, André Lieutier. Smooth manifold reconstruction from noisy and non-uniform approximation with guarantees. Computational Geometry 40(2):156–170 (2008). DOI: 10.1016/j.comgeo.2007.07.001. https://doi.org/10.1016/j.comgeo.2007.07.001
5. Frédéric Chazal, David Cohen-Steiner, André Lieutier. A Sampling Theory for Compact Sets in Euclidean Space. Discrete & Computational Geometry 41:461–479 (2009). DOI: 10.1007/s00454-009-9144-8. https://doi.org/10.1007/s00454-009-9144-8
6. Dominique Attali, André Lieutier, David Salinas. Vietoris–Rips complexes also provide topologically correct reconstructions of sampled shapes. Computational Geometry 46(4):448–465 (2013). DOI: 10.1016/j.comgeo.2012.02.009. https://doi.org/10.1016/j.comgeo.2012.02.009
7. Jean-Daniel Boissonnat, Frédéric Chazal, Mariette Yvinec. Geometric and Topological Inference. Cambridge University Press (2018). DOI: 10.1017/9781108297806. https://doi.org/10.1017/9781108297806
8. Partha Niyogi, Stephen Smale, Shmuel Weinberger. A Topological View of Unsupervised Learning from Noisy Data. SIAM Journal on Computing 40(3):646–663 (2011). DOI: 10.1137/090762932. https://doi.org/10.1137/090762932
9. Sivaraman Balakrishnan, Alessandro Rinaldo, Don Sheehy, Aarti Singh, Larry Wasserman. Minimax Rates for Homology Inference. AISTATS 2012; arXiv:1112.5627 (2011). https://arxiv.org/abs/1112.5627
10. Donald R. Sheehy. Linear-Size Approximations to the Vietoris–Rips Filtration. Discrete & Computational Geometry 49:778–796 (2013). DOI: 10.1007/s00454-013-9513-1. https://doi.org/10.1007/s00454-013-9513-1
11. Tamal K. Dey, Zhe Dong, Yusu Wang. Parameter-free Topology Inference and Sparsification for Data on Manifolds. Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pages 2733–2747; arXiv:1505.06462 (2015). DOI: 10.1137/1.9781611974782.181. https://arxiv.org/abs/1505.06462
12. Nicholas J. Cavanna, Donald R. Sheehy. Adaptive Metrics for Adaptive Samples. Algorithms 13(8):200 (2020). DOI: 10.3390/a13080200. https://doi.org/10.3390/a13080200
13. Abigail Hickok. A Family of Density-Scaled Filtered Complexes. arXiv:2112.03334 (2021). https://arxiv.org/abs/2112.03334
14. Sara Kališnik, Davorin Lešnik. Finding the homology of manifolds using ellipsoids. Journal of Applied and Computational Topology 8(1):193–238 (2023). DOI: 10.1007/s41468-023-00145-6. https://doi.org/10.1007/s41468-023-00145-6
15. Yuan Wang, Bei Wang. Topological Inference of Manifolds with Boundary. arXiv:1810.05759 (2018). https://arxiv.org/abs/1810.05759
16. Omer Bobrowski, Shmuel Weinberger. On the vanishing of homology in random Čech complexes. Random Structures & Algorithms 51(1):14–51 (2016). DOI: 10.1002/rsa.20697. https://doi.org/10.1002/rsa.20697
17. Henry-Louis de Kergorlay. Random Čech complexes on R^d: decrackling the noise with local scalings. arXiv:1912.10548 (2019). https://arxiv.org/abs/1912.10548
18. Sandra Di Rocco, David Eklund, Oliver Gäfvert. Sampling and homology via bottlenecks. Mathematics of Computation 91(338):2969–2995 (2022); arXiv:2010.07976 (2020). DOI: 10.1090/mcom/3757. https://arxiv.org/abs/2010.07976
19. Reza Mirzaie. On topology estimation of submanifolds in Riemannian manifolds by random points. arXiv:2512.23225 (2025). https://arxiv.org/abs/2512.23225