Sampling, Metric Entropy, and Dimensionality Reduction

DOI10.1137/130944436MaRDI QIDQ5253416zbMATH OpenOpenAlexFDO

Authors Dmitry Batenkov, Omer Friedland, Yosef Yomdin

Publication date 26 May 2015

Published in SIAM Journal on Mathematical Analysis (Search for Journal in Brave)

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

zbMATH Keywords

dimensionality reductionJohnson-Lindenstrauss lemmametric entropysampling

Mathematics Subject Classification ID

Approximation by arbitrary nonlinear expressions; widths and entropy (41A46) Hilbert spaces of continuous, differentiable or analytic functions (46E20) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Measures of information, entropy (94A17) Sampling theory in information and communication theory (94A20)

Abstract: Let $Q$ be a relatively compact subset in a Hilbert space $V$. For a given $e>0$ let $N(e,Q)$ be the minimal number of linear measurements, sufficient to reconstruct any $xinQ$ with the accuracy $e$. We call $N(e,Q)$ a sampling $e$-entropy of $Q$. Using Dimensionality Reduction, as provided by the Johnson-Lindenstrauss lemma, we show that, in an appropriate probabilistic setting, $N(e,Q)$ is bounded from above by the Kolmogorov's $e$-entropy $H(e,Q)$, defined as $H(e,Q)=logM(e,Q)$, with $M(e,Q)$ being the minimal number of $e$-balls covering $Q$. As the main application, we show that piecewise smooth (piecewise analytic) functions in one and several variables can be sampled with essentially the same accuracy rate as their regular counterparts. For univariate piecewise $C^k$-smooth functions this result, which settles the so-called Eckhoff conjecture, was recently established in cite{Bat} via a deterministic "algebraic reconstruction" algorithm.

Recommendations

• Metric entropy, n-widths, and sampling of functions on manifolds
• Approximating entropy from sublinear samples
• Intrinsic convergence properties of entropic sampling algorithms
• Metric entropy of high dimensional distributions
• Sampling lower bounds via information theory
• An entropic approach to dimensionality reduction on discrete processes
• Sampling and empirical risk minimization
• Sampling from a Manifold

Cites work

• A generalized Prony method for reconstruction of sparse sums of eigenfunctions of linear operators
• A remark on compressed sensing
• A simple proof of the restricted isometry property for random matrices
• Algebraic Fourier reconstruction of piecewise smooth functions
• Approximating piecewise-smooth functions
• Approximation of the discontinuities of a function by its classical orthogonal polynomial Fourier coefficients
• Compressed sensing and best \(k\)-term approximation
• Convergence rates for greedy algorithms in reduced basis methods
• Detection of edges in spectral data
• Entropy numbers, s-numbers, and eigenvalue problems
• Extensions of Lipschitz mappings into a Hilbert space
• Linear versus non-linear acquisition of step-functions
• Model-Based Compressive Sensing
• Nonlinear Kolmogorov widths
• On a high order numerical method for functions with singularities
• On asymptotics of entropy of a class of analytic functions
• On representation of functions by means of superpositions and related topics
• Optimal nonlinear approximation
• Problems and results in extremal combinatorics. I.
• Pseudospectral Fourier reconstruction with the modified inverse polynomial reconstruction method
• Semialgebraic complexity of functions
• Stable reconstructions in Hilbert spaces and the resolution of the Gibbs phenomenon
• Structured Compressed Sensing: From Theory to Applications
• The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite
• Wavelet compression and nonlinear n-widths

Cited in

(2)

• Metric entropy, n-widths, and sampling of functions on manifolds
• Density theorems for nonuniform sampling of bandlimited functions using derivatives or bunched measurements

This page was built for publication: Sampling, Metric Entropy, and Dimensionality Reduction

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