Document Open Access Logo

𝓁_p-Spread and Restricted Isometry Properties of Sparse Random Matrices

Authors Venkatesan Guruswami, Peter Manohar, Jonathan Mosheiff

PDF
Thumbnail PDF

File

LIPIcs.CCC.2022.7.pdf
  • Filesize: 0.71 MB
  • 17 pages

Document Identifiers

Author Details

Venkatesan Guruswami
  • University of California, Berkeley, CA, USA
Peter Manohar
  • Carnegie Mellon University, Pittsburgh, PA, USA
Jonathan Mosheiff
  • Carnegie Mellon University, Pittsburgh, PA, USA

Funding

  • Guruswami, Venkatesan: Supported in part by NSF grants CCF-1908125 and CCF-2210823, and a Simons Investigator Award.
  • Manohar, Peter: Supported in part by an ARCS Scholarship, NSF Graduate Research Fellowship (under grant numbers DGE1745016 and DGE2140739), and NSF CCF-1814603. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
  • Mosheiff, Jonathan: Supported in part by NSF CCF-1814603.

Acknowledgements

We thank Sidhanth Mohanty for helpful discussions about the works of [Brito et al., 2018; Bordenave, 2019; Bordenave and Collins, 2019; Sidhanth Mohanty et al., 2020; Sidhanth Mohanty et al., 2020; Ryan O'Donnell and Xinyu Wu, 2020], and Yuval Peled for helpful discussions about convergence theorems for graph spectra. We thank Amir Shpilka for bringing the work of [Zohar Shay Karnin, 2011] to our attention, and Ioana Dumitriu for bringing the works of [Brito et al., 2018; Yizhe Zhu, 2020] to our attention.

Cite As Get BibTex

Venkatesan Guruswami, Peter Manohar, and Jonathan Mosheiff. 𝓁_p-Spread and Restricted Isometry Properties of Sparse Random Matrices. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.CCC.2022.7

Abstract

Random subspaces X of ℝⁿ of dimension proportional to n are, with high probability, well-spread with respect to the 𝓁₂-norm. Namely, every nonzero x ∈ X is "robustly non-sparse" in the following sense: x is ε ‖x‖₂-far in 𝓁₂-distance from all δ n-sparse vectors, for positive constants ε, δ bounded away from 0. This "𝓁₂-spread" property is the natural counterpart, for subspaces over the reals, of the minimum distance of linear codes over finite fields, and corresponds to X being a Euclidean section of the 𝓁₁ unit ball. Explicit 𝓁₂-spread subspaces of dimension Ω(n), however, are unknown, and the best known explicit constructions (which achieve weaker spread properties), are analogs of low density parity check (LDPC) codes over the reals, i.e., they are kernels of certain sparse matrices.
Motivated by this, we study the spread properties of the kernels of sparse random matrices. We prove that with high probability such subspaces contain vectors x that are o(1)⋅‖x‖₂-close to o(n)-sparse with respect to the 𝓁₂-norm, and in particular are not 𝓁₂-spread. This is strikingly different from the case of random LDPC codes, whose distance is asymptotically almost as good as that of (dense) random linear codes.
On the other hand, for p < 2 we prove that such subspaces are 𝓁_p-spread with high probability. The spread property of sparse random matrices thus exhibits a threshold behavior at p = 2. Our proof for p < 2 moreover shows that a random sparse matrix has the stronger restricted isometry property (RIP) with respect to the 𝓁_p norm, and in fact this follows solely from the unique expansion of a random biregular graph, yielding a somewhat unexpected generalization of a similar result for the 𝓁₁ norm [Berinde et al., 2008]. Instantiating this with suitable explicit expanders, we obtain the first explicit constructions of 𝓁_p-RIP matrices for 1 ≤ p < p₀, where 1 < p₀ < 2 is an absolute constant.

Subject Classification

ACM Subject Classification
  • Theory of computation → Pseudorandomness and derandomization
  • Theory of computation → Random projections and metric embeddings
Keywords
  • Spread Subspaces
  • Euclidean Sections
  • Restricted Isometry Property
  • Sparse Matrices

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Zeyuan Allen-Zhu, Rati Gelashvili, and Ilya P. Razenshteyn. Restricted isometry property for general p-norms. In 31st International Symposium on Computational Geometry, SoCG 2015, June 22-25, 2015, Eindhoven, The Netherlands, volume 34 of LIPIcs, pages 451-460. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. Google Scholar
  2. Afonso S Bandeira and Ramon Van Handel. Sharp nonasymptotic bounds on the norm of random matrices with independent entries. Annals of Probability, 44(4):2479-2506, 2016. Google Scholar
  3. Boaz Barak, Fernando G. S. L. Brandão, Aram Wettroth Harrow, Jonathan A. Kelner, David Steurer, and Yuan Zhou. Hypercontractivity, sum-of-squares proofs, and their applications. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 307-326. ACM, 2012. Google Scholar
  4. Richard Baraniuk, Mark Davenport, Ronald DeVore, and Michael Wakin. A simple proof of the Restricted Isometry property for random matrices. Available at https://www.math.tamu.edu/~rdevore/publications/131.pdf, 2007.
  5. Anirban Basak and Mark Rudelson. Invertibility of sparse non-hermitian matrices. Advances in Mathematics, 310:426-483, 2017. Google Scholar
  6. R. Berinde, A. C. Gilbert, P. Indyk, H. Karloff, and M. J. Strauss. Combining geometry and combinatorics: A unified approach to sparse signal recovery. In 2008 46th Annual Allerton Conference on Communication, Control, and Computing, pages 798-805, 2008. URL: https://doi.org/10.1109/ALLERTON.2008.4797639.
  7. Charles Bordenave. A new proof of friedman’s second eigenvalue theorem and its extension to random lifts. In Annales scientifiques de l'Ecole normale supérieure, 2019. Google Scholar
  8. Charles Bordenave and Benoît Collins. Eigenvalues of random lifts and polynomials of random permutation matrices. Annals of Mathematics, 190(3):811-875, 2019. Google Scholar
  9. Gerandy Brito, Ioana Dumitriu, and Kameron Decker Harris. Spectral gap in random bipartite biregular graphs and applications. arXiv preprint, 2018. URL: http://arxiv.org/abs/1804.07808.
  10. Emmanuel J. Candès, Justin K. Romberg, and Terence Tao. Stable signal recovery from incomplete and inaccurate measurements. Comm. Pure Appl. Math., 59:1207-1223, 2006. Google Scholar
  11. Emmanuel J. Candès and Terence Tao. Decoding by linear programming. IEEE Trans. Inf. Theory, 51(12):4203-4215, 2005. Google Scholar
  12. Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, and Avi Wigderson. Randomness conductors and constant-degree lossless expanders. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 659-668. ACM, 2002. Google Scholar
  13. David L. Donoho. Compressed sensing. IEEE Trans. Inf. Theory, 52(4):1289-1306, 2006. URL: https://doi.org/10.1109/TIT.2006.871582.
  14. T. Figiel, J. Lindenstrauss, and V. D. Milman. The dimension of almost spherical sections of convex bodies. Acta Math., 139(1-2):53-94, 1977. Google Scholar
  15. R. G. Gallager. Low-Density Parity-Check Codes. MIT Press, 1963. Google Scholar
  16. A. Garnaev and E. D. Gluskin. The widths of Euclidean balls. Doklady An. SSSR., 277:1048-1052, 1984. Google Scholar
  17. E. D. Gluskin. Norms of random matrices and diameters of finite-dimensional sets. Mat. Sb. (N.S.), 120(162)(2):180-189, 286, 1983. Google Scholar
  18. V. Guruswami, J. Lee, and A. Wigderson. Euclidean sections of with sublinear randomness and error-correction over the reals. In 12th International Workshop on Randomization and Combinatorial Optimization: Algorithms and Techniques (RANDOM), pages 444-454, 2008. Google Scholar
  19. Venkatesan Guruswami, James R. Lee, and Alexander A. Razborov. Almost Euclidean subspaces of 𝓁₁^N via expander codes. Combinatorica, 30(1):47-68, 2010. URL: https://doi.org/10.1007/s00493-010-2463-9.
  20. Piotr Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream computation. Journal of the ACM, 53(3):307-323, 2006. Google Scholar
  21. Piotr Indyk. Uncertainty principles, extractors, and explicit embeddings of L₁ into L₂. In Proceedings of the 39th Annual ACM Symposium on the Theory of Computing, pages 615-620, 2007. Google Scholar
  22. Piotr Indyk and Stanislaw J. Szarek. Almost-euclidean subspaces of 𝓁₁ⁿ via tensor products: A simple approach to randomness reduction. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings, volume 6302 of Lecture Notes in Computer Science, pages 632-641. Springer, 2010. Google Scholar
  23. Zohar Shay Karnin. Deterministic construction of a high dimensional l_p section in l_1^n for any p2. In Lance Fortnow and Salil P. Vadhan, editors, Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 645-654. ACM, 2011. URL: https://doi.org/10.1145/1993636.1993722.
  24. B. S. Kashin. The widths of certain finite-dimensional sets and classes of smooth functions. Izv. Akad. Nauk SSSR Ser. Mat., 41(2):334-351, 478, 1977. Google Scholar
  25. Boris S Kashin and Vladimir N Temlyakov. A remark on compressed sensing. Mathematical notes, 82(5):748-755, 2007. Google Scholar
  26. Sidhanth Mohanty, Ryan O'Donnell, and Pedro Paredes. Explicit near-ramanujan graphs of every degree. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 510-523. ACM, 2020. Google Scholar
  27. Sidhanth Mohanty, Ryan O'Donnell, and Pedro Paredes. The SDP value for random two-eigenvalue csps. In 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France, volume 154 of LIPIcs, pages 50:1-50:45. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  28. Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, and Mary Wootters. LDPC codes achieve list decoding capacity. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, pages 458-469, 2020. Google Scholar
  29. Ryan O'Donnell and Xinyu Wu. Explicit near-fully X-ramanujan graphs. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1045-1056. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00101.
  30. Tom Richardson and Ruediger Urbanke. Modern Coding Theory. Cambridge University Press, USA, 2008. Google Scholar
  31. Michael Sipser and Daniel A. Spielman. Expander codes. IEEE Trans. Inform. Theory, 42(6, part 1):1710-1722, 1996. Codes and complexity. Google Scholar
  32. Robert M. Tanner. A recursive approach to low complexity codes. IEEE Transactions on Information Theory, 27(5):533-547, 1981. Google Scholar
  33. Terence Tao. Topics in random matrix theory, volume 132. American Mathematical Soc., 2012. Google Scholar
  34. Yizhe Zhu. On the second eigenvalue of random bipartite biregular graphs. arXiv preprint, 2020. URL: http://arxiv.org/abs/2005.08103.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact