TY - JOUR
T1 - Uniform uncertainty principle for Bernoulli and subgaussian ensembles
AU - Mendelson, Shahar
AU - Pajor, Alain
AU - Tomczak-Jaegermann, Nicole
PY - 2008/12
Y1 - 2008/12
N2 - 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.
AB - 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.
KW - Approximate reconstruction
KW - Generic chaining
KW - Random matrices
KW - Uniform uncertainty principle
UR - http://www.scopus.com/inward/record.url?scp=55649100730&partnerID=8YFLogxK
U2 - 10.1007/s00365-007-9005-8
DO - 10.1007/s00365-007-9005-8
M3 - Article
SN - 0176-4276
VL - 28
SP - 277
EP - 289
JO - Constructive Approximation
JF - Constructive Approximation
IS - 3
ER -