Abstract
It is well-known that \(\mathbb R^N\) has subspaces of dimension proportional to N on which the ℓ1 and ℓ2 norms are uniformly equivalent, but it is unknown how to construct them explicitly. We show that, for any δ> 0, such a subspace can be generated using only N δ random bits. This improves over previous constructions of Artstein-Avidan and Milman, and of Lovett and Sodin, which require O(N logN), and O(N) random bits, respectively.
Such subspaces are known to also yield error-correcting codes over the reals and compressed sensing matrices. Our subspaces are defined by the kernel of a relatively sparse matrix (with at most N δ non-zero entries per row), and thus enable compressed sensing in near-linear O(N 1 + δ) time.
As in the work of Guruswami, Lee, and Razborov, our construction is the continuous analog of a Tanner code, and makes use of expander graphs to impose a collection of local linear constraints on vectors in the subspace. Our analysis is able to achieve uniform equivalence of the ℓ1 and ℓ2 norms (independent of the dimension). It has parallels to iterative decoding of Tanner codes, and leads to an analogous near-linear time algorithm for error-correction over reals.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Artstein-Avidan, S., Milman, V.D.: Logarithmic reduction of the level of randomness in some probabilistic geometric constructions. J. Funct. Anal. 235(1), 297–329 (2006)
Alon, N.: Personal communication (2008)
Candes, E.J., Tao, T.: Decoding by linear programming. IEEE Trans. Inform. Theory 51(12), 4203–4215 (2005)
Donoho, D.L.: Compressed sensing. IEEE Transactions on Information Theory 52, 1289–1306 (2006)
Figiel, T., Lindenstrauss, J., Milman, V.D.: The dimension of almost spherical sections of convex bodies. Acta Math. 139(1-2), 53–94 (1977)
Garnaev, A., Gluskin, E.D.: The widths of Euclidean balls. Doklady An. SSSR. 277, 1048–1052 (1984)
Guruswami, V., Indyk, P.: Linear-time encodable/decodable codes with near-optimal rate. IEEE Trans. Inform. Theory 51(10), 3393–3400 (2005)
Guruswami, V., Lee, J.R., Razborov, A.: Almost Euclidean subspaces of \(\ell_1^{N}\) via expander codes. In: SODA 2008: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics, pp. 353–362 (2008)
Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Amer. Math. Soc. (N.S.) 43(4), 439–561 (2006)
Indyk, P.: Stable distributions, pseudorandom generators, embeddings, and data stream computation. Journal of the ACM 53(3), 307–323 (2006)
Indyk, P.: Uncertainty principles, extractors, and explicit embeddings of L 2 into L 1. In: Proceedings of the 39th Annual ACM Symposium on the Theory of Computing, pp. 615–620 (2007)
Johnson, W.B., Schechtman, G.: Finite dimensional subspaces of \(L\sb p\). In: Handbook of the geometry of Banach spaces, vol. I, pp. 837–870. North-Holland, Amsterdam (2001)
Kashin, B.S.: The widths of certain finite-dimensional sets and classes of smooth functions. Izv. Akad. Nauk SSSR Ser. Mat. 41(2), 334–351, 478 (1977)
Kashin, B.S., Temlyakov, V.N.: A remark on compressed sensing (2007), http://www.dsp.ece.rice.edu/cs/KT2007.pdf
Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica 8(3), 261–277 (1988)
Lovett, S., Sodin, S.: Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits. Electronic Colloquium on Computational Complexity, Report TR07-012 (2007)
Milman, V.: Topics in asymptotic geometric analysis. Geom. Funct. Anal., 792–815 (2000) (Special Volume, Part II); GAFA 2000 (Tel Aviv, 1999)
Schütt, C.: Entropy numbers of diagonal operators between symmetric Banach spaces. J. Approx. Theory 40(2), 121–128 (1984)
Sipser, M., Spielman, D.A.: Expander codes. IEEE Trans. Inform. Theory 42(6, part 1), 1710–1722 (1996) (Codes and complexity)
Szarek, S.: Convexity, complexity, and high dimensions. In: International Congress of Mathematicians, vol. II, pp. 1599–1621. Eur. Math. Soc., Zürich (2006)
Tanner, R.M.: A recursive approach to low complexity codes. IEEE Transactions on Information Theory 27(5), 533–547 (1981)
Xu, W., Hassibi, B.: Efficient compressive sensing with determinstic guarantees using expander graphs. In: IEEE Information Theory Workshop (September 2007)
Zémor, G.: On expander codes. IEEE Transactions on Information Theory 47(2), 835–837 (2001)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Guruswami, V., Lee, J.R., Wigderson, A. (2008). Euclidean Sections of \(\ell_1^N\) with Sublinear Randomness and Error-Correction over the Reals. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds) Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2008 2008. Lecture Notes in Computer Science, vol 5171. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85363-3_35
Download citation
DOI: https://doi.org/10.1007/978-3-540-85363-3_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85362-6
Online ISBN: 978-3-540-85363-3
eBook Packages: Computer ScienceComputer Science (R0)