Title :
Certifying the Restricted Isometry Property is Hard
Author :
Bandeira, Afonso S. ; Dobriban, E. ; Mixon, Dustin G. ; Sawin, W.F.
Author_Institution :
Program in Appl. & Comput. Math., Princeton Univ., Princeton, NJ, USA
Abstract :
This paper is concerned with an important matrix condition in compressed sensing known as the restricted isometry property (RIP). We demonstrate that testing whether a matrix satisfies RIP is NP-hard. As a consequence of our result, it is impossible to efficiently test for RIP provided P ≠ NP.
Keywords :
computational complexity; matrix algebra; NP-hard; RIP; important matrix condition; restricted isometry property; Complexity theory; Compressed sensing; Educational institutions; Polynomials; Sparks; Testing; Compressed sensing; computational complexity; restricted isometry property;
Journal_Title :
Information Theory, IEEE Transactions on
DOI :
10.1109/TIT.2013.2248414
