Document Open Access Logo

Restricted Isometry Property for General p-Norms

Authors Zeyuan Allen-Zhu, Rati Gelashvili, Ilya Razenshteyn

PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.451.pdf
  • Filesize: 0.48 MB
  • 10 pages

Document Identifiers

Author Details

Zeyuan Allen-Zhu
Rati Gelashvili
Ilya Razenshteyn

Cite As Get BibTex

Zeyuan Allen-Zhu, Rati Gelashvili, and Ilya Razenshteyn. Restricted Isometry Property for General p-Norms. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 451-460, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.SOCG.2015.451

Abstract

The Restricted Isometry Property (RIP) is a fundamental property of a matrix which enables sparse recovery. Informally, an m x n matrix satisfies RIP of order k for the L_p norm, if |Ax|_p is approximately |x|_p for every x with at most k non-zero coordinates.

For every 1 <= p < infty we obtain almost tight bounds on the minimum number of rows m necessary for the RIP property to hold. Prior to this work, only the cases p = 1, 1 + 1/log(k), and 2 were studied. Interestingly, our results show that the case p=2 is a "singularity" point: the optimal number of rows m is Theta(k^p) for all p in [1, infty)-{2}, as opposed to Theta(k) for k=2.

We also obtain almost tight bounds for the column sparsity of RIP matrices and discuss implications of our results for the Stable Sparse Recovery problem.

Subject Classification

Keywords
  • compressive sensing
  • dimension reduction
  • linear algebra
  • high-dimensional geometry

Metrics

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

References

  1. Zeyuan Allen-Zhu, Rati Gelashvili, Silvio Micali, and Nir Shavit. Johnson-Lindenstrauss Compression with Neuroscience-Based Constraints. ArXiv e-prints, abs/1411.5383, November 2014. Also appeared in the Proceedings of the National Academy of Sciences of the USA, vol 111, no 47. Google Scholar
  2. Zeyuan Allen-Zhu, Rati Gelashvili, and Ilya Razenshteyn. Restricted Isometry Property for General p-Norms. ArXiv e-prints, abs/1407.2178v3, February 2015. Google Scholar
  3. Richard Baraniuk, Mark Davenport, Ronald DeVore, and Michael Wakin. A simple proof of the restricted isometry property for random matrices. Constructive Approximation, 28(3):253-263, 2008. Google Scholar
  4. Radu Berinde, Anna C. Gilbert, Piotr Indyk, Howard Karloff, and Martin J. Strauss. Combining geometry and combinatorics: A unified approach to sparse signal recovery. In Proceedings of the 46th Annual Allerton Conference on Communication, Control, and Computing (Allerton 2008), pages 798-805, 2008. Google Scholar
  5. Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, and Srinivasan Venkatesh. Are bitvectors optimal? SIAM Journal on Computing, 31(6):1723-1744, 2002. Google Scholar
  6. Emmanuel Candès, Justin Romberg, and Terence Tao. Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics, 59(8):1207-1223, 2006. Google Scholar
  7. Emmanuel Candès and Terence Tao. Decoding by linear programming. IEEE Transactions on Information Theory, 51(12):4203-4215, 2005. Google Scholar
  8. Emmanuel J. Candès. The restricted isometry property and its implications for compressed sensing. Comptes Rendus Mathematique, 346(9-10):589-592, 2008. Google Scholar
  9. Venkat B. Chandar. Sparse Graph Codes for Compression, Sensing, and Secrecy. PhD thesis, Massachusetts Institute of Technology, 2010. Google Scholar
  10. Khanh Do Ba, Piotr Indyk, Eric Price, and David P. Woodruff. Lower bounds for sparse recovery. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'10), pages 1190-1197, 2010. Google Scholar
  11. David L. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289-1306, 2006. Google Scholar
  12. Anna C. Gilbert and Piotr Indyk. Sparse recovery using sparse matrices. Proceedings of IEEE, 98(6):937-947, 2010. Google Scholar
  13. Anna C. Gilbert, Martin J. Strauss, Joel A. Tropp, and Roman Vershynin. One sketch for all: fast algorithms for compressed sensing. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC 2007), pages 237-246, 2007. Google Scholar
  14. Piotr Indyk and Ilya Razenshteyn. On model-based RIP-1 matrices. In Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP'13), pages 564-575, 2013. Google Scholar
  15. Kumar Joag-Dev and Frank Proschan. Negative association of random variables with applications. Annals of Statistics, 11(1):286-295, 1983. Google Scholar
  16. Raghunandan M. Kainkaryam, Angela Bruex, Anna C. Gilbert, John Schiefelbein, and Peter J. Woolf. poolMC: Smart pooling of mRNA samples in microarray experiments. BMC Bioinformatics, 11(299), 2010. Google Scholar
  17. Rafał Latała. Estimation of moments of sums of independent real random variables. Annals of Probability, 25(3):1502-1513, 1997. Google Scholar
  18. James R. Lee, Manor Mendel, and Assaf Naor. Metric structures in L₁: dimension, snowflakes, and average distortion. European Journal of Combinatorics, 26(8):1180-1190, 2005. Google Scholar
  19. S. Muthukrishnan. Data streams: Algorithms and applications. Foundations and Trends in Theoretical Computer Science, 1(2):117-236, 2005. Google Scholar
  20. Mergen Nachin. Lower bounds on the column sparsity of sparse recovery matrices. undergraduate thesis, MIT, 2010. Google Scholar
  21. A.V. Nagaev. Integral limit theorems taking large deviations into account when Cramér’s condition does not hold. I. Theory of Probability and Its Applications, 14(1):51-64, 1969. Google Scholar
  22. A.V. Nagaev. Integral limit theorems taking large deviations into account when Cramér’s condition does not hold. II. Theory of Probability and Its Applications, 14(2):193-208, 1969. Google Scholar
  23. Jelani Nelson and Huy L. Nguyễn. Sparsity lower bounds for dimensionality reducing maps. In Proceedings of the 45th ACM Symposium on the Theory of Computing (STOC'13), pages 101-110, 2013. Google Scholar
  24. Holger Rauhut. Compressive sensing and structured random matrices. Theoretical foundations and numerical methods for sparse recovery, 9:1-92, 2010. Google Scholar
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