Reconstruction and subgaussian operators

Details Reconstruction and subgaussian operators Reconstruction and subgaussian operators

2005-06-13

arxiv.org/abs/math/0506239v1

Mathematics

Functional Analysis

31 pages; no figures; submitted

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Reconstruction and subgaussian operators does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Reconstruction and subgaussian operators, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reconstruction and subgaussian operators will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-649590