Stability and Minimax Optimality of Tangential Delaunay Complexes for Manifold Reconstruction
Tóm tắt
We consider the problem of optimality in manifold reconstruction. A random sample $$\mathbb {X}_n = \{X_1,\ldots ,X_n\}\subset \mathbb {R}^D$$ composed of points close to a d-dimensional submanifold M, with or without outliers drawn in the ambient space, is observed. Based on the tangential Delaunay complex (Discrete Comput Geom 51(1):221–267 2014), we construct an estimator $$\widehat{M}$$ that is ambient isotopic and Hausdorff-close to M with high probability. The estimator $$\widehat{M}$$ is built from existing algorithms. In a model with additive noise of small amplitude, we show that this estimator is asymptotically minimax optimal for the Hausdorff distance over a class of submanifolds satisfying a reach constraint. Therefore, even with no a priori information on the tangent spaces of M, our estimator based on Tangential Delaunay Complexes is optimal. This shows that the optimal rate of convergence can be achieved through existing algorithms. A similar result is also derived in a model with outliers. A geometric interpolation result is derived, showing that the Tangential Delaunay Complex is stable with respect to noise and perturbations of the tangent spaces. In the process, a decluttering procedure and a tangent space estimator both based on local principal component analysis (PCA) are studied.
Tài liệu tham khảo
citation_journal_title=Geom. Dedicata; citation_title=Gauss equation and injectivity radii for subspaces in spaces of curvature bounded above; citation_author=SB Alexander, RL Bishop; citation_volume=117; citation_publication_date=2006; citation_pages=65-84; citation_doi=10.1007/s10711-005-9011-6; citation_id=CR1
citation_journal_title=J. Mach. Learn. Res.; citation_title=Spectral clustering based on local PCA; citation_author=E Arias-Castro, G Lerman, T Zhang; citation_volume=18; citation_issue=9; citation_publication_date=2017; citation_pages=1-57; citation_id=CR2
citation_journal_title=Ann. Stat.; citation_title=Community detection in dense random networks; citation_author=E Arias-Castro, N Verzelen; citation_volume=42; citation_issue=3; citation_publication_date=2014; citation_pages=940-969; citation_doi=10.1214/14-AOS1208; citation_id=CR3
citation_journal_title=Discrete Comput. Geom.; citation_title=Manifold reconstruction using tangential Delaunay complexes; citation_author=J-D Boissonnat, A Ghosh; citation_volume=51; citation_issue=1; citation_publication_date=2014; citation_pages=221-267; citation_doi=10.1007/s00454-013-9557-2; citation_id=CR4
citation_journal_title=Discrete Comput. Geom.; citation_title=Manifold reconstruction in arbitrary dimensions using witness complexes; citation_author=J-D Boissonnat, LJ Guibas, SY Oudot; citation_volume=42; citation_issue=1; citation_publication_date=2009; citation_pages=37-70; citation_doi=10.1007/s00454-009-9175-1; citation_id=CR5
citation_journal_title=ESAIM Probab. Stat.; citation_title=Theory of classification: a survey of some recent advances; citation_author=S Boucheron, O Bousquet, G Lugosi; citation_volume=9; citation_publication_date=2005; citation_pages=323-375; citation_doi=10.1051/ps:2005018; citation_id=CR6
citation_title=Concentration Inequalities: A Nonasymptotic Theory of Independence; citation_publication_date=2013; citation_id=CR7; citation_author=S Boucheron; citation_author=G Lugosi; citation_author=P Massart; citation_publisher=Oxford University Press
citation_journal_title=C. R. Math. Acad. Sci. Paris; citation_title=A Bennett concentration inequality and its application to suprema of empirical processes; citation_author=O Bousquet; citation_volume=334; citation_issue=6; citation_publication_date=2002; citation_pages=495-500; citation_doi=10.1016/S1631-073X(02)02292-6; citation_id=CR8
Buchet, M., Dey, T.K., Wang, J., Wang, Y.: Declutter and resample: towards parameter free denoising. In: Aronov, B., Katz, M.J. (eds.) The 33rd International Symposium on Computational Geometry (SoCG’17). LIPIcs. Leibniz Int. Proc. Inform., vol. 77, Art. No. 23. Schloss Dagstuhl Leibniz-Zentrum für Informatik, Wadern (2017)
do Carmo, M.P.: Riemannian Geometry. Mathematics: Theory & Applications. Birkhäuser, Boston, MA (1992)
Chazal, F., Cohen-Steiner, D., Lieutier, A.: A sampling theory for compact sets in Euclidean space. In: Proceedings of the 22nd Annual Symposium on Computational Geometry (SCG’06), pp. 319–326. ACM, New York (2006)
citation_journal_title=J. Mach. Learn. Res.; citation_title=Convergence rates for persistence diagram estimation in topological data analysis; citation_author=F Chazal, M Glisse, C Labruère, B Michel; citation_volume=16; citation_publication_date=2015; citation_pages=3603-3635; citation_id=CR12
Cheng, S.-W., Dey, T.K., Ramos, E.A.: Manifold reconstruction from point samples. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’05), pp. 1018–1027. ACM, New York (2005)
Clarkson, K.L.: Building triangulations using
$$\varepsilon $$
-nets. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC’06), pp. 326–335. ACM, New York (2006)
citation_journal_title=Adv. Appl. Probab.; citation_title=On boundary estimation; citation_author=A Cuevas, A Rodríguez-Casal; citation_volume=36; citation_issue=2; citation_publication_date=2004; citation_pages=340-354; citation_doi=10.1239/aap/1086957575; citation_id=CR15
citation_journal_title=III. SIAM J. Numer. Anal.; citation_title=The rotation of eigenvectors by a perturbation; citation_author=C Davis, WM Kahan; citation_volume=7; citation_publication_date=1970; citation_pages=1-46; citation_doi=10.1137/0707001; citation_id=CR16
citation_journal_title=NoDEA Nonlinear Differ. Equ. Appl.; citation_title=Global inversion of functions: an introduction; citation_author=G Marco, G Gorni, G Zampieri; citation_volume=1; citation_issue=3; citation_publication_date=1994; citation_pages=229-248; citation_doi=10.1007/BF01197748; citation_id=CR17
Dey, T.L.: Curve and surface reconstruction: algorithms with mathematical analysis. Cambridge Monographs on Applied and Computational Mathematics, vol. 23. Cambridge University Press, Cambridge (2007)
citation_journal_title=IEEE Trans. Inform. Theory; citation_title=De-noising by soft-thresholding; citation_author=DL Donoho; citation_volume=41; citation_issue=3; citation_publication_date=1995; citation_pages=613-627; citation_doi=10.1109/18.382009; citation_id=CR19
citation_journal_title=Adv. Appl. Probab.; citation_title=Rates of convergence for random approximations of convex sets; citation_author=L Dümbgen, G Walther; citation_volume=28; citation_issue=2; citation_publication_date=1996; citation_pages=384-393; citation_doi=10.2307/1428063; citation_id=CR20
Dyer, R., Vegter, G., Wintraecken, M.: Riemannian simplices and triangulations. In: Arge, L., Pach, J. (eds.) The 31st International Symposium on Computational Geometry (SoCG’15). LIPIcs. Leibniz Int. Proc. Inform. (LIPIcs), vol. 34, pp. 255–269. Schloss Dagstuhl Leibniz-Zentrum für Informatik, Wadern (2015)
citation_journal_title=Trans. Am. Math. Soc.; citation_title=Curvature measures; citation_author=H Federer; citation_volume=93; citation_issue=3; citation_publication_date=1959; citation_pages=418-491; citation_doi=10.1090/S0002-9947-1959-0110078-1; citation_id=CR22
Federer, H.: Geometric Measure Theory. Die Grundlehren der Mathematischen Wissenschaften, vol. 153. Springer, New York (1969)
citation_journal_title=Ann. Stat.; citation_title=Manifold estimation and singular deconvolution under Hausdorff loss; citation_author=CR Genovese, M Perone-Pacifico, I Verdinelli, L Wasserman; citation_volume=40; citation_issue=2; citation_publication_date=2012; citation_pages=941-963; citation_doi=10.1214/12-AOS994; citation_id=CR24
citation_journal_title=J. Mach. Learn. Res.; citation_title=Minimax manifold estimation; citation_author=CR Genovese, M Perone-Pacifico, I Verdinelli, L Wasserman; citation_volume=13; citation_publication_date=2012; citation_pages=1263-1291; citation_id=CR25
citation_journal_title=Electron. J. Stat.; citation_title=Tight minimax rates for manifold estimation under Hausdorff loss; citation_author=AKH Kim, HH Zhou; citation_volume=9; citation_issue=1; citation_publication_date=2015; citation_pages=1562-1582; citation_doi=10.1214/15-EJS1039; citation_id=CR26
citation_journal_title=Ann. Stat.; citation_title=Convergence of estimates under dimensionality restrictions; citation_author=L LeCam; citation_volume=1; citation_issue=1; citation_publication_date=1973; citation_pages=38-53; citation_doi=10.1214/aos/1193342380; citation_id=CR27
citation_journal_title=J. Mach. Learn. Res.; citation_title=Multiscale dictionary learning: non-asymptotic bounds and robustness; citation_author=M Maggioni, S Minsker, N Strawn; citation_volume=17; citation_publication_date=2016; citation_pages=1-51; citation_id=CR28
citation_journal_title=Ann. Stat.; citation_title=Asymptotical minimax recovery of sets with smooth boundaries; citation_author=E Mammen, AB Tsybakov; citation_volume=23; citation_issue=2; citation_publication_date=1995; citation_pages=502-524; citation_doi=10.1214/aos/1176324533; citation_id=CR29
citation_journal_title=Discrete Comput. Geom.; citation_title=Finding the homology of submanifolds with high confidence from random samples; citation_author=P Niyogi, S Smale, S Weinberger; citation_volume=39; citation_issue=1–3; citation_publication_date=2008; citation_pages=419-441; citation_doi=10.1007/s00454-008-9053-2; citation_id=CR30
citation_journal_title=Pattern Recognit. Lett.; citation_title=Fast principal component analysis using fixed-point algorithm; citation_author=A Sharma, KK Paliwal; citation_volume=28; citation_issue=10; citation_publication_date=2007; citation_pages=1151-1155; citation_doi=10.1016/j.patrec.2007.01.012; citation_id=CR31