Abstract of a paper by Shahar Mendelson, Alain Pajor and Nicole Tomczak-Jaegermann
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.
participants (1)
-
Dale Alspach