Certifying the restricted isometry property is hard

I Introduction

It is now well known that compressed sensing offers a method of taking few sensing measurements of high-dimensional sparse vectors, while at the same time enabling efficient and stable reconstruction . In this field, the restricted isometry property is arguably the most popular condition to impose on the sensing matrix in order to acquire state-of-the-art reconstruction guarantees:

We say a matrix $\Phi$ satisfies the $(K,\delta)$-restricted isometry property (RIP) if

for every vector $x$ with at most $K$ nonzero entries.

To date, RIP-based reconstruction guarantees exist for Basis Pursuit , CoSaMP and Iterative Hard Thresholding , and the ubiquitous utility of RIP has made the construction of RIP matrices a subject of active research –. Here, random matrices have found much more success than deterministic constructions , but this success is with high probability, meaning there is some (small) chance of failure in the construction. Furthermore, RIP is a statement about the conditioning of all $\binom{N}{K}$ submatrices of an $M\times N$ sensing matrix, and so it seems computationally intractable to check whether a given instance of a random matrix fails to satisfy RIP; it is widely conjectured that certifying RIP for an arbitrary matrix is ${\mathsf{NP}}$-hard. In the present paper, we prove this conjecture.

Given a matrix $\Phi$, a positive integer $K$, and some $\delta\in(0,1)$, does $\Phi$ satisfy the $(K,\delta)$-restricted isometry property?

In short, we show that any efficient method of solving Problem 2 can be called in an algorithm that efficiently solves the ${\mathsf{NP}}$-complete subset sum problem. As a consequence of our result, there is no method by which one can efficiently test for RIP provided ${\mathsf{P}}\neq{\mathsf{NP}}$. This contrasts with previous work , in which the reported hardness results are based on less-established assumptions on the complexity of dense subgraph problems.

In the next section, we review the basic concepts we will use from computational complexity, and Section 3 contains our main result.

II A brief review of computational complexity

In complexity theory, problems are categorized into complexity classes according to the amount of resources required to solve them. For example, the complexity class ${\mathsf{P}}$ contains all problems which can be solved in polynomial time, while problems in ${\mathsf{EXP}}$ may require as much as exponential time. Problems in ${\mathsf{NP}}$ have the defining quality that solutions can be verified in polynomial time given a certificate for the answer. As an example, the graph isomorphism problem is in ${\mathsf{NP}}$ because, given an isomorphism between graphs (a certificate), one can verify that the isomorphism is legitimate in polynomial time. Clearly, ${\mathsf{P}}\subseteq{\mathsf{NP}}$, since we can ignore the certificate and still solve the problem in polynomial time.

While problem categories provide one way to describe complexity, another important tool is the polynomial-time reduction, which allows one to show that a given problem is “more complex” than another. To be precise, a polynomial-time reduction from problem $A$ to problem $B$ is a polynomial-time algorithm that solves problem $A$ by exploiting an oracle which solves problem $B$; the reduction indicates that solving problem $A$ is no harder than solving problem $B$ (up to polynomial factors in time), and we say “$A$ reduces to $B$,” or $A\leq B$. Such reductions lead to some of the most popular definitions in complexity theory: We say a problem $B$ is called ${\mathsf{NP}}$-hard if every problem $A$ in ${\mathsf{NP}}$ reduces to $B$, and a problem is called ${\mathsf{NP}}$-complete if it is both ${\mathsf{NP}}$-hard and in ${\mathsf{NP}}$. In plain speak, ${\mathsf{NP}}$-hard problems are harder than every problem in ${\mathsf{NP}}$, while ${\mathsf{NP}}$-complete problems are the hardest of problems in ${\mathsf{NP}}$.

Contrary to popular intuition, ${\mathsf{NP}}$-hard problems are not merely problems that seem to require a lot of computation to solve. Of course, ${\mathsf{NP}}$-hard problems have this quality, as an ${\mathsf{NP}}$-hard problem can be solved in polynomial time only if ${\mathsf{P}}={\mathsf{NP}}$; this is an open problem, but it is widely believed that ${\mathsf{P}}\neq{\mathsf{NP}}$ . However, there are other problems which seem hard but are not known to be ${\mathsf{NP}}$-hard (e.g., the graph isomorphism problem). As such, while testing for RIP in the general case seems to be computationally intensive, it is not obvious whether the problem is actually ${\mathsf{NP}}$-hard. Indeed, by the definition of ${\mathsf{NP}}$-hard, one must compare its complexity to the complexity of every problem in ${\mathsf{NP}}$. To this end, notice that $A\leq B$ and $B\leq C$ together imply $A\leq C$, and so to demonstrate that a problem $C$ is ${\mathsf{NP}}$-hard, it suffices to show that $B\leq C$ for some ${\mathsf{NP}}$-hard problem $B$.

In the present paper, we demonstrate the hardness of certifying RIP by reducing from the following problem:

Given a matrix $\Psi$ and some positive integer $K$, do there exist $K$ columns of $\Psi$ which are linearly dependent?

Problem 3 has a brief history in computational complexity. First, McCormick demonstrated that the analogous problem of testing the girth of a transversal matroid is ${\mathsf{NP}}$-complete, and so by invoking the randomized matroid representation of Marx , Problem 3 is hard for ${\mathsf{NP}}$ under randomized reductions . Next, Khachiyan showed that the problem is ${\mathsf{NP}}$-hard by focusing on the case where $K$ equals the number of rows of $\Psi$; using a particular matrix construction with Vandermonde components, he reduced this instance of the problem to the subset sum problem. Recently, Tillmann and Pfetsch used ideas similar to McCormick’s to strengthen Khachiyan’s result: they prove Problem 3 is ${\mathsf{NP}}$-hard without focusing on such a specific instance of the problem. Each of these complexity results use $M\times N$ matrices with integer entries whose binary representations take $\leq p(M,N)$ bits for some polynomial $p$; we will exploit this feature in our proof.

III Main result

We are now ready to state the remainder of our reduction: For some value of $\delta$ (which we will determine later), ask the oracle if $\Phi$ is $(K,\delta)$-RIP; then

The remainder of this proof will demonstrate (i) and (ii).

It is important to note that Theorem 4 is a statement about testing for RIP in the worst case; this result does not rule out the existence of matrices for which RIP is easily verified (e.g., using coherence in conjunction with the Gershgorin circle theorem for small values of $K$ ).

References