Certifying the restricted isometry property is hard

Before I start, here’s the plug: This blog entry is all about a recent paper of the same name that I wrote with Afonso, Edgar and Will. 🙂

Everyone who’s familiar with compressed sensing knows about the restricted isometry property (RIP). Recently, I blogged about the significance of RIP, but its popularity is perhaps mostly due to the intuition it provides for good sensing matrices. Indeed, a short, fat matrix is RIP if it acts as a near-isometry on sufficiently sparse vectors, meaning the columns of the matrix exhibit a higher level of incoherence; instead of pairwise incoherence, it has some sort of -wise incoherence, where is the desired sparsity level. Amazingly, this intuitive property allows us to efficiently find the sparsest vector that satisfies , which is otherwise a combinatorial -norm minimization problem.

Oftentimes, random processes are used to produce RIP matrices. Deterministic matrices can also be used, but to date, they can only provably admit much smaller sparsity levels. Since random matrices are so frequently RIP (they are with high probability), it would be nice to at least be able to verify this property. The naive approach is to test every submatrix of columns of , but there are way too many of such matrices. An efficient algorithm would likely account for much deeper relationships between singular values of distinct submatrices, but many in the community have presumed that no such algorithm exists. Here’s a small sample of quotes related to the difficulty of verifying RIP (aka UUP):

• “An alternate approach, and one of interest in its own right, is to work on improving the time it takes to verify that a given matrix (possibly one of a special form) obeys the UUP.” – Tao
• “It is important to note that verifying the RIP may be a difficult task.” – Baraniuk, Davenport, DeVore and Wakin
• “Although it is known that certain probabilistic processes generate matrices that satisfy RIP with high probability, there is no practical algorithm for verifying whether a given sensing matrix has this property…” – Calderbank, Howard and Jafarpour
• “…testing these conditions on generic matrices is potentially harder than solving the combinatorial -norm minimization problem…” – d’Aspremont and El Karoui

The last quote is particularly interesting. To be clear, Natarajan showed that it’s NP-hard to find the sparsest such that , and so the quote of d’Aspremont and El Karoui can be reworded to say that the following conjecture is potentially true:

Conjecture. Given a matrix , , and a positive integer , it’s NP-hard to certify whether is -RIP.

Indeed, if the above conjecture were true, and moreover if (as is believed by the vast majority of computational complexity theorists), then there is no polynomial-time algorithm to test for RIP. This corresponds to the intuition shared by most of the compressed sensing community, but it would be nice to actually prove it!

Well, our paper almost does this, that is, we establish that no efficient RIP-testing algorithm exists provided . This is a slightly stronger complexity assumption than , but it’s nearly as widely believed. In fact, most believe that since randomized algorithms are expected to have deterministic counterparts through derandomization. To be more precise, our paper shows how any efficient algorithm to certify RIP can be called in an efficient randomized algorithm that solves the clique decision problem (which is NP-complete). As such, we say RIP certification is “hard for NP under randomized polynomial-time reductions.” If derandomization is possible (i.e., ), then our paper shows that RIP certification is NP-hard.

The proof (or more specifically, the reduction) has three main steps. First, we invoke a 30-year-old reduction which maps the clique decision problem to matroid theory. This reduction shows that it’s NP-complete to determine the girth of a transversal matroid. Next, we invoke a more recent discovery that every transversal matroid is represented by a matrix of integer entries, and that a random choice for the matrix will successfully represent it with high probability (this is the only source of randomness in our reduction). This means that the girth of the transversal matroid, and hence the clique number of the original graph, can be tested using this matrix. The last step shows how to call an RIP-testing algorithm to evaluate the matrix and efficiently solve both problems.

If you’ve never read a proof in computational complexity, I recommend giving this paper a read. At the end, we give some ideas for how to directly prove the above conjecture without assuming the full power of the conjecture, but it appears to be hard, so to speak.