A conditional construction of restricted isometries

Posted on by Dustin G. Mixon

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 p be a prime which is 1 mod 4. Consider the p\times p DFT matrix, and grab rows corresponding to the quadratic residues (i.e., perfect squares) modulo p. 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 \alpha>0, there exists \beta>0 such that

\displaystyle{\bigg|\sum_{a,b\in S}\bigg(\frac{a-b}{p}\bigg)\bigg|<|S|^{2-\beta}\qquad\forall S\subseteq\mathbb{F}_p,~|S|>p^\alpha}

for every sufficiently large prime p\equiv1\bmod4.

Conjecture B. The largest clique in the Paley graph of p vertices has o(\sqrt{p}) 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”

    1. 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.

      Reply

Leave a comment