We give a new explicit construction of n×N matrices satisfying the Restricted Isometry Property (RIP). Namely, for someε > 0, largeN, and any n satisfyingN1−ε ≤ n ≤ N, we construct RIP matrices of order k ≥ n1/2+ε and constant δ = n−ε. This overcomesthe natural barrier k = O(n1/2) for proofs based on small coherence, which areused in all previous explicit constructions of RIP matrices. Key ingredients in ourproof are new estimates for sumsets in product sets and for exponential sums with theproducts of sets possessing special additive structure. We also give a construction ofsets of n complex numbers whose kth moments are uniformly small for 1 ≤ k ≤ N(Tur´an’s power sum problem), which improves upon known explicit constructionswhen (logN)1+o(1) ≤ n ≤ (logN)4+o(1). This latter construction produces elementary explicit examples of n×N matrices that satisfy the RIP and whose columns constitute anew spherical code; for those problems the parameters closely match those of existingconstructions in the range (logN)1+o(1) ≤ n ≤ (logN)5/2+o(1).
Published in Duke Mathematical Journal, Volume 159, Issue 1, 2011, pages 145-185.
Bourgain, J., Dilworth, S. J., Ford, K., Konyagin, S., & Kutzarova, D. (2011). Explicit Constructions of RIP Matrices and Related Problems. Duke Mathematical Journal, 159 (1), 145-185.
©Duke Mathematical Journal 2011, Duke University Press