This is an announcement for the paper "Reconstruction and subgaussian operators" by Shahar Mendelson, Alain Pajor and Nicole Tomczak-Jaegermann.
Abstract: We present a randomized method to approximate any vector $v$ from some set $T \subset \R^n$. The data one is given is the set $T$, and $k$ scalar products $(\inr{X_i,v})_{i=1}^k$, where $(X_i)_{i=1}^k$ are i.i.d. isotropic subgaussian random vectors in $\R^n$, and $k \ll n$. We show that with high probability, any $y \in T$ for which $(\inr{X_i,y})_{i=1}^k$ is close to the data vector $(\inr{X_i,v})_{i=1}^k$ will be a good approximation of $v$, and that the degree of approximation is determined by a natural geometric parameter associated with the set $T$. We also investigate a random method to identify exactly any vector which has a relatively short support using linear subgaussian measurements as above. It turns out that our analysis, when applied to ${-1,1}$-valued vectors with i.i.d, symmetric entries, yields new information on the geometry of faces of random ${-1,1}$-polytope; we show that a $k$-dimensional random ${-1,1}$-polytope with $n$ vertices is $m$-neighborly for very large $m\le {ck/\log (c' n/k)}$. The proofs are based on new estimates on the behavior of the empirical process $\sup_{f \in F} \left|k^{-1}\sum_{i=1}^k f^2(X_i) -\E f^2 \right|$ when $F$ is a subset of the $L_2$ sphere. The estimates are given in terms of the $\gamma_2$ functional with respect to the $\psi_2$ metric on $F$, and hold both in exponential probability and in expectation.
Archive classification: Functional Analysis; Probability
Mathematics Subject Classification: 46B07, 47B06, 41A45; 94B75, 52B05
Remarks: 31 pages; no figures; submitted
The source file(s), MPT_subgaussian.tex: 75209 bytes, is(are) stored in gzipped form as 0506239.gz with size 24kb. The corresponding postcript file has gzipped size 106kb.
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.FA/0506239
or
http://arXiv.org/abs/math.FA/0506239
or by email in unzipped form by transmitting an empty message with subject line
uget 0506239
or in gzipped form by using subject line
get 0506239
to: math@arXiv.org.