Adaptive geometric multiscale approximations for intrinsically low-dimensional data

MaRDI QIDQ5214182zbMATH OpenFDO

Authors Wenjing Liao, Mauro Maggioni

Publication date 7 February 2020

Full work available at URL https://arxiv.org/abs/1611.01179, http://jmlr.csail.mit.edu/papers/v20/17-252.html

zbMATH Keywords

adaptive approximationdictionary learningmanifold learningmulti-resolution analysis

Mathematics Subject Classification ID

Directional data; spatial statistics (62H11) Factor analysis and principal components; correspondence analysis (62H25) Learning and adaptive systems in artificial intelligence (68T05) Computational aspects of data analysis and big data (68T09)

Abstract: We consider the problem of efficiently approximating and encoding high-dimensional data sampled from a probability distribution $ho$ in $mathbb{R}^D$, that is nearly supported on a $d$-dimensional set $mathcalM$ - for example supported on a $d$-dimensional Riemannian manifold. Geometric Multi-Resolution Analysis (GMRA) provides a robust and computationally efficient procedure to construct low-dimensional geometric approximations of $mathcalM$ at varying resolutions. We introduce a thresholding algorithm on the geometric wavelet coefficients, leading to what we call adaptive GMRA approximations. We show that these data-driven, empirical approximations perform well, when the threshold is chosen as a suitable universal function of the number of samples $n$, on a wide variety of measures $ho$, that are allowed to exhibit different regularity at different scales and locations, thereby efficiently encoding data from more complex measures than those supported on manifolds. These approximations yield a data-driven dictionary, together with a fast transform mapping data to coefficients, and an inverse of such a map. The algorithms for both the dictionary construction and the transforms have complexity $Cnlogn$ with the constant linear in $D$ and exponential in $d$. Our work therefore establishes adaptive GMRA as a fast dictionary learning algorithm with approximation guarantees. We include several numerical experiments on both synthetic and real data, confirming our theoretical results and demonstrating the effectiveness of adaptive GMRA.

Recommendations

• Multi-resolution geometric analysis for data in high dimensions
• Multiscale dictionary learning: non-asymptotic bounds and robustness
• Multi-scale geometric methods for data sets. II: Geometric multi-resolution analysis
• Geometric component analysis and its applications to data analysis
• Some recent advances in multiscale geometric analysis of point clouds

Cites work

• K-Dimensional Coding Schemes in Hilbert Spaces
• A distribution-free theory of nonparametric regression
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• A T(b) theorem with remarks on analytic capacity and the Cauchy integral
• Adapting to Unknown Smoothness via Wavelet Shrinkage
• Adaptive geometric multiscale approximations for intrinsically low-dimensional data
• Approximation of points on low-dimensional manifolds via random linear projections
• Asymptotic regularity of subdivisions of Euclidean domains by iterated PCA and iterated 2-means
• Atomic Decomposition by Basis Pursuit
• Compressed sensing
• Dictionary Learning Algorithms for Sparse Representation
• Estimation of Subspace Arrangements with Applications in Modeling and Segmenting Mixed Data
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Foundations of a multi-way spectral clustering framework for hybrid linear modeling
• Geometric diffusions as a tool for harmonic analysis and structure definition of data: diffusion maps
• 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 1380579 (Why is no real title available?)
• Hybrid linear modeling via local best-fit flats
• Ideal spatial adaptation by wavelet shrinkage
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• Multi-scale geometric methods for data sets. II: Geometric multi-resolution analysis
• Multiscale dictionary learning: non-asymptotic bounds and robustness
• Multiscale geometric methods for data sets. I: Multiscale SVD, noise and curvature.
• New analysis of manifold embeddings and signal recovery from compressive measurements
• On the importance of combining wavelet-based nonlinear approximation with coding strategies
• Online learning for matrix factorization and sparse coding
• Principal Manifolds and Nonlinear Dimensionality Reduction via Tangent Space Alignment
• Rectifiable sets and the traveling salesman problem
• RELATIONS BETWEEN TWO SETS OF VARIATES
• Sample Complexity of Dictionary Learning and Other Matrix Factorizations
• Ten Lectures on Wavelets
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• The Rotation of Eigenvectors by a Perturbation. III
• The sample complexity of dictionary learning
• Universal algorithms for learning theory. I: Piecewise constant functions.
• Universal algorithms for learning theory. II: Piecewise polynomial functions

Cited in

(16)

• On recovery guarantees for one-bit compressed sensing on manifolds
• Multiscale geometric feature extraction for high-dimensional and non-Euclidean data with applications
• Multiscale regression on unknown manifolds
• Heuristic framework for multiscale testing of the multi-manifold hypothesis
• Adaptive Euclidean maps for histograms: generalized Aitchison embeddings
• Multiscale geometric methods for data sets. I: Multiscale SVD, noise and curvature.
• A scale-based approach to finding effective dimensionality in manifold learning
• Multiscale dictionary learning: non-asymptotic bounds and robustness
• Scale Space Representations Locally Adapted to the Geometry of Base and Target Manifold
• Multi-scale geometric methods for data sets. II: Geometric multi-resolution analysis
• Multiscale strategies for computing optimal transport
• Adaptive geometric multiscale approximations for intrinsically low-dimensional data
• Multi-resolution geometric analysis for data in high dimensions
• Approximation of functions on manifolds in high dimension from noisy scattered data
• Deep nonparametric estimation of intrinsic data structures by chart autoencoders: generalization error and robustness
• Manifold learning in Wasserstein space

Describes a project that uses

Uses Software

• CIFAR

This page was built for publication: Adaptive geometric multiscale approximations for intrinsically low-dimensional data

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