A conditional construction of restricted isometries

I have a recent paper on the arXiv with Afonso Bandeira and Joel Moreira that provides a deterministic RIP matrix which breaks the square-root bottleneck, conditional on a folklore conjecture in number theory.

Here’s the construction (essentially): Let be a prime which is 1 mod 4. Consider the DFT matrix, and grab rows corresponding to the quadratic residues (i.e., perfect squares) modulo . This construction was initially suggested in this paper. We already know that partial Fourier matrices break the square-root bottleneck if the rows are drawn at random, so our result corresponds to the intuition that quadratic residues exhibit some notion of pseudorandomness.

There are actually two folklore conjectures at play in our paper. Conjecture A implies that this matrix breaks the square-root bottleneck, which in turn implies Conjecture B:

Conjecture A (Conjecture 2.2 in this paper). For each , there exists such that

for every sufficiently large prime .

Conjecture B. The largest clique in the Paley graph of vertices has vertices.

Unfortunately, Conjecture A is considered to be very difficult. On the other hand, so is Conjecture B; this paper provides the state of the art. As such, you can expect this matrix to break the square-root bottleneck, but good luck proving it.