{
  "id": "1805.11238",
  "version": "v1",
  "published": "2018-05-29T04:09:10.000Z",
  "updated": "2018-05-29T04:09:10.000Z",
  "title": "Explicit construction of RIP matrices is Ramsey-hard",
  "authors": [
    "David Gamarnik"
  ],
  "comment": "4 pages",
  "categories": [
    "math.PR",
    "cs.IT",
    "math.IT",
    "stat.CO"
  ],
  "abstract": "Matrices $\\Phi\\in\\R^{n\\times 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 construction of such matrices defied the repeated efforts, and the most known approaches hit the so-called $\\sqrt{n}$ sparsity bottleneck. The notable exception is the work by Bourgain et al \\cite{bourgain2011explicit} constructing an $n\\times p$ RIP matrix with sparsity $s=\\Theta(n^{{1\\over 2}+\\epsilon})$, but in the regime $n=\\Omega(p^{1-\\delta})$. In this short note we resolve this open question in a sense by showing that an explicit construction of a matrix satisfying the RIP in the regime $n=O(\\log^2 p)$ and $s=\\Theta(n^{1\\over 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 extremal combinatorics which has been open for decades.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-05-29T04:09:10.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "explicit construction",
      "rip matrix",
      "ramsey-hard",
      "random matrices satisfy",
      "three-colored ramsey graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 4,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}