Explicit Construction of RIP Matrices Is Ramsey‐Hard. Issue 9 (11th November 2019) - Gamarnik, David
Abstract: Matrices Φ ∈ ℝ n × p satisfying the restricted isometry property (RIP) are an important ingredient of the compressive sensing methods. While it is known that random matrices satisfy the RIP with high probability even for n = log O (1) p, the explicit deteministic construction of such matrices defied the repeated efforts, and most of the known approaches hit the so‐called n sparsity bottleneck. The notable exception is the work by Bourgain et al. constructing an n × p RIP matrix with sparsity s = Θ ( n 1/2 + ϵ ), but in the regime n = Ω ( p 1 − δ ). In this short note we resolve this open question by showing that an explicit construction of a matrix satisfying the RIP in the regime n = O (log 2 p ) and s = Θ ( n 1/2 ) implies an explicit construction of a three‐colored Ramsey graph on p nodes with clique sizes bounded by O (log 2 p ) — a question in the field of extremal combinatorics that has been open for decades. © 2019 Wiley Periodicals, Inc.