Infinite multidimensional scaling for metric measure spaces

Kroshnin, Alexey; Stepanov, Eugene; Trevisan, Dario

ESAIM: Control, Optimisation and Calculus of Variations, Tome 28 (2022), article no. 58

For a given metric measure space (X, d, μ) we consider finite samples of points, calculate the matrix of distances between them and then reconstruct the points in some finite-dimensional space using the multidimensional scaling (MDS) algorithm with this distance matrix as an input. We show that this procedure gives a natural limit as the number of points in the samples grows to infinity and the density of points approaches the measure μ. This limit can be viewed as “infinite MDS” embedding of the original space, now not anymore into a finite-dimensional space but rather into an infinitedimensional Hilbert space. We further show that this embedding is stable with respect to the natural convergence of metric measure spaces. However, contrary to what is usually believed in applications, we show that in many cases it does not preserve distances, nor is even bi-Lipschitz, but may provide snowflake (Assouad-type) embeddings of the original space to a Hilbert space (this is, for instance, the case of a sphere and a flat torus equipped with their geodesic distances).

Classification : 51F99, 58J50, 47G10, 15A18, 62H25
Keywords: Isometric embedding, Assouad embedding, multidimensional scaling (MDS)

[1] H. Adams, M. Blumstein and L. Kassab, Multidimensional scaling on metric measure spaces. Rocky Mount. J. Math. 50 (2020) 397–413. | MR | Zbl | DOI

[2] L. Ambrosio, N. Gigli and G. Savaré, Gradient Flows: In Metric Spaces and in the Space of Probability Measures. Springer Science & Business Media (2008). | MR | Zbl

[3] L. Ambrosio, S. Honda, J. W. Portegies and D. Tewodrose, Embedding of ${\mathrm{RCD}}^{*}(K,N)$ spaces in $L^2$ via eigenfunctions. J. Funct. Anal. 280 (2021) Paper No. 108968, 72. | MR | Zbl | DOI

[4] L. Ambrosio and P. Tilli, Topics on analysis in metric spaces, volume 25 of Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford (2004). | MR | Zbl

[5] E. Arias-Castro, A. Javanmard and B. Pelletier, Perturbation bounds for procrustes, classical scaling, and trilateration, with applications to manifold learning. J. Mach. Learn. Res. 21 (2020) 15–19. | MR | Zbl

[6] D. Azevedo and V. A. Menegatto, Eigenvalues of dot-product kernels on the sphere. Proc. Ser. Br. Soc. Comput. Appl. Math. 3 (2015).

[7] M. Balasubramanian and E. L. Schwartz, The isomap algorithm and topological stability. Science 295 (2002) 7–7. | DOI

[8] Y. Bengio, O. Delalleau, N. Le Roux, J.-F. Paiement, P. Vincent and M. Ouimet, Learning eigenfunctions links spectral embedding and kernel PCA. Neural Comput. 16 (2004) 2197–2219. | Zbl | DOI

[9] P. Bérard, G. Besson and S. Gallot, Embedding Riemannian manifolds by their heat kernel. Geom. Funct. Anal. 4 (1994) 373–398. | MR | Zbl | DOI

[10] I. Borg and P. J. F. Groenen, Modern multidimensional scaling: Theory and applications. Springer Science & Business Media (2005). | MR | Zbl

[11] I. Chesser, T. Francis, M. De Graef and E. A. Holm, Learning the grain boundary manifold: tools for visualizing and fitting grain boundary properties. Acta Mater. 195 (2020) 209–218. | DOI

[12] H. Federer, Geometric Measure Theory. Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen. Springer (1969). | Zbl

[13] J. Heinonen, P. Koskela, N. Shanmugalingam and J. T. Tyson, Sobolev spaces on metric measure spaces. Number 27. Cambridge University Press (2015). | MR | Zbl | DOI

[14] L. Kassab, Multidimensional scaling: Infinite metric measure spaces. Preprint [] (2019). Masters thesis. | arXiv

[15] S. Lim and F. Mémoli, Classical mds on metric measure spaces. Preprint [] (2022). | arXiv | MR | Zbl

[16] F. Mémoli, Gromov-Wasserstein distances and the metric approach to object matching. Found. Comput. Math. 11 (2011) 417–487. | MR | Zbl | DOI

[17] N. Puchkin, V. Spokoiny, E. Stepanov and D. Trevisan, Reconstruction of manifold embeddings into euclidean spaces via intrinsic distances. Preprint [] (2020). | arXiv | MR

[18] L. Rosasco, M. Belkin and E. De Vito, On learning with integral operators. J. Machine Learn. Res. 11 (2010) 905–934. | MR | Zbl

[19] B. Russo, On the Hausdorff-Young theorem for integral operators. Pacific J. Math. 68 (1977) 241–253. | MR | Zbl | DOI

[20] J. Tenenbaum, Mapping a manifold of perceptual observations. Advances in neural information processing systems, 10 (1997).

[21] J. Tenenbaum, V. De Silva and J. C. Langford, A global geometric framework for nonlinear dimensionality reduction. Science 290 (2000) 2319–2323. | DOI

[22] J. T. Tyson and J.-M. Wu, Characterizations of snowflake metric spaces. Ann. Acad. Sci. Fenn. Math 30 (2005) 313–336. | MR | Zbl

[23] J. Von Neumann and I. J. Schoenberg, Fourier integrals and metric geometry. Trans. Arn,. Math. Soc. 50 (1941) 226–251. | MR | Zbl | DOI

[24] J. Wang, Geometric structure of high-dimensional data and dimensionality reduction. Springer (2012). | MR | Zbl

[25] J. Weidmann, Integraloperatoren der Spurklasse. Math. Ann. 163 (1966) 340–345. | MR | Zbl | DOI

[26] W. A. Wilson, On certain types of continuous transformations of metric spaces. Arn,. J. Math. 57 (1935) 62–68. | MR | Zbl