Minimax rates for homology inference

Sivaraman Balakrishnan, Alesandro Rinaldo, Don Sheehy, Aarti Singh, Larry Wasserman
Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, PMLR 22:64-72, 2012.

Abstract

Often, high dimensional data lie close to a low-dimensional submanifold and it is of interest to understand the geometry of these submanifolds. The homology groups of a (sub)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 this paper, we consider the statistical problem of estimating the homology of a manifold from noisy samples under several different noise models. We derive upper and lower bounds on the minimax risk for this problem. Our upper bounds are based on estimators which are constructed from a union of balls of appropriate radius around carefully selected sample points. In each case we establish complementary lower bounds using Le Cam’s lemma.

Cite this Paper

BibTeX
@InProceedings{pmlr-v22-balakrishnan12a, title = {Minimax rates for homology inference}, author = {Balakrishnan, Sivaraman and Rinaldo, Alesandro and Sheehy, Don and Singh, Aarti and Wasserman, Larry}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {64--72}, year = {2012}, editor = {Lawrence, Neil D. and Girolami, Mark}, volume = {22}, series = {Proceedings of Machine Learning Research}, address = {La Palma, Canary Islands}, month = {21--23 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v22/balakrishnan12a/balakrishnan12a.pdf}, url = {https://proceedings.mlr.press/v22/balakrishnan12a.html}, abstract = {Often, high dimensional data lie close to a low-dimensional submanifold and it is of interest to understand the geometry of these submanifolds. The homology groups of a (sub)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 this paper, we consider the statistical problem of estimating the homology of a manifold from noisy samples under several different noise models. We derive upper and lower bounds on the minimax risk for this problem. Our upper bounds are based on estimators which are constructed from a union of balls of appropriate radius around carefully selected sample points. In each case we establish complementary lower bounds using Le Cam’s lemma.} }
Endnote
%0 Conference Paper %T Minimax rates for homology inference %A Sivaraman Balakrishnan %A Alesandro Rinaldo %A Don Sheehy %A Aarti Singh %A Larry Wasserman %B Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2012 %E Neil D. Lawrence %E Mark Girolami %F pmlr-v22-balakrishnan12a %I PMLR %P 64--72 %U https://proceedings.mlr.press/v22/balakrishnan12a.html %V 22 %X Often, high dimensional data lie close to a low-dimensional submanifold and it is of interest to understand the geometry of these submanifolds. The homology groups of a (sub)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 this paper, we consider the statistical problem of estimating the homology of a manifold from noisy samples under several different noise models. We derive upper and lower bounds on the minimax risk for this problem. Our upper bounds are based on estimators which are constructed from a union of balls of appropriate radius around carefully selected sample points. In each case we establish complementary lower bounds using Le Cam’s lemma.
RIS
TY - CPAPER TI - Minimax rates for homology inference AU - Sivaraman Balakrishnan AU - Alesandro Rinaldo AU - Don Sheehy AU - Aarti Singh AU - Larry Wasserman BT - Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-balakrishnan12a PB - PMLR DP - Proceedings of Machine Learning Research VL - 22 SP - 64 EP - 72 L1 - http://proceedings.mlr.press/v22/balakrishnan12a/balakrishnan12a.pdf UR - https://proceedings.mlr.press/v22/balakrishnan12a.html AB - Often, high dimensional data lie close to a low-dimensional submanifold and it is of interest to understand the geometry of these submanifolds. The homology groups of a (sub)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 this paper, we consider the statistical problem of estimating the homology of a manifold from noisy samples under several different noise models. We derive upper and lower bounds on the minimax risk for this problem. Our upper bounds are based on estimators which are constructed from a union of balls of appropriate radius around carefully selected sample points. In each case we establish complementary lower bounds using Le Cam’s lemma. ER -
APA
Balakrishnan, S., Rinaldo, A., Sheehy, D., Singh, A. & Wasserman, L.. (2012). Minimax rates for homology inference. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 22:64-72 Available from https://proceedings.mlr.press/v22/balakrishnan12a.html.

Related Material