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.APPROX-RANDOM.2014.371
URN: urn:nbn:de:0030-drops-47092
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4709/
Natarajan, Abhiram ;
Wu, Yi
Computational Complexity of Certifying Restricted Isometry Property
Abstract
Given a matrix A with n rows, a number k < n, and 0 < delta < 1, A is (k,delta)-RIP (Restricted Isometry Property) if, for any vector x in R^n, with at most k non-zero co-ordinates, (1-delta)|x|^2 <= |Ax|^2 <= (1+delta)|Ax|^2. In many applications, such as compressed sensing and sparse recovery, it is desirable to construct RIP matrices with a large k and a small delta;. Given the efficacy of random constructions in generating useful RIP matrices, the problem of certifying the RIP parameters of a matrix has become important. In this paper, we prove that it is hard to approximate the RIP parameters of a matrix assuming the Small-Set-Expansion-Hypothesis. Specifically, we prove that for any arbitrarily large constant C>0 and any arbitrarily small constant 0<delta<1, there exists some k such that given a matrix M, it is SSE-Hard to distinguish the following two cases: i) (Highly RIP) M is (k,delta)-RIP; ii) (Far away from RIP) M is not (k/C,1-delta)-RIP.
Most of the previous results on the topic of hardness of RIP certification only hold for certification when delta=o(1). In practice, it is of interest to understand the complexity of certifying a matrix with delta being close to sqrt(2) - 1, as it suffices for many real applications to have matrices with delta=sqrt(2)-1. Our hardness result holds for any constant delta. Specifically, our result proves that even if delta is indeed very small, i.e. the matrix is in fact strongly RIP, certifying that the matrix exhibits weak RIP itself is SSE-Hard.
In order to prove the hardness result, we prove a variant of the Cheeger's Inequality for sparse vectors.
BibTeX - Entry
@InProceedings{natarajan_et_al:LIPIcs:2014:4709,
author = {Abhiram Natarajan and Yi Wu},
title = {{Computational Complexity of Certifying Restricted Isometry Property}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
pages = {371--380},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-74-3},
ISSN = {1868-8969},
year = {2014},
volume = {28},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4709},
URN = {urn:nbn:de:0030-drops-47092},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.371},
annote = {Keywords: Restricted Isometry Property, RIP, RIP Certification, Sparse Cheeger Inequality, SSE Hard}
}
|
Keywords: |
|
Restricted Isometry Property, RIP, RIP Certification, Sparse Cheeger Inequality, SSE Hard |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) |
|
Issue Date: |
|
2014 |
|
Date of publication: |
|
04.09.2014 |
