Paper Info
Title
Hidden Cliques and the Certification of the Restricted Isometry Property.
Abstract
Compressed sensing is a technique for finding sparse solutions to underdetermined linear systems. This technique relies on properties of the sensing matrix such as the restricted isometry property. Sensing matrices that satisfy this property with optimal parameters are mainly obtained via probabilistic arguments. Deciding whether a given matrix satisfies the restricted isometry property is a non-trivial computational problem. Indeed, we show in this paper that restricted isometry parameters cannot be approximated in polynomial time within any constant factor under the assumption that the hidden clique problem is hard. Moreover, on the positive side we propose an improvement on the brute-force enumeration algorithm for checking the restricted isometry property.
Year
DOI
Venue
2012
10.1109/TIT.2014.2331341
IEEE Transactions on Information Theory
Keywords
DocType
Volume
compressed sensing,computational complexity,sparse matrices,compressed sensing,hidden clique problem,probabilistic arguments,restricted isometry property certification,sensing matrix,underdetermined linear systems,Compressed sensing,computational complexity,hidden clique problem,restricted isometry property
Journal
60
Issue
ISSN
Citations 
8
0018-9448
11
PageRank 
References 
Authors
0.72
11
2
Name
Order
Citations
PageRank
Pascal Koiran1919113.85
Anastasios Zouzias219314.06