Multi-scale geometric methods for data sets. II: Geometric multi-resolution analysis

DOI10.1016/J.ACHA.2011.08.001zbMATH Open1242.42038arXiv1105.4924OpenAlexW2964012263MaRDI QIDQ413654FDOQ413654

Guangliang Chen, Mauro Maggioni, William Allard

Publication date: 7 May 2012

Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Abstract: Data sets are often modeled as point clouds in $R^D$, for $D$ large. It is often assumed that the data has some interesting low-dimensional structure, for example that of a $d$-dimensional manifold $M$, with $d$ much smaller than $D$. When $M$ is simply a linear subspace, one may exploit this assumption for encoding efficiently the data by projecting onto a dictionary of $d$ vectors in $R^D$ (for example found by SVD), at a cost $(n+D)d$ for $n$ data points. When $M$ is nonlinear, there are no "explicit" constructions of dictionaries that achieve a similar efficiency: typically one uses either random dictionaries, or dictionaries obtained by black-box optimization. In this paper we construct data-dependent multi-scale dictionaries that aim at efficient encoding and manipulating of the data. Their construction is fast, and so are the algorithms that map data points to dictionary coefficients and vice versa. In addition, data points are guaranteed to have a sparse representation in terms of the dictionary. We think of dictionaries as the analogue of wavelets, but for approximating point clouds rather than functions.

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

Recommendations

• Multi-resolution geometric analysis for data in high dimensions
• Multiscale geometric methods for data sets. I: Multiscale SVD, noise and curvature.
• Multiresolution analysis over triangle meshes: method and data structure
• A class of multi-resolution approximations for large spatial datasets
• scientific article; zbMATH DE number 1962908
• Geometric component analysis and its applications to data analysis
• Adaptive geometric multiscale approximations for intrinsically low-dimensional data
• The geometry and the analytic properties of isotropic multiresolution analysis
• Multiscale methods for problems with complex geometry
• Geometric diffusions as a tool for harmonic analysis and structure definition of data: multiscale methods

zbMATH Keywords

framemulti-scale analysisdictionary learningmultiresolution analysisgeometric waveletshigh-dimensional data set

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Nontrigonometric harmonic analysis involving wavelets and other special systems (42C40) Nontrigonometric harmonic analysis (42C99)

Cites Work

• Title not available (Why is that?)
• Finding the homology of submanifolds with high confidence from random samples
• Diffusion maps
• Diffusion wavelets
• Curvature Measures
• Atomic Decomposition by Basis Pursuit
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• Title not available (Why is that?)
• A theory for multiresolution signal decomposition: the wavelet representation
• Ten Lectures on Wavelets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Multiresolution Approximations and Wavelet Orthonormal Bases of L 2 (R)
• Title not available (Why is that?)
• A T(b) theorem with remarks on analytic capacity and the Cauchy integral
• Random projections of smooth manifolds
• Online learning for matrix factorization and sparse coding
• Manifold parametrizations by eigenfunctions of the Laplacian and heat kernels
• Title not available (Why is that?)
• Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps
• Principal Manifolds and Nonlinear Dimensionality Reduction via Tangent Space Alignment
• Title not available (Why is that?)
• Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data
• An introduction to frames and Riesz bases
• Intrinsic dimension estimation of data: An approach based on Grassberger-Procaccia's algorithm
• Title not available (Why is that?)
• Image decomposition via the combination of sparse representations and a variational approach
• Title not available (Why is that?)
• Multiscale Representations for Manifold-Valued Data
• Fast computation in adaptive tree approximation
• Uniform rectifiability and quasiminimizing sets of arbitrary codimension
• Multiscale geometric methods for data sets. I: Multiscale SVD, noise and curvature.
• A Randomized Algorithm for Principal Component Analysis
• Rectifiable sets and the traveling salesman problem
• The traveling salesman problem and harmonic analysis
• Diffusion wavelet packets
• Title not available (Why is that?)
• Geometric diffusions as a tool for harmonic analysis and structure definition of data: Multiscale methods
• Title not available (Why is that?)
• Fast high-dimensional approximation with sparse occupancy trees
• Asymptotic regularity of subdivisions of Euclidean domains by iterated PCA and iterated 2-means

Cited In (28)

• Data-driven spectral decomposition and forecasting of ergodic dynamical systems
• Multiscale geometric methods for data sets. I: Multiscale SVD, noise and curvature.
• Approximation of functions over manifolds: a moving least-squares approach
• Deep nonparametric estimation of intrinsic data structures by chart autoencoders: generalization error and robustness
• Adaptive Geometric Multiscale Approximations for Intrinsically Low-dimensional Data
• A machine learning approach to optimal Tikhonov regularization I: Affine manifolds
• Hierarchical regularization networks for sparsification based learning on noisy datasets
• Geometric multiscale analysis: from wavelets to parabolic molecules
• An analyst's traveling salesman theorem for sets of dimension larger than one
• Local Linear Regression on Manifolds and Its Geometric Interpretation
• On recovery guarantees for one-bit compressed sensing on manifolds
• Approximation of curve-based sleeve functions in high dimensions
• Approximation of generalized ridge functions in high dimensions
• Constraint matrix factorization for space variant PSFs field restoration
• Bayesian Multiscale Modeling of Closed Curves in Point Clouds
• Extraction and prediction of coherent patterns in incompressible flows through space-time koopman analysis
• A distributed and incremental SVD algorithm for agglomerative data analysis on large networks
• The shape of data and probability measures
• Metrics, quantization and registration in varifold spaces
• Multilevel declassification method for geographic vector field data: a geometric algebra approach
• Reprint of: A forward-backward greedy approach for sparse multiscale learning
• Learning sets with separating kernels
• Manifold Learning and Nonlinear Homogenization
• Multiscale regression on unknown manifolds
• A forward-backward greedy approach for sparse multiscale learning
• Solving inverse problems using data-driven models
• Title not available (Why is that?)
• ATLAS: A Geometric Approach to Learning High-Dimensional Stochastic Systems Near Manifolds

Uses Software

• PDCO

This page was built for publication: Multi-scale geometric methods for data sets. II: Geometric multi-resolution analysis

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