Uniform Uncertainty Principle for Bernoulli and Subgaussian Ensembles

By Shahar Mendelson, Alain Pajor, Nicole Tomczak-Jaegermann. 2006

331 citations recorded by the source corpus.

The paper considers random matrices with independent subgaussian columns and provides a new elementary proof of the Uniform Uncertainty Principle for such matrices. The Principle was introduced by Candes, Romberg and Tao in 2004; for subgaussian random matrices it was carlier proved by the present authors, as a consequence of a general result based on a generic chaining method of Talagrand. The present proof combines a simple measure concentration and a covering argument, which are standard tools of high-dimensional convexity.

Subfields: Applied Mathematics, Computational Mechanics, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Computational Mechanics

In Statistical and Nonlinear Physics

Citations in the corpus

Introduction to the non-asymptotic analysis of random matrices (2010, background): “65 was proved in [54] for the row-independent model; an extension from sub-gaussian to sub-exponential distributions is given in [3].”
Uncertainty Principles and Vector Quantization (2006, background): “Theorem 4.6 and Lemma 4.8 below can be deduced from the recent works [32], [33].”
Multi-Label Prediction via Compressed Sensing (2009, background): “(DeVore, 2007)), the best guarantees are obtained when the matrix is chosen randomly from an appropriate distribution, such as one of the following (Mendelson et al., 2008; Rudelson & Vershynin, 2006).”
Iterative Hard Thresholding for Compressed Sensing (2008, background): “The importance of thesep-compressiblesignals is that they can be well approximated using exact sparse signals.”
Compressed Sensing with Coherent and Redundant Dictionaries (2010, unknown): “It is now well known that many types of random measurement matrices have small restricted isometry constants [16,32,37,6].”
Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit (2007, methodology): “No iterative methods have been known to feature such uniform guarantees, with the exception of Chaining Pursuit [14] and the HHS Algorithm [15] which however only work with specifically designed structured measurement matrices.”
An Introduction To Compressive Sampling (2008, unknown): “IEEE SIGNAL PROCESSING MAGAZINE [24] MARCH 2008”
Group Lasso for high dimensional sparse quantile regression models (2011, unknown): “…as long as For each k , it is shown by a standard argument that there exists a 1 / 2-cover Π k of U k such that Π k ⊂ U k , U k ⊂ 2 conv Π k and | Π k | ≤ 5 p k (conv Π k stands for the convex hull of Π k , and 2 conv Π k = { 2 α : α ∈ conv Π k } ; for this result, cf. Mendelson et al., 2008).”
Restricted Eigenvalue Conditions on Subgaussian Random Matrices (2009, methodology): “…for a random matrix the UUP holds for s = O ( n/ log( p/n )) with i.i.d. Gaussian random variables (that is, Gaussian random ensemble, subject to normalizations of columns), the Bernoulli, and in general the subgaussian ensembles ( Baraniuk et al., 2008; Mendelson et al., 2008) (cf. Theorem 2.5).”
Compressed Sensing and Redundant Dictionaries (2007, background): “Finally, it would be interesting to relax the incoherence assumption on the dictionary.”
Non-asymptotic theory of random matrices: extreme singular values (2010, unknown): “For random subgaussian matrices this result was proved in [9, 57] by an ε-net argument, where one first checks the deviation inequality |‖Ax‖(2)2 − 1| ≤ δ with exponentially high probability for a fixed vector x as in (5.”
Restricted Eigenvalue Properties for Correlated Gaussian Designs (2010, methodology): “…isometry property (RIP) holds with high probability for various classes of random matrices with i.i.d. entries, including sub-Gaussian matrices (Mendelson et al., 2008) with sample size n = Ω(k log(p/k)), and for i.i.d. subexponential random matrices (Adamczak et al., 2009) provided that n =…”
Fast and Efficient Compressive Sensing Using Structurally Random Matrices (2011, background): “wer bound value of 1/ √ N. A popular family of sensing matrices is a random projection or a random matrix of i.i.d random variables from a subGaussian distribution such as Gaussian or Bernoulli [12], [13]. This family of sensing matrix is well-known as it is universally incoherent with all other spa”