Average-case hardness of RIP certification
The restricted isometry property (RIP) for design matrices gives guarantees for optimal recovery in sparse linear models. It is of high interest in compressed sensing and statistical learning. This property is particularly important for computationally efficient recovery methods. As a consequence, even though it is in general NP-hard to check that RIP holds, there have been substantial efforts to find tractable proxies for it. These would allow the construction of RIP matrices and the polynomial-time verification of RIP given an arbitrary matrix. We consider the framework of average-case certifiers, that never wrongly declare that a matrix is RIP, while being often correct for random instances. While there are such functions which are tractable in a suboptimal parameter regime, we show that this is a computationally hard task in any better regime. Our results are based on a new, weaker assumption on the problem of detecting dense subgraphs.
A matrix of size (n,p), whose coefficients are independently drawn from suitable random distributions, satisfies with high probability the RIP property with parameters k,t, provided that n >> k log p / (t*t). The question considered in this article is: is there a polynomial-time algorithm that, given such a random matrix, is able to certify, in at least 2/3 of the cases, that this matrix indeed satisfies RIP? The answer is known to be positive when n is of the order of (k*k) log p / (t*t). This article shows that, for any alpha < 1, there is a sequence of (n,k,t) going to infinity, such that n >> k^(1+alpha) / (t*t), for which no certifier exists. The result holds under the assumption that a problem of dense subgraph testing can also not be solved with relatively large probability in polynomial time, in a certain regime.
I think that the result of this article is interesting and elegant. I would be happy to see it published. However, the proofs, in the appendix, contain a number of typos that need to be corrected. There is also an inequality that I do not understand, at the end of the proof of the main theorem; I would appreciate additional explanations about it.  Regarding the presentation, I find the article well-written. I have two regrets, but they are relatively minor: - I think it would be better to underline before the very end of the article that the proof does not currently work in the regime n >> k^(1+alpha) and theta constant. - I would have liked the authors to give a general picture of the proof in the main part of the article, more detailed that the paragraph that follows Theorem 4.  Typos and remarks: - Line 16: "ee" -> "see". - Theorem (informal): I think the statement would be more clear with "for any alpha" at the beginning of the sentence. - Line 80: "an a" -> "a". - "measureable" -> "measurable" (appears twice). - Line 178: "lim" -> "lim inf". - Line 256: I think A_G has not been defined. - Lines 284/285, "shows through a reduction to the planted dense subgraph problem": this part of the sentence is not clear. - In the appendix, equation after line 9: "\approx" -> "<<" ? - Algorithm 1: I think the definition of k should appear before the one of l. - Line 14: the coefficients of X to not exactly have distribution \tilde Q, because of the averaging. - Equation after line 14: it does not necessarily go to zero. I think we only know that the lim sup is at most 1/3. - Line 15: the statement holds only "with high probability". - Equation after line 16: I do not think that the second part is necessarily true. You have to specify how you choose theta. - Equation after line 18: the lim inf must actually be zero. - Equation after line 23 should be broken in two lines. - Equation after line 34 is only valid for epsilon under some constant value. - Equation (3): I do not understand where the k comes from in the denominator, inside the exponential. - Line 46: shouldn't v be padded with zeros, so as to be of size p? - Equation after line 49: I think that the zero-norm of \tilde v should be replaced with the cardinality of \tilde S. - Equation after line 49 (this is the one that I do not understand): from what I understand, the authors use as a lower bound for the 1-norm the sum of Z^(a,b) v^(b). Is my understanding correct? Because then, aren't there cross terms Z^(a,b) v^(b')? - Line 53: I think the authors could give a slightly more detailed justification, because \tilde v and \tilde X are not independent. - Line 57: I think a l^2 is missing in the denominator. - Statement of Lemma 1: I think the three inequalities are in the wrong direction. I also have the impression that the right hand sides should be squared (because of the application of Chebyshev's inequality). - Equation after line 67: in the first line, the 'v' should be a 'u'. At the end, there should be only one dot. - Equation after line 78: the inequality should be reversed. - Equation after line 90: I think that there should not be a square in the right hand side. I also do not think that the second and third terms of the middle part can be directly majorized by 1/2 |u_J^TAu_J|. - Line 97: "O(n^2p)" -> "O(np^2)"? - Line 98: "lim" -> "lim inf". - Line 101: "and fact that" -> "and the fact that". - Equation after line 102: shouldn't the term in the exponential be divided by 4, as in the equation after line 85, where the denominator is 256, and not 64? - Line 107: "R" -> "mathbb{R}". - Lines 114 to 116: is b equal to mu? - Equation after line 127: I think that the second equality is an inequality. - Statement of Lemma 6, and last equation of the proof: I think (1-n^(1-gamma)) is (1-n^(1-gamma))^(-1). - Line 146: "smaller than ||U||_0" -> "smaller than ||U||_\infty". - Line 149: "any one" -> "any of the".