Computer Science – Computational Complexity
Scientific paper
2011-03-25
Computer Science
Computational Complexity
21 pages, This version corrects a small typo at the end of the proof of Theorem 1
Scientific paper
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 the restricted isometry property with optimal parameters are mainly obtained via probabilistic arguments. Given any matrix, deciding whether it satisfies the restricted isometry property is a non-trivial computational problem. In this paper, we give reductions from dense subgraph problems to the certification of the restricted isometry property. This gives evidence that certifying the restricted isometry property is unlikely to be feasible in polynomial-time. Moreover, on the positive side we propose an improvement on the brute-force enumeration algorithm for checking the restricted isometry property. Another contribution of independent interest is a spectral algorithm for certifying that a random graph does not contain any dense k-subgraph. This "skewed spectral algorithm" performs better than the basic spectral algorithm in a certain range of parameters.
Koiran Pascal
Zouzias Anastasios
No associations
LandOfFree
On the Certification of the Restricted Isometry Property does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the Certification of the Restricted Isometry Property, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Certification of the Restricted Isometry Property will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-571056