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

DOI10.1016/J.JCO.2010.04.004zbMATH Open1204.41019arXiv1002.0672OpenAlexW4290998531MaRDI QIDQ609740FDOQ609740

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

Publication date: 1 December 2010

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Atomic Decomposition by Basis Pursuit
• Stable signal recovery from incomplete and inaccurate measurements
• A simple proof of the restricted isometry property for random matrices
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Compressed sensing
• Compressed sensing and best \(k\)-term approximation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\)
• Hardness vs randomness
• Restricted isometry properties and nonconvex compressive sensing
• Gelfand numbers of operators with values in a Hilbert space
• Entropy numbers of diagonal operators between symmetric Banach spaces
• Sparse representations in unions of bases
• 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
• Title not available (Why is that?)
• Widths of embeddings in function spaces
• NORMS OF RANDOM MATRICES AND WIDTHS OF FINITE-DIMENSIONAL SETS
• DIAMETERS OF SOME FINITE-DIMENSIONAL SETS AND CLASSES OF SMOOTH FUNCTIONS
• Entropy numbers, s-numbers, and eigenvalue problems
• Optimal recovery and \(n\)-widths for convex classes of functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A lower estimate for entropy numbers
• Compressive sensing and structured random matrices
• Lower bounds for constant weight codes
• How neighborly can a centrally symmetric polytope be?
• Lower bounds for sparse recovery
• Highly sparse representations from dictionaries are unique and independent of the sparseness measure
• The geometry of random \(\{-1,1\}\)-polytopes
• Are bitvectors optimal?
• Title not available (Why is that?)

Cited In (47)

• Compressive Sensing
• Aggregation of affine estimators
• Kolmogorov \(n\)-widths of function classes induced by a non-degenerate differential operator: a convex duality approach
• Bounds on Kolmogorov widths and sampling recovery for classes with small mixed smoothness
• Remote sensing via \(\ell_1\)-minimization
• Sparse Legendre expansions via \(\ell_1\)-minimization
• Sparse representations and approximation theory
• Optimal approximation of infinite-dimensional holomorphic functions
• Gelfand and Kolmogorov numbers of Sobolev embeddings of weighted function spaces
• 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
• Random sections of \(\ell_p\)-ellipsoids, optimal recovery and Gelfand numbers of diagonal operators
• Stability of \(l_q\)-analysis based dual frame with Weibull matrices for \(0<q\leq 1\)
• 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
• Sparse recovery with coherent tight frames via analysis Dantzig selector and analysis LASSO
• Carl's inequality for quasi-Banach spaces
• A new look at random projections of the cube and general product measures
• Randomized approximation of summable sequences -- adaptive and non-adaptive
• Improved bounds for the RIP of subsampled circulant matrices
• Sparse recovery with partial support knowledge
• Uniqueness conditions for a class of \(\ell_{0}\)-minimization problems
• Sparse disjointed recovery from noninflating measurements
• 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
• Some \(s\)-numbers of embeddings in function spaces with polynomial weights
• The restricted isometry property for time-frequency structured random matrices
• Improved bounds for sparse recovery from subsampled random convolutions
• Homogeneous algorithms and solvable problems on cones
• Gel'fand widths of the unit ball of the Hardy class \(H^ p\) in weight spaces
• Flavors of compressive sensing
• Analysis of the ratio of \(\ell_1\) and \(\ell_2\) norms in compressed sensing

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)