This is an announcement for the paper "Uniform uncertainty principle for Bernoulli and subgaussian ensembles" by Shahar Mendelson, Alain Pajor and Nicole Tomczak-Jaegermann.
Abstract: We present a simple solution to a question posed by Candes, Romberg and Tao on the uniform uncertainty principle for Bernoulli random matrices. More precisely, we show that a rectangular k*n random subgaussian matrix (with k < n) has the property that by arbitrarily extracting any m (with m < k) columns, the resulting submatrices are arbitrarily close to (multiples of) isometries of a Euclidean space. We obtain the optimal estimate for m as a function of k,n and the degree of "closeness" to an isometry. We also give a short and self-contained solution of the reconstruction problem for sparse vectors.
Archive classification: Statistics; Functional Analysis
Mathematics Subject Classification: 46B07; 47B06; 41A05; 62G05; 94B75
Remarks: 15 pages; no figures; submitted
The source file(s), uup-arx-21-08.tex: 48079 bytes, is(are) stored in gzipped form as 0608665.gz with size 16kb. The corresponding postcript file has gzipped size 71kb.
Submitted from: alain.pajor@univ-mlv.fr
The paper may be downloaded from the archive by web browser from URL
http://front.math.ucdavis.edu/math.ST/0608665
or
http://arXiv.org/abs/math.ST/0608665
or by email in unzipped form by transmitting an empty message with subject line
uget 0608665
or in gzipped form by using subject line
get 0608665
to: math@arXiv.org.