Uniform uncertainty principle for Bernoulli and subgaussian ensembles

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

Nicole Tomczak-Jaegermann, Shahar Mendelson, 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 matrices; generic chaining; approximate reconstruction; uniform uncertainty principle

Mathematics Subject Classification ID

60B20: Random matrices (probabilistic aspects)

46B07: Local theory of Banach spaces

41A45: Approximation by arbitrary linear expressions

52A23: Asymptotic theory of convex bodies

Related Items

Sparsity and non-Euclidean embeddings, Restricted isometries for partial random circulant matrices, Invertibility of random submatrices via tail-decoupling and a matrix Chernoff inequality, On higher order isotropy conditions and lower bounds for sparse quadratic forms, Compressive sensing using chaotic sequence based on Chebyshev map, Compressed sensing with coherent and redundant dictionaries, The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\), Error estimates for orthogonal matching pursuit and random dictionaries, Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling, Iterative hard thresholding for compressed sensing, Stability properties of neighbourly random polytopes, Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit, Sparse recovery with coherent tight frames via analysis Dantzig selector and analysis LASSO, Stability and instance optimality for Gaussian measurements in compressed sensing, Near oracle performance and block analysis of signal space greedy methods, Greedy signal space methods for incoherence and beyond, Greedy-like algorithms for the cosparse analysis model, Fast and RIP-optimal transforms

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