NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
Paper ID: 6848 Random Quadratic Forms with Dependence: Applications to Restricted Isometry and Beyond

### Reviewer 1

Originality: I believe the results in the paper are novel, I am not aware of other works for uniform large deviation bounds for random quadratic forms, where the random entries form a MDS. The main tools used - namely decoupling and chaining - are standard tools for deriving such bounds when the random entries are independent, but the paper extends them in a novel way to handle MDSs. Clarity: I found the paper to be well written in general, with the notation well defined, and was able to follow the arguments in the main text. I have some minor comments regarding typos and some technical questions. The list of typos mentioned below is not complete and I would suggest that the authors make another careful pass of the paper (including the supplementary material) to flush out other typos. 1) In line 30, it would be good to explain what the notation “vec(A)” means (i.e., how is the vector constructed exactly). 2) Line 82: typo in definition of (2,\infty) norm. 3) Line 84: “second class in..” -> “second class is..” 4) Line 85: “literature have used…” -> “literature has used…” 5) In lines 94-96, you explain that Hanson Wright inequality is for a fixed matrix, while you consider a uniform bound over a set of matrices. Still, if \mathcal{A} is a compact set, couldn’t one use a naive union bound argument over a cover of \mathcal{A}? 6) Line 99: empty bracket [] appears after [19,31]. 7) Line 147: missing comma between references. 8) Line 156: I could not verify why \eta_j is a sub-Gaussian MDS (I can see the sub-Gaussian part, but not the MDS-2 condition), this could be explained in a footnote. Same comment for \eta_j in line 164. 9) Line 158: “…be an bounded” -> “…be a bounded…” 10) Line 199: I don’t understand why there is a sup and inf (over u \in \mathcal{A}) in the definition of RIP? Moreover, \delta_s is defined as the smallest constant in (0,1) for which eq. (22) holds (hence it is well defined), see for eg. the book “Mathematical Introduction to Compressive Sensing” by Foucart and Rauhut for a precise definition. 11) Corollary 1 has the notation vec(X) in the statement which has not yet been defined. 12) In line 227, shouldn’t we have d_{F}(\mathcal{A}) = 1? Similarly, shouldn’t we have d_{2->2} (\mathcal{A}) = 1/\sqrt{n} ? Also, in line 230, \norm{\theta}_2^2 should be replaced with 1. It would also help to inform the reader that the unit norm assumption is w.l.o.g. 13) Line 235: should be “…sequence of x_i’s…”; line 238 should be: “… our result provides a tool…” ; line 239: should be “…that is obtained…” 14) Line 242: should be “…and are a desirable alternative to random matrices with i.i.d entries…” 15) Line 253 has an incomplete sentence; this needs to be fixed. Quality: I haven’t been able to check the proofs in detail as they are all confined to the supplementary material and are fairly long and tedious. It will certainly help if the (top level) proof outline for bounding the L_p norms of the two terms in eq. (6) could be provided in the main text. I feel this is important, as this is really the main crux of this paper. Significance: I feel that the bounds obtained in this paper have the potential of being useful in a number of problem settings where the data is obtained sequentially or adaptively, and thus contains statistical dependencies with the past observations. So, I am quite positive that the results will be of interest to researchers in high dimensional statistics, compressed sensing and randomized linear algebra.