Manifold learning with arbitrary norms

Abstract

Manifold learning methods play a prominent role in nonlinear dimensionality reduction and other tasks involving high-dimensional data sets with low intrinsic dimensionality. Many of these methods are graph-based: they associate a vertex with each data point and a weighted edge with each pair. Existing theory shows that the Laplacian matrix of the graph converges to the Laplace-Beltrami operator of the data manifold, under the assumption that the pairwise affinities are based on the Euclidean norm. In this paper, we determine the limiting differential operator for graph Laplacians constructed using $\text{any}$ norm. Our proof involves an interplay between the second fundamental form of the manifold and the convex geometry of the given norm's unit ball. To demonstrate the potential benefits of non-Euclidean norms in manifold learning, we consider the task of mapping the motion of large molecules with continuous variability. In a numerical simulation we show that a modified Laplacian eigenmaps algorithm, based on the Earthmover's distance, outperforms the classic Euclidean Laplacian eigenmaps, both in terms of computational cost and the sample size needed to recover the intrinsic geometry.

arXiv comment53 pages, 8 figures, 3 tables, to appear in Journal of Fourier Analysis and Applications

References in corpus (16)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Consistency of spectral clustering
• Diffusion Maps, Spectral Clustering and Eigenfunctions of Fokker-Planck operators
• Single-particle cryo-electron microscopy: Mathematical theory, computational challenges, and opportunities
• Empirical graph Laplacian approximation of Laplace--Beltrami operators: Large sample results
• Moments and Absolute Moments of the Normal Distribution
• An Analysis of the Convergence of Graph Laplacians
• Cryo-EM reconstruction of continuous heterogeneity by Laplacian spectral volumes
• Hierarchical Coupled Geometry Analysis for Neuronal Structure and Activity Pattern Discovery
• A Spectral Series Approach to High-Dimensional Nonparametric Regression
• Hyper-Molecules: on the Representation and Recovery of Dynamical Structures, with Application to Flexible Macro-Molecular Structures in Cryo-EM
• Approximation of Functions over Manifolds: A Moving Least-Squares Approach
• Minimax-optimal semi-supervised regression on unknown manifolds
• Earthmover-based manifold learning for analyzing molecular conformation spaces
• The embedding dimension of Laplacian eigenfunction maps
• Wasserstein K-Means for Clustering Tomographic Projections

Cited by in corpus (1)

• Discovering Conservation Laws using Optimal Transport and Manifold Learning