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.

Dear Dustin,

I came across your above-mentioned work while Marc Pfetsch and I were independently investigating complexity issues in compressed sensing. It seems it was about time that McCormick’s (or, Stockmeyer’s) result resurfaces — it in fact implies the NP-hardness of computing the spark of a matrix, i.e., the girth of a vector matroid, as well as that of a transversal matroid. It is always mentioned that spark is NP-hard, but it seems no one ever gave a reference for this… well, McCormick it is 🙂

Consequently, in a way, your result can indeed be “derandomized”, by taking the vector matroid perspective instead of transversal matroids; see http://arxiv.org/abs/1205.2081

I also noted your thesis is now in the arxiv, I’ll be sure to check it out.

Cheers,

Andreas

Very nice! I haven’t read the paper too carefully, but your reduction appears to directly map the clique decision problem to short, fat matrices, bypassing transversal matroids altogether and thereby removing the need for randomness in the matroid-to-matrix step. It’s interesting how it seems particularly difficult to derandomize this last leg of my argument, and yet you can apparently derandomize the entire argument with a little ingenuity. Indeed, your direct map builds matrices which have the same nonzero entry locations as mine, but you manage to pick the entries deterministically—though your procedure doesn’t seem to represent general transversal matroids.

Yes, McCormick/Stockmeyer’s construction was left pretty general, although their original proof implicitly works with the “matching property”. It seems that they had transversal matroids in mind. We worked around this property, filling the upper part of the matrix with the actual incidence matrix, and then invoking some technical arguments about size and rank of incidence matrices (of subgraphs) to achieve the desired connection between cliques and circuits in the general vector (not transversal) matroid sense. It’s all connected via the original proof from McCormick’s thesis, but the details can turn somewhat tricky with either approach.

It would be interesting if the “rationality gap” can be used (constructively) to show NP-hardness of the decision problems “Is Phi (K,delta)-RIP with delta<d?" with some

fixed/given d<1. Maybe one can make use of how the RIP is not invariant to scaling by

regular matrices (Ax=b iff GAx=Gb for any regular G, but the RIP behavior of A and GA can differ wildly).