Interpolation, the rudimentary geometry of spaces of Lipschitz functions, and geometric complexity. (English) Zbl 1447.57036

Weinberger, Shmuel

Found. Comput. Math. 19, No. 5, 991-1011 (2019).

Summary: We consider seriously the analogy between interpolation of nonlinear functions and manifold learning from samples, and examine the results of transferring ideas from each of these domains to the other. Illustrative examples are given in approximation theory, variational calculus (closed geodesics), and quantitative cobordism theory.

MSC:

57R75	\(\mathrm{O}\)- and \(\mathrm{SO}\)-cobordism
41A10	Approximation by polynomials
55Q05	Homotopy groups, general; sets of homotopy classes
68T05	Learning and adaptive systems in artificial intelligence

Keywords:

interpolation; function space; persistent homology; homotopy; quantitative cobordism; embedding; survey

References:

[1]	Atiyah, M.; Bott, R., A Lefschetz fixed point formula for elliptic complexes: II. Applications, Ann. of Math., 88, 451-491, (1968) · Zbl 0167.21703
[2]	Amenta, N.; Bern, M., Surface reconstruction by voronoi filtering, Discrete Comput. Geom., 22, 481-504, (1999) · Zbl 0939.68138
[3]	Barzdin, Ya. M., On the Realization of Networks in Three-Dimensional Space, 194-202, (1993), Dordrecht
[4]	J. Boissonnat, F. Chazal, and M. Yvinec. Computational geometry and topology for data analysis. To appear. · Zbl 1457.62006
[5]	Boissonnat, J.; Guibas, L.; Oudot, S., Manifold reconstruction in arbitrary dimensions using witness complexes, Discrete Comput. Geom., 42, 37-70, (2009) · Zbl 1194.68245
[6]	Buoncristiano, S.; Hacon, D., An elementary geometric proof of two theorems of Thom, Topology, 20, 97-99, (1981) · Zbl 0456.57011
[7]	Bourgain, J., On Lipschitz embedding of finite metric spaces in Hilbert space, Israel J. Math., 52, 46-52, (1985) · Zbl 0657.46013
[8]	Brown, E., Finite computability of Postnikov complexes, Ann. of Math., 65, 1-20, (1957) · Zbl 0077.16804
[9]	W. Browder. Surgery on simply connected manifolds. Springer Verlag, 1972. · Zbl 0239.57016
[10]	J. Block and S. Weinberger. Large scale homology theories and geometry. In Geometric Topology: 1993 Georgia International Topology Conference, AMS/IP Stud. Adv. Math., pages 522-569, Providence, RI, 1997. Amer. Math. Soc. · Zbl 0898.55006
[11]	Chambers, G.; Dotterer, D.; Manin, F.; Weinberger, S., Quantitative null-cobordism, J. Amer. Math. Soc., 31, 1165-1203, (2018) · Zbl 1402.53035
[12]	S. Cheng, T. Dey, and E. A. Ramos. Manifold reconstruction from point samples. In SODA ’05 Proceedings of the sixtieth annual ACM-SIAM symposium on discrete algorithms, pages 1018-1027, Philadelphia, PA, 2005. Society for Industrial and Applied Mathematics. · Zbl 1297.68235
[13]	Cheeger, Jeff; Gromov, Mikhael, On the Characteristic Numbers of Complete Manifolds of Bounded Curvature and Finite Volume, 115-154, (1985), Berlin, Heidelberg · Zbl 0592.53036
[14]	Cha, J., A topological approach to Cheeger-Gromov universal bounds for von Neumann \(\rho\)-invariants, Comm. Pure and Applied Math., 69, 1154-1209, (2016) · Zbl 1358.57020
[15]	Carlsson, G.; Memoli, F., Classifying clustering schemes, Found. Comput. Math., 13, 221-252, (2013) · Zbl 1358.62057
[16]	Chambers, G.; Manin, F.; Weinberger, S., Quantitative nullhomotopy and rational homotopy type, Geom. Funct. Anal., 28, 563-588, (2018) · Zbl 1408.57023
[17]	Cohen-Steiner, D.; Edelsbrunner, H.; Harer, J., Stability of persistence diagrams, Discrete Comput. Geom., 37, 103-120, (2007) · Zbl 1117.54027
[18]	Carlsson, G.; Zomorodian, A., Computing persistent homology, Discrete Comput. Geom., 33, 249-274, (2005) · Zbl 1069.55003
[19]	F. Cucker and D. Zhou. Learning Theory: An Approximation Theory Viewpoint. Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, 2007. · Zbl 1274.41001
[20]	Dranishnikov, A.; Ferry, S.; Weinberger, S., Large Riemannian manifolds which are flexible, Ann. of Math., 157, 919-938, (2003) · Zbl 1051.53035
[21]	A. Dranishnikov, S. Ferry, and S. Weinberger. An infinite dimensional phenomenon in finite dimensional topology. Preprint, 2017.
[22]	M. DoCarmo. Riemannian Geometry. Birkhäuser Verlag, 1992.
[23]	Edelsbrunner, H.; Grayson, D., Edgewise subdivision of a simplex, Discrete Comput. Geom., 24, 707-719, (2000) · Zbl 0968.51016
[24]	Edelsbrunner, H.; Letscher, D.; Zomorodian, A., Topological persistence and simplification, Discrete Comput. Geom., 28, 511-533, (2002) · Zbl 1011.68152
[25]	Y. Eliashberg and N. Mishachev. Introduction to the h-Principle, volume 48 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2002.
[26]	Fefferman, C., Whitney’s extension problem for \(c^m\), Ann. of Math., 164, 313-359, (2006) · Zbl 1109.58016
[27]	Fefferman, C., \(c^m\)-extension by linear operators, Ann. of Math., 166, 779-835, (2007) · Zbl 1161.46013
[28]	Ferry, S., Topological finiteness theorems for manifolds in Gromov-Hausdorff space, Duke Math. J., 74, 95-106, (1994) · Zbl 0824.53040
[29]	Fefferman, C.; Mitter, S.; Naryanan, H., Testing the manifold hypothesis, J. Amer. Math. Soc., 29, 983-1049, (2016) · Zbl 1359.62122
[30]	Ferry, S.; Weinberger, S., Quantitative algebraic topology and Lipschitz homotopy, Proc. Natl. Acad. Sci. U.S.A., 110, 19246-19250, (2013) · Zbl 1302.57060
[31]	Gromov, M.; Guth, L., Generalizations of the Kolmogorov-Barzdin embedding estimates, Duke Math. J., 161, 2549-2603, (2012) · Zbl 1261.53041
[32]	Gromov, M., Homotopical effects of dilation, J. Diff. Geo., 13, 313-310, (1978) · Zbl 0427.58010
[33]	Gromov, M., Groups of polynomial growth and expanding maps, Publ. Math. IHÉS, 53, 51-78, (1981) · Zbl 0474.20018
[34]	M. Gromov. Partial Differential Relations. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. Springer Verlag, 1986.
[35]	Gromov, M., Dimension, non-linear spectra and width, 132-184, (1988), Berlin, Heidelberg
[36]	M. Gromov. Metric Structures for Riemannian and non-Riemannian Spaces. Modern Birkhäuser Classics. Birkhäuser Verlag, 1999.
[37]	M. Gromov. Quantitative homotopy theory. In H. Rossi, editor, Prospects in Mathematics (Princeton, NJ, 1996), pages 45-49. Amer. Math. Soc., Providence, RI, 1999. · Zbl 0927.57022
[38]	J. Kleinberg. An impossibility theorm for clustering. In S. Becker, K. Obermayer, and S. Thrun, editors, Advances in Neural Information Processing Systems 15 (NIPS 2002), pages 463-470. MIT Press, Cambridge, MA, 2002.
[39]	F. Manin. Plato’s cave and differential forms. Preprint, 2018.
[40]	J. Matousek. Lecture notes on metric embeddings. Preprint, 2013.
[41]	J. Milnor. Morse Theory, volume 51 of Annals of Mathematics Studies. Princeton University Press, Princeton, NJ, 1963.
[42]	Milnor, J., A note on curvature and fundamental group, J. Differ. Geom., 2, 1-7, (1968) · Zbl 0162.25401
[43]	F. Manin and S. Weinberger. The Gromov-Guth embedding theorem. Appendix to [11].
[44]	Nabutovsky, A., Non-recursive functions, knots “with thick ropes” and self-clenching “thick” hyperspheres, Commun. Pure Appl. Math., 48, 1-50, (1995) · Zbl 0845.57023
[45]	A. Nabutovsky. Morse landscapes of Riemannian functionals and related problems. In Proceedings of the International Congress of Mathematicians: Hyderabad, India, pages 862-881, 2010. · Zbl 1230.58010
[46]	Niyogi, P.; Smale, S.; Weinberger, S., Finding the homology of submanifolds with high confidence from random samples, Discrete Comput. Geom., 39, 419-441, (2008) · Zbl 1148.68048
[47]	Nabutovsky, A.; Weinberger, S., Variational problems for Riemannian functionals and arithmetic groups, Publ. Math. IHÉS, 92, 5-62, (2000) · Zbl 1003.58007
[48]	S. Oudot. Persistence Theory: From Quiver Representations to Data Analysis, volume 209 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2015.
[49]	I. Polterovich, L. Polterovich, and V. Stojisavljević. Persistence barcodes and Laplace eigenfunctions on surfaces. Preprint, 2017. · Zbl 1420.58012
[50]	L. Polterovich, D. Rosen, K. Samvelyan, and J. Zhang. Persistent homology for symplectic topologists. Preprint, 2018.
[51]	Robins, V., Toward computing homology from finite approximations, Topology Proceedings, 24, 503-532, (1999) · Zbl 1026.55009
[52]	J. Roe. Index theory, coarse geometry, and topology of manifolds, volume 90 of CMBS Regional Conference Series in Mathematics. American Mathematical Society, Providence, RI, 1996.
[53]	Smale, S., The classification of immersions of spheres in Euclidean spaces, Ann. of Math., 69, 327-344, (1959) · Zbl 0089.18201
[54]	E. Spanier. Algebraic Topology. McGraw-Hill, 1956.
[55]	R. Strong. Notes on cobordism theory. Mathematical Notes. Princeton University Press, Princeton, NJ, 1968.
[56]	Sullivan, D., Infinitesimal computations in topology, Publ. Math. IHÉS, 47, 269-331, (1977) · Zbl 0374.57002
[57]	Thom, R., Quelques propriétés globales des variétés différentiables, Comment. Math. Helv., 28, 17-86, (1954) · Zbl 0057.15502
[58]	J. Traub and A. Werschulz. Complexity and information. Lezioni Lincee. Cambridge University Press, Cambridge, United Kingdom, 1999.
[59]	Valiant, L., A theory of the learnable, Commun. ACM, 27, 1134-1142, (1984) · Zbl 0587.68077
[60]	C. T. C. Wall. Surgery on Compact Manifolds. London Mathematical Society Monographs. Academic Press, Cambridge, MA, 1969.
[61]	S. Weinberger. Computers, Rigidity, and Moduli. Princeton University Press, Princeton, NJ, 2004.
[62]	S. Weinberger. What is... persistent homology. Notices Amer. Math. Soc., 58(1), 2011.
[63]	Y. Yomdin and G. Comte. Tame Geometry with Applications in Smooth Analysis, volume 1834 of Lecture Notes in Mathematics. Springer Verlag Berlin Heidelberg, 2004.