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.
3 thoughts on “A conditional construction of restricted isometries”
How is your paper related to “Explicit constructions of RIP matrices and related problems” by Bourgain, Dilworth, Ford, Konyagin and Kutzarova?
The constructions are very different, but both improve over the square-root bottleneck (and no other construction with this performance is known to date). Notably, the construction of Bourgain et al. doesn’t assume any conjecture in number theory, unlike ours.
Ah, nevermind, for a second I thought that your paper does not cite it…