Tight Lower Bounds for Homology Inference
This provides a fundamental theoretical result for researchers in topological data analysis and manifold learning, though it is incremental as it refines prior bounds.
The paper tackles the problem of estimating the homology groups of a manifold from noiseless samples, showing that the upper bound by Niyogi, Smale, and Weinberger is tight, thus establishing rate optimal asymptotic minimax bounds for this statistical inference task.
The homology groups of a manifold are important topological invariants that provide an algebraic summary of the manifold. These groups contain rich topological information, for instance, about the connected components, holes, tunnels and sometimes the dimension of the manifold. In earlier work, we have considered the statistical problem of estimating the homology of a manifold from noiseless samples and from noisy samples under several different noise models. We derived upper and lower bounds on the minimax risk for this problem. In this note we revisit the noiseless case. In previous work we used Le Cam's lemma to establish a lower bound that differed from the upper bound of Niyogi, Smale and Weinberger by a polynomial factor in the condition number. In this note we use a different construction based on the direct analysis of the likelihood ratio test to show that the upper bound of Niyogi, Smale and Weinberger is in fact tight, thus establishing rate optimal asymptotic minimax bounds for the problem. The techniques we use here extend in a straightforward way to the noisy settings considered in our earlier work.