# Reconstruction and subgaussian operators

Research paper by **Shahar Mendelson, Alain Pajor, Nicole Tomczak-Jaegermann**

Indexed on: **13 Jun '05**Published on: **13 Jun '05**Published in: **Mathematics - Functional Analysis**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### 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} |k^{-1}\sum_{i=1}^k f^2(X_i) -\E f^2 |$
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.