[Banach] Abstract of a paper by Shahar Mendelson, Alain Pajor and Nicole Tomczak-Jaegermann

[Dale Alspach]

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 at 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 at arXiv.org.