Testing the manifold hypothesis

DOI10.1090/JAMS/852MaRDI QIDQ5741444zbMATH OpenOpenAlexFDO

Authors Hariharan Narayanan, Charles Fefferman, Sanjoy K. Mitter

Publication date 25 July 2016

Published in Journal of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.0425

zbMATH Keywords

dimension reductionmanifold estimationmanifold learningprincipal manifolds

Mathematics Subject Classification ID

Fiber bundles in algebraic topology (55R10) Embeddings in differential topology (57R40) Nonparametric regression and quantile regression (62G08) Hypothesis testing in multivariate analysis (62H15) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: The hypothesis that high dimensional data tend to lie in the vicinity of a low dimensional manifold is the basis of manifold learning. The goal of this paper is to develop an algorithm (with accompanying complexity guarantees) for fitting a manifold to an unknown probability distribution supported in a separable Hilbert space, only using i.i.d samples from that distribution. More precisely, our setting is the following. Suppose that data are drawn independently at random from a probability distribution $P$ supported on the unit ball of a separable Hilbert space $H$. Let $G(d,V,au)$ be the set of submanifolds of the unit ball of $H$ whose volume is at most $V$ and reach (which is the supremum of all $r$ such that any point at a distance less than $r$ has a unique nearest point on the manifold) is at least $au$. Let $L(M,P)$ denote mean-squared distance of a random point from the probability distribution $P$ to $M$. We obtain an algorithm that tests the manifold hypothesis in the following sense. The algorithm takes i.i.d random samples from $P$ as input, and determines which of the following two is true (at least one must be): (a) There exists $MinG(d,CV,fracauC)$ such that $L(M,P)leqCepsilon.$ (b) There exists no $MinG(d,V/C,Cau)$ such that $L(M,P)leqfracepsilonC.$ The answer is correct with probability at least $1-delta$.

Recommendations

• Minimax rates for estimating the dimension of a manifold
• Finding the homology of submanifolds with high confidence from random samples
• Learning gradients on manifolds
• Sampling from a Manifold
• Shape dimension and intrinsic metric from samples of manifolds with high co-dimension (extended abstract)

Cites work

• K-Dimensional Coding Schemes in Hilbert Spaces
• \(k\)-plane clustering
• A new algorithm for minimizing convex functions over convex sets
• Advanced Lectures on Machine Learning
• Approximation of points on low-dimensional manifolds via random linear projections
• Combinatorics of random processes and sections of convex bodies
• Curvature Measures
• Estimation of dependences based on empirical data. Transl. from the Russian by Samuel Kotz
• Extensions of Lipschitz mappings into a Hilbert space
• Finding the homology of submanifolds with high confidence from random samples
• Geometric diffusions as a tool for harmonic analysis and structure definition of data: multiscale methods
• Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data
• scientific article; zbMATH DE number 499496 (Why is no real title available?)
• scientific article; zbMATH DE number 1560711 (Why is no real title available?)
• scientific article; zbMATH DE number 847265 (Why is no real title available?)
• scientific article; zbMATH DE number 893887 (Why is no real title available?)
• scientific article; zbMATH DE number 5485566 (Why is no real title available?)
• Infinite-dimensional manifolds of finite-entropy probability measures
• Interpolation and extrapolation of smooth functions by linear operators
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• Lectures on topics in analysis. Notes by M. S. Rajwade
• Locally defined principal curves and surfaces
• Manifold estimation and singular deconvolution under Hausdorff loss
• Manifold reconstruction from point samples
• Manifold reconstruction in arbitrary dimensions using witness complexes
• Minimax manifold estimation
• Nonparametric ridge estimation
• Principal Curves
• Principal Manifolds and Nonlinear Dimensionality Reduction via Tangent Space Alignment
• Random projections of smooth manifolds
• Robust recovery of multiple subspaces by geometric \(l_{p}\) minimization
• Some applications of concentration inequalities to statistics
• The C^m norm of a function with prescribed jets. II
• The concentration of measure phenomenon
• Tighter bounds for random projections of manifolds
• Topology and data
• Uniform Central Limit Theorems
• Universal local parametrizations via heat kernels and eigenfunctions of the Laplacian

Cited in

(only showing first 100 items - show all)

• Ricci curvature and the manifold learning problem
• Metric thickenings of Euclidean submanifolds
• Deep learning of thermodynamics-aware reduced-order models from data
• Density estimation on an unknown submanifold
• Robust \(k\)-means clustering for distributions with two moments
• Dimensionality reduction for \(k\)-distance applied to persistent homology
• Accelerating phase-field predictions via recurrent neural networks learning the microstructure evolution in latent space
• Reconstruction and interpolation of manifolds. I: The geometric Whitney problem
• On boundary detection
• Heuristic framework for multiscale testing of the multi-manifold hypothesis
• Interpolation, the rudimentary geometry of spaces of Lipschitz functions, and geometric complexity
• Finding the homology of submanifolds with high confidence from random samples
• Data analysis from empirical moments and the Christoffel function
• Data-driven spatiotemporal modeling for structural dynamics on irregular domains by stochastic dependency neural estimation
• Side effects of learning from low-dimensional data embedded in a Euclidean space
• Computational mean-field games on manifolds
• Megaman: scalable manifold learning in Python
• Occupants in manifolds
• Minimax rates for estimating the dimension of a manifold
• Normal-bundle bootstrap
• Reconstruction of a Riemannian manifold from noisy intrinsic distances
• Inverse problems on low-dimensional manifolds
• Geometric anomaly detection in data
• A Metric Space for Point Process Excitations
• Bayesian Imaging with Data-Driven Priors Encoded by Neural Networks
• Model-Centric Data Manifold: The Data Through the Eyes of the Model
• Persistent intersection homology for the analysis of discrete data
• Recovery of Surfaces and Functions in High Dimensions: Sampling Theory and Links to Neural Networks
• IAN: Iterated Adaptive Neighborhoods for Manifold Learning and Dimensionality Estimation
• Learning gradients on manifolds
• Pursuit of a discriminative representation for multiple subspaces via sequential games
• Universally consistent estimation of the reach
• Deep nonparametric estimation of intrinsic data structures by chart autoencoders: generalization error and robustness
• Wassmap: Wasserstein Isometric Mapping for Image Manifold Learning
• Deep nonparametric regression on approximate manifolds: nonasymptotic error bounds with polynomial prefactors
• Applications of No-Collision Transportation Maps in Manifold Learning
• Low dimensional approximation and generalization of multivariate functions on smooth manifolds using deep ReLU neural networks
• Optimal 1-Wasserstein distance for WGANs
• Tangent space and dimension estimation with the Wasserstein distance
• Discretized gradient flow for manifold learning
• Algebraic machine learning with an application to chemistry
• Random Fixed Boundary Flows
• Estimating a density near an unknown manifold: a Bayesian nonparametric approach
• A Whitney extension problem for manifolds
• Cartan moving frames and the data manifolds
• Method of moments for estimation of noisy curves
• Effective theory building and manifold learning
• Osculating geometry and higher-order distance loci
• Riemannian integrated gradients: a geometric view of explainable AI
• Localized Schrödinger bridge sampler
• Reconstruction of dynamical systems without time label
• Deep generative models: complexity, dimensionality, and approximation
• Nonasymptotic bounds for forward processes in denoising diffusions: Ornstein-Uhlenbeck is hard to beat
• Deep Mutual Density Ratio Estimation with Bregman Divergence and Its Applications
• Reconstruction and interpolation of manifolds. II: Inverse problems with partial data for distances observations and for the heat kernel
• Uncertainty estimation for learning-based classification of corrupted images
• Asymptotic theory of geometric and adaptive k-means clustering
• An accumulation method for early fault warning and its application to wind turbine systems
• Unsupervised solution operator learning for mean-field games
• Uncertainty quantification in cost-effectiveness analysis for stochastic-based infectious disease models: insights from surveillance on lymphatic filariasis
• Manifold learning in Wasserstein space
• An adaptive and stability-promoting layerwise training approach for sparse deep neural network architecture
• Manifold fitting under unbounded noise
• Fitting a manifold of large reach to noisy data
• Approximation by non-symmetric networks for cross-domain learning
• Mitigating distribution shift in machine learning-augmented hybrid simulation
• Adversarial attacks on neural networks through canonical Riemannian foliations
• Topological reconstruction of compact supports of dependent stationary random variables
• A universal law of robustness via isoperimetry
• Markov spin models for image generation: explicit large deviations with respect to the number of pixels
• On consistent estimation of dimension values
• Enabling probabilistic learning on manifolds through double diffusion maps
• Mode and Ridge Estimation in Euclidean and Directional Product Spaces: A Mean Shift Approach
• Optimal convergence rates for the spectrum of the graph Laplacian on Poisson point clouds
• Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis
• Discussion of: ``Statistical exploration of the manifold hypothesis

This page was built for publication: Testing the manifold hypothesis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5741444)