Almost Euclidean subspaces of \ell_1^N via expander codes
Preprint
Abstract
We give an explicit (in particular, deterministic polynomial time) construction of subspaces X of R^N of dimension (1-o(1))N such that for every element x in X, |x|_1 and N^{1/2} |x|_2 are equivalent up to a factor of (log N)^{log log log N}. If we are allowed to use N^{o(1)} random bits, this factor can be improved to poly(log N). 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.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Deterministic constructions of compressed sensing matricesJournal of Complexity, 2007
- Logarithmic reduction of the level of randomness in some probabilistic geometric constructionsJournal of Functional Analysis, 2006
- A sum-product estimate in finite fields, and applicationsGeometric and Functional Analysis, 2004
- Topics in Asymptotic Geometric Analysis2000
- The geometry of graphs and some of its algorithmic applicationsCombinatorica, 1995
- QUADRATIC FORMS OVER GF(2)1991
- Entropy numbers of diagonal operators between symmetric Banach spacesJournal of Approximation Theory, 1984
- Random embeddings of Euclidean spaces in sequence spacesIsrael Journal of Mathematics, 1981
- The dimension of almost spherical sections of convex bodiesActa Mathematica, 1977
- A class of low-rate nonlinear binary codesInformation and Control, 1972