Explicit Construction of RIP Matrices Is Ramsey‐Hard
Author(s)
Gamarnik, David
DownloadSubmitted version (107.3Kb)
Open Access Policy
Open Access Policy
Creative Commons Attribution-Noncommercial-Share Alike
Terms of use
Metadata
Show full item recordAbstract
© 2019 Wiley Periodicals, Inc. 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 = logO(1)p, the explicit deteministic construction of such matrices defied the repeated efforts, and most of the known approaches hit the so-called (Formula presented.) sparsity bottleneck. The notable exception is the work by Bourgain et al. constructing an n × p RIP matrix with sparsity s = Θ(n1/2 + ϵ), but in the regime n = Ω(p1 − δ). 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(log2p) and s = Θ(n1/2) implies an explicit construction of a three-colored Ramsey graph on p nodes with clique sizes bounded by O(log2p) — a question in the field of extremal combinatorics that has been open for decades. © 2019 Wiley Periodicals, Inc.
Date issued
2020Department
Massachusetts Institute of Technology. Department of MathematicsJournal
Communications on Pure and Applied Mathematics
Publisher
Wiley