Computational Complexity of Certifying Restricted Isometry Property

Given a matrix $A$ with $n$ rows, a number $k<n$, and $0<\delta <1$, $A$ is $(k,\delta )$-RIP (Restricted Isometry Property) if, for any vector $x \in $\mathbb{R}$^n$,withatmost$k$non-zeroco-ordinates,$$(1-\delta) |x|_2 \leq |A x|_2 \leq (1+\delta)|x|_2$$ In many applications, such as compressed sensing and sparse recovery, it is desirable to construct RIP matrices with a large $k$ and a small $\delta$. Given the efficacy of random constructions in generating useful RIP matrices, the problem of certifying the RIP parameters of a matrix has become important. In this paper, we prove that it is hard to approximate the RIP parameters of a matrix assuming the Small-Set-Expansion-Hypothesis. Specifically, we prove that for any arbitrarily large constant $C>0$ and any arbitrarily small constant $0<\delta <1$, there exists some $k$ such that given a matrix $M$, it is SSE-Hard to distinguish the following two cases:

• (Highly RIP) $M$ is $(k,\delta )$-RIP.
• (Far away from RIP) $M$ is not $(k\mathrm{/}C,1-\delta )$-RIP. Most of the previous results on the topic of hardness of RIP certification only hold for certification when $\delta =o(1)$. In practice, it is of interest to understand the complexity of certifying a matrix with $\delta$ being close to $\sqrt{2}-1$, as it suffices for many real applications to have matrices with $\delta =\sqrt{2}-1$. Our hardness result holds for any constant $\delta$. Specifically, our result proves that even if $\delta$ is indeed very small, i.e. the matrix is in fact \emph{strongly RIP}, certifying that the matrix exhibits \emph{weak RIP} itself is SSE-Hard. In order to prove the hardness result, we prove a variant of the Cheeger’s Inequality for sparse vectors.