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.