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.