2026-07-24T18:14:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5127 2024-03-06T10:35:54Z ddc:004 open_access

Restricted Isometry Property for General p-Norms Allen-Zhu, Zeyuan Gelashvili, Rati Razenshteyn, Ilya compressive sensing dimension reduction linear algebra high-dimensional geometry 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zeyuan Allen-Zhu and Rati Gelashvili and Ilya Razenshteyn 2015 Is Part Of LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SOCG.2015.451 urn:nbn:de:0030-drops-51273 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.451 eng https://creativecommons.org/licenses/by/3.0/legalcode