Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > EUCLIDEAN SECTION:
Reports tagged with Euclidean Section:
TR10-162 | 30th October 2010
Zohar Karnin

#### Deterministic Construction of a high dimensional $\ell_p$ section in $\ell_1^n$ for any $p<2$

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
more >>>

ISSN 1433-8092 | Imprint