The Gelfand widths of _p-balls for 0 < p 1

DOI10.1016/J.JCO.2010.04.004MaRDI QIDQ609740zbMATH OpenOpenAlexFDO

Authors Simon Foucart, Alain Pajor, Holger Rauhut, Tino Ullrich

Publication date 1 December 2010

Published in Journal of Complexity (Search for Journal in Brave)

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

zbMATH Keywords

sparse recoverycompressive sensing\(\ell _{1}\)-minimization\(\ell _p\)-minimizationGelfand widths

Mathematics Subject Classification ID

Approximation by arbitrary nonlinear expressions; widths and entropy (41A46)

Abstract: We provide sharp lower and upper bounds for the Gelfand widths of $el{l}_p$-balls in the $N$-dimensional $el{l}_q^N$-space for $0<pleq1$ and $p<qleq2$. Such estimates are highly relevant to the novel theory of compressive sensing, and our proofs rely on methods from this area.

Recommendations

• Kolmogorov widths of the intersection of two finite-dimensional balls
• Stability of low-rank matrix recovery and its connections to Banach space geometry
• scientific article; zbMATH DE number 3944477
• Gelfand numbers related to structured sparsity and Besov space embeddings with small mixed smoothness
• Publication:3199984

Cites work

• scientific article; zbMATH DE number 1574600 (Why is no real title available?)
• scientific article; zbMATH DE number 3877692 (Why is no real title available?)
• scientific article; zbMATH DE number 3814227 (Why is no real title available?)
• scientific article; zbMATH DE number 3944477 (Why is no real title available?)
• scientific article; zbMATH DE number 3953477 (Why is no real title available?)
• scientific article; zbMATH DE number 44592 (Why is no real title available?)
• scientific article; zbMATH DE number 713342 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• A lower estimate for entropy numbers
• A simple proof of the restricted isometry property for random matrices
• Are bitvectors optimal?
• Atomic Decomposition by Basis Pursuit
• Compressed sensing
• Compressed sensing and best \(k\)-term approximation
• Compressive sensing and structured random matrices
• DIAMETERS OF SOME FINITE-DIMENSIONAL SETS AND CLASSES OF SMOOTH FUNCTIONS
• Entropy numbers of diagonal operators between symmetric Banach spaces
• Entropy numbers, s-numbers, and eigenvalue problems
• Gelfand numbers of operators with values in a Hilbert space
• Hardness vs randomness
• Highly sparse representations from dictionaries are unique and independent of the sparseness measure
• How neighborly can a centrally symmetric polytope be?
• Lower bounds for constant weight codes
• Lower bounds for sparse recovery
• NORMS OF RANDOM MATRICES AND WIDTHS OF FINITE-DIMENSIONAL SETS
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Optimal recovery and n-widths for convex classes of functions
• Restricted isometry properties and nonconvex compressive sensing
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Sparse representations in unions of bases
• Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\)
• Stable signal recovery from incomplete and inaccurate measurements
• The geometry of random \(\{-1,1\}\)-polytopes
• The restricted isometry property and its implications for compressed sensing
• Tractability of multivariate problems. Volume I: Linear information
• Uniform uncertainty principle for Bernoulli and subgaussian ensembles
• Widths of embeddings in function spaces

Cited in

(47)

• Kolmogorov n-widths of function classes induced by a non-degenerate differential operator: a convex duality approach
• Compressive Sensing
• Aggregation of affine estimators
• Bounds on Kolmogorov widths and sampling recovery for classes with small mixed smoothness
• Remote sensing via _1-minimization
• Sparse Legendre expansions via _1-minimization
• Sparse representations and approximation theory
• Gelfand and Kolmogorov numbers of Sobolev embeddings of weighted function spaces
• Optimal approximation of infinite-dimensional holomorphic functions
• On the volume of unit balls of finite-dimensional Lorentz spaces
• Entropy numbers of finite-dimensional embeddings
• Approximation of functions with small mixed smoothness in the uniform norm
• Stability of \(l_q\)-analysis based dual frame with Weibull matrices for \(0<q\leq 1\)
• Random sections of \(\ell_p\)-ellipsoids, optimal recovery and Gelfand numbers of diagonal operators
• On deterministic sketching and streaming for sparse recovery and norm estimation
• Entropy numbers of finite dimensional mixed-norm balls and function space embeddings with small mixed smoothness
• Gelfand numbers related to structured sparsity and Besov space embeddings with small mixed smoothness
• Theory and applications of compressed sensing
• Fast and RIP-optimal transforms
• Letter to the editor: ``On exact recovery of sparse vectors from linear measurements
• Widths of embeddings of 2-microlocal Besov spaces
• Carl's inequality for quasi-Banach spaces
• Sparse recovery with coherent tight frames via analysis Dantzig selector and analysis LASSO
• A new look at random projections of the cube and general product measures
• Improved bounds for the RIP of subsampled circulant matrices
• Randomized approximation of summable sequences -- adaptive and non-adaptive
• Sparse recovery with partial support knowledge
• Sparse disjointed recovery from noninflating measurements
• Uniqueness conditions for a class of \(\ell_{0}\)-minimization problems
• Restricted isometries for partial random circulant matrices
• An introduction to compressed sensing
• Book Review: A mathematical introduction to compressive sensing
• Entropy and sampling numbers of classes of ridge functions
• Gelfand numbers of embeddings of Schatten classes
• Gelfand numbers of embeddings of mixed Besov spaces
• On the null space property of \(l_q\)-minimization for \(0 < q \leq 1\) in compressed sensing
• Metric entropy, n-widths, and sampling of functions on manifolds
• Capturing ridge functions in high dimensions from point queries
• Metric entropy of $q$-hulls in Banach spaces of type-$p$
• Uniform recovery of fusion frame structured sparse signals
• The restricted isometry property for time-frequency structured random matrices
• Some \(s\)-numbers of embeddings in function spaces with polynomial weights
• Improved bounds for sparse recovery from subsampled random convolutions
• Gel'fand widths of the unit ball of the Hardy class H^ p in weight spaces
• Homogeneous algorithms and solvable problems on cones
• Flavors of compressive sensing
• Analysis of the ratio of \(\ell_1\) and \(\ell_2\) norms in compressed sensing

Describes a project that uses

Uses Software

• PDCO

This page was built for publication: The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\)

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