License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SOCG.2015.451
URN: urn:nbn:de:0030-drops-51273
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5127/
Allen-Zhu, Zeyuan ;
Gelashvili, Rati ;
Razenshteyn, Ilya
Restricted Isometry Property for General p-Norms
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.
BibTeX - Entry
@InProceedings{allenzhu_et_al:LIPIcs:2015:5127,
author = {Zeyuan Allen-Zhu and Rati Gelashvili and Ilya Razenshteyn},
title = {{Restricted Isometry Property for General p-Norms}},
booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)},
pages = {451--460},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-83-5},
ISSN = {1868-8969},
year = {2015},
volume = {34},
editor = {Lars Arge and J{\'a}nos Pach},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5127},
URN = {urn:nbn:de:0030-drops-51273},
doi = {10.4230/LIPIcs.SOCG.2015.451},
annote = {Keywords: compressive sensing, dimension reduction, linear algebra, high-dimensional geometry}
}
Keywords: |
|
compressive sensing, dimension reduction, linear algebra, high-dimensional geometry |
Collection: |
|
31st International Symposium on Computational Geometry (SoCG 2015) |
Issue Date: |
|
2015 |
Date of publication: |
|
12.06.2015 |