ECCC-Report TR10-162https://eccc.weizmann.ac.il/report/2010/162Comments and Revisions published for TR10-162en-usSun, 31 Oct 2010 02:09:51 +0200
Paper TR10-162
| Deterministic Construction of a high dimensional $\ell_p$ section in $\ell_1^n$ for any $p<2$ |
Zohar Karnin
https://eccc.weizmann.ac.il/report/2010/162For any $00$, we give an efficient
deterministic construction of a linear subspace $V \subseteq
\R^n$, of dimension $(1-\epsilon)n$ in which the $\ell_p$ and
$\ell_r$ norms are the same up to a multiplicative factor of
$\poly(\epsilon^{-1})$ (after the correct normalization). As a
corollary we get a deterministic compressed sensing algorithm
(Base Pursuit) for a new range of parameters. In particular, for
any constant $\epsilon>0$ and $p<2$, we obtain a linear operator
$A:\R^n \rightarrow \R^{\epsilon n}$ with the $\ell_1/\ell_p$
guarantee for $(n \cdot \poly(\epsilon))$-sparse vectors. Namely,
let $x$ be a vector in $\R^n$ whose $\ell_1$ distance from a
$k$-sparse vector (for some $k=n \cdot \poly(\epsilon)$) is
$\delta$. The algorithm, given $Ax$ as input, outputs an $n$
dimensional vector $y$ such that $||x-y||_p \leq \delta
k^{1/p-1}$. In particular this gives a weak form of the
$\ell_2/\ell_1$ guarantee.
Our construction has the additional benefit that when viewed as a
matrix, $A$ has at most $O(1)$ non-zero entries in each row. As a
result, both the encoding (computing $Ax$) and decoding
(retrieving $x$ from $Ax$) can be computed efficiently.
Sun, 31 Oct 2010 02:09:51 +0200https://eccc.weizmann.ac.il/report/2010/162