Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR07-086 | 7th September 2007 00:00

Almost Euclidean subspaces of $\ell_1^N$ via expander codes

TR07-086
Authors: Venkatesan Guruswami, James R. Lee, Alexander Razborov
Publication: 11th September 2007 14:58
Keywords:

Abstract:

We give an explicit (in particular, deterministic polynomial time)
construction of subspaces $X \subseteq \R^N$ of dimension $(1-o(1))N$ such that for every $x \in X$,
$$(\log N)^{-O(\log\log\log N)} \sqrt{N}\, \|x\|_2 \leq \|x\|_1 \leq \sqrt{N}\, \|x\|_2.$$
If we are allowed to use $N^{1/\log\log N}\leq N^{o(1)}$ random bits
and $\dim(X) \geq (1-\eta)N$ for any fixed constant $\eta$, the lower bound
can be further improved to $(\log N)^{-O(1)} \sqrt{N}\|x\|_2$. Our
construction makes use of unbalanced bipartite graphs to impose
local linear constraints on vectors in the subspace, and our analysis
relies on expansion properties of the graph. This is inspired by
similar constructions of error-correcting codes.

ISSN 1433-8092 | Imprint