@inproceedings{7f66c9a711ca484c97072e5d177231a8,
title = "Breaking the k2 barrier for explicit RIP matrices",
abstract = "We give a new explicit construction of n x N matrices satisfying the Restricted Isometry Property (RIP). Namely, for some ε>0, large k and k2-ε ≤ N ≤ k2+ε, we construct RIP matrices of order k with n=O(k2-ε). This overcomes the natural barrier n >> k2 for proofs based on small coherence, which are used in all previous explicit constructions of RIP matrices. Key ingredients in our proof are new estimates for sumsets in product sets and for exponential sums with the products of sets possessing special additive structure.",
keywords = "compressed sensing, restricted isometry property",
author = "Jean Bourgain and Dilworth, {Stephen J.} and Kevin Ford and Konyagin, {Sergei V.} and Denka Kutzarova",
year = "2011",
doi = "10.1145/1993636.1993721",
language = "English (US)",
isbn = "9781450306911",
series = "Proceedings of the Annual ACM Symposium on Theory of Computing",
publisher = "Association for Computing Machinery",
pages = "637--644",
booktitle = "STOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing",
address = "United States",
note = "43rd ACM Symposium on Theory of Computing, STOC 2011 ; Conference date: 06-06-2011 Through 08-06-2011",
}