Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Deterministic Construction of a high dimensional ell-p section in ell-1^n for any p<2 (and its implications in compressed sensing)
event speaker icon
Zohar Karnin (CS, Technion)
event date icon
Wednesday, 10.11.2010, 12:30
event location icon
Room 337-8 Taub Bld.
For 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.