Explicit Construction of RIP Matrices Is Ramsey‐Hard. Issue 9 (11th November 2019)

• Record Type: Journal Article
• Authors: Gamarnik, David
• Is Part Of: Communications on pure and applied mathematics. Volume 73:Issue 9(2020:Sep.)
• Page Start: 2043
• Page End: 2048
• Publication Date: 2019-11-11
• Subjects: Mathematics -- Periodicals; Mechanics -- Periodicals; Mathématiques -- Périodiques; Mécanique -- Périodiques; 510.5
• DOI: 10.1002/cpa.21873
• Languages: English
• ISSNs: 0010-3640

Abstract

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.