Uniform uncertainty principle for Bernoulli and subgaussian ensembles

DOI10.1007/s00365-007-9005-8zbMath1230.46011arXivmath/0608665OpenAlexW1984305442MaRDI QIDQ1039886

Shahar Mendelson, Nicole Tomczak-Jaegermann, Alain Pajor

Publication date: 23 November 2009

Published in: Constructive Approximation (Search for Journal in Brave)

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

zbMATH Keywords

random matricesgeneric chainingapproximate reconstructionuniform uncertainty principle

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Local theory of Banach spaces (46B07) Approximation by arbitrary linear expressions (41A45) Asymptotic theory of convex bodies (52A23)

Related Items (49)

Derandomized compressed sensing with nonuniform guarantees for \(\ell_1\) recovery ⋮ An analysis of penalized interaction models ⋮ Compressed data separation via unconstrained l1-split analysis ⋮ Derandomizing restricted isometries via the Legendre symbol ⋮ Improved bounds for sparse recovery from subsampled random convolutions ⋮ High-dimensional \(A\)-learning for optimal dynamic treatment regimes ⋮ Trace regression model with simultaneously low rank and row(column) sparse parameter ⋮ Unnamed Item ⋮ Sparsity and non-Euclidean embeddings ⋮ The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\) ⋮ High-dimensional dynamic systems identification with additional constraints ⋮ Stable Image Reconstruction Using Transformed Total Variation Minimization ⋮ Improved bounds for the RIP of Subsampled Circulant matrices ⋮ Improved RIP-based bounds for guaranteed performance of two compressed sensing algorithms ⋮ The sampling complexity on nonconvex sparse phase retrieval problem ⋮ Restricted isometries for partial random circulant matrices ⋮ Error estimates for orthogonal matching pursuit and random dictionaries ⋮ Matrix deviation inequality for ℓp-norm ⋮ Time for dithering: fast and quantized random embeddings via the restricted isometry property ⋮ A strong restricted isometry property, with an application to phaseless compressed sensing ⋮ Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling ⋮ Bipolar measurement matrix using chaotic sequence ⋮ Greedy-like algorithms for the cosparse analysis model ⋮ Sparsity and incoherence in orthogonal matching pursuit ⋮ Invertibility of random submatrices via tail-decoupling and a matrix Chernoff inequality ⋮ Signal separation under coherent dictionaries and \(\ell_p\)-bounded noise ⋮ On higher order isotropy conditions and lower bounds for sparse quadratic forms ⋮ Compressive sensing using chaotic sequence based on Chebyshev map ⋮ Kernel conjugate gradient methods with random projections ⋮ Dimensionality reduction with subgaussian matrices: a unified theory ⋮ Sparse recovery under weak moment assumptions ⋮ Sparse recovery with coherent tight frames via analysis Dantzig selector and analysis LASSO ⋮ Compressed sensing with coherent and redundant dictionaries ⋮ Stability and instance optimality for Gaussian measurements in compressed sensing ⋮ Fast and RIP-optimal transforms ⋮ Iterative hard thresholding for compressed sensing ⋮ Uniform recovery of fusion frame structured sparse signals ⋮ Erasure recovery matrices for encoder protection ⋮ Stability properties of neighbourly random polytopes ⋮ Sparse recovery from extreme eigenvalues deviation inequalities ⋮ Sparse Learning for Large-Scale and High-Dimensional Data: A Randomized Convex-Concave Optimization Approach ⋮ Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit ⋮ Sparse reconstruction with multiple Walsh matrices ⋮ Posterior asymptotic normality for an individual coordinate in high-dimensional linear regression ⋮ Weaker regularity conditions and sparse recovery in high-dimensional regression ⋮ Unnamed Item ⋮ Near oracle performance and block analysis of signal space greedy methods ⋮ Greedy signal space methods for incoherence and beyond ⋮ Nonuniform recovery of fusion frame structured sparse signals

Cites Work

• Unnamed Item
• Unnamed Item
• A simple proof of the restricted isometry property for random matrices
• Weak convergence and empirical processes. With applications to statistics
• Reconstruction and subgaussian operators in asymptotic geometric analysis
• Reconstruction and subgaussian processes
• Decoding by Linear Programming
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• The Generic Chaining
• Stable signal recovery from incomplete and inaccurate measurements
• Compressed sensing

This page was built for publication: Uniform uncertainty principle for Bernoulli and subgaussian ensembles