[Banach] Abstract of a paper by Shahar Mendelson, Alain Pajor and Nicole Tomczak-Jaegermann
alspach at www.math.okstate.edu
Tue Aug 29 13:34:32 CDT 2006
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;
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
or by email in unzipped form by transmitting an empty message with
or in gzipped form by using subject line
to: math at arXiv.org.
More information about the Banach