The Gelfand widths of $\ell_p$-balls for $0 < p \leq 1$

DOI10.1016/j.jco.2010.04.004zbMath1204.41019arXiv1002.0672OpenAlexW4290998531MaRDI QIDQ609740

Simon Foucart, Holger Rauhut, Alain Pajor, 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

compressive sensing sparse recovery $\ell _{1}$-minimization $\ell _p$-minimization Gelfand widths

Mathematics Subject Classification ID

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

Related Items

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

Uses Software

PDCO

Cites Work

The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\)