jmlr jmlr2012 jmlr2012-68 jmlr2012-68-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Christopher Genovese, Marco Perone-Pacifico, Isabella Verdinelli, Larry Wasserman
Abstract: We find the minimax rate of convergence in Hausdorff distance for estimating a manifold M of dimension d embedded in RD given a noisy sample from the manifold. Under certain conditions, we show that the optimal rate of convergence is n−2/(2+d) . Thus, the minimax rate depends only on the dimension of the manifold, not on the dimension of the space in which M is embedded. Keywords: manifold learning, minimax estimation
R. Baraniuk and M. Wakin. Random projections of smooth manifolds. Foundations of Computational Mathematics, 9:51–77, 2007. M. Birman and M. Solomjak. Piecewise-polynomial approximation of functions of the classes w p . Mathematics of USSR Sbornik, 73:295–317, 1967. J. Boissonnat and A. Ghosh. Manifold reconstruction using tangential delaunay complexes. In Proceedings of the 2010 Annual Symposium on Computational Geometry, pages 324–333. ACM, 2010. F. Chazal and A. Lieutier. Smooth manifold reconstruction from noisy and non-uniform approximation with guarantees. Computational Geometry, 40:156–170, 2008. S. Cheng and T. Dey. Manifold reconstruction from point samples. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1018–1027. SIAM, 2005. 1290 M INIMAX M ANIFOLD E STIMATION A. Cuevas and A. Rodr´guez-Casal. On boundary estimation. Advances in Applied Probability, 36 ı (2):340–354, 2004. L. Devroye and G. Wise. Detection of abnormal behavior via nonparametric estimation of the support. SIAM Journal on Applied Mathematics, 38:480–488, 1980. T. Dey. Curve and Surface Reconstruction: Algorithms with Mathematical Analysis. Cambridge University Press, 2006. T. Dey and S. Goswami. Provable surface reconstruction from noisy samples. In Proceedings of the Twentieth Annual Symposium on Computational Geometry, pages 330–339. ACM, 2004. H. Federer. Curvature measures. Transactions of the American Statistical Society, 93:418–491, 1959. C. Genovese, M. Perone-Pacifico, I. Verdinelli, and L. Wasserman. Nonparametric filament estimation. arXiv:1003.5536, 2010. O. Gonzalez and J. Maddocks. Global curvature, thickness, and the ideal shapes of knots. Proceedings of the National Academy of Sciences, 96(9):4769–4773, 1999. L. LeCam. Convergence of estimates under dimensionality restrictions. The Annals of Statistics, pages 38–53, 1973. J.M. Lee. Introduction to Smooth Manifolds. Springer, 2002. P. Niyogi, S. Smale, and S. Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete and Computational Geometry, 39:419–441, 2006. P. Niyogi, S. Smale, and S. Weinberger. A topological view of unsupervised learning from noisy data. Unpublished technical report, University of Chicago, 2008. X. Shen and W. Wong. Probability inequalities for likelihood ratios and convergence rates of sieve mles. The Annals of Statistics, 23:339–362, 1995. A. Tsybakov. Introduction to Nonparametric Estimation. Springer, 2008. B. Yu. Assouad, Fano, and Le Cam. In Festschrift for Lucien Le Cam. Springer, 1997. 1291