Conditional Restricted Isometries

We have finally made (conditional) progress on the Paley ETF conjecture! Joel, Dustin, and I just uploaded our paper “A conditional construction of restricted isometries” to the arxiv. The conjecture states that a particularly simple deterministic construction, the Paley ETF (see below), satisfies the restricted isometry property past the squareroot bottleneck, we were able to establish this conditional on a folklore number theory conjecture.

Let $latex K \leq M \leq N$ be positive integers and let . An matrix is said to satisfy the -restricted isometry property (RIP) if

whenever  has at most nonzero entries (i.e., x is a -sparse vector). RIP matrices are very important in sparse recovery as they are known to allow for recovery of a sparse vector from very few, , linear measurements. It is known that several random matrices satisfy RIP for . On the other hand, guarantees on deterministic constructions have a tendency of not going beyond , which has been commonly referred to as the squareroot bottleneck.

The problem of building deterministic RIP matrices that break the squareroot bottleneck was posed by Terry Tao in his blog more than 7 years ago. Since then, only one deterministic construction is known to break this bottleneck, due to Bourgain et al.. Although a groundbreaking result, their construction is a fairly complicated and the improvement is only slight, when compared to the performance of random constructions (Dustin has a nice expository chapter on it).

On the other hand, the Paley ETF construction is remarkably simple, it essentially consists of a partial discrete fourier transform matrix (of prime order ) where one selects the rows that correspond to quadratic residues module . The rough intuition for such a construction is also simple: If the rows had been selected at random it would be known that the resulting matrix is RIP (for) with high probability, and the quadratic residues modulo a prime are known to behave random-like in several instances.

In this paper, we were able to sandwich the conjecture that the Paley ETF breaks the squareroot bottleneck (from now on, referred to as Paley ETF conjecture) between two number theory conjectures. We show that a folklore conjecture in Number Theory (Conjecture 2.2 in this paper) implies the Paley ETF conjecture. On the other hand, the Paley ETF conjecture implies the Paley Clique conjecture, a statement about the clique number of a Paley graph that is widely believed in Number Theory.

If one believe that these two Number Theory conjectures are true and very difficult to prove (as otherwise they would probably be theorems), then one can see our result as saying that the Paley ETF is indeed true but also very difficult to prove!

Advertisement