TY - JOUR

T1 - Explicit constructions of rip matrices and related problems

AU - Bourgain, Jean

AU - Dilworth, Stephen

AU - Ford, Kevin

AU - Konyagin, Sergei

AU - Kutzarova, Denka

PY - 2011/7/15

Y1 - 2011/7/15

N2 - We give a new explicit construction of n×N matrices satisfying the Restricted Isometry Property (RIP). Namely, for some ε>0,largeN, and any n satisfying N1-ε ≤ n ≤ N, we construct RIP matrices of order k ≥ n1/2+ε and constant δ = n-ε. This overcomes the natural barrier k = O(n1/2) 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. We also give a construction of sets of n complex numbers whose kth moments are uniformly small for 1 ≤ k ≤ N (Turán's power sum problem), which improves upon known explicit constructions when (log N)1+o(1) ≤ n ≤ (log N)4+o(1). This latter construction produces elementary explicit examples of n×N matrices that satisfy the RIP and whose columns constitute a new spherical code; for those problems the parameters closely match those of existing constructions in the range (log N)1+o(1) ≤ n ≤ (log N)5/2+o(1).

AB - We give a new explicit construction of n×N matrices satisfying the Restricted Isometry Property (RIP). Namely, for some ε>0,largeN, and any n satisfying N1-ε ≤ n ≤ N, we construct RIP matrices of order k ≥ n1/2+ε and constant δ = n-ε. This overcomes the natural barrier k = O(n1/2) 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. We also give a construction of sets of n complex numbers whose kth moments are uniformly small for 1 ≤ k ≤ N (Turán's power sum problem), which improves upon known explicit constructions when (log N)1+o(1) ≤ n ≤ (log N)4+o(1). This latter construction produces elementary explicit examples of n×N matrices that satisfy the RIP and whose columns constitute a new spherical code; for those problems the parameters closely match those of existing constructions in the range (log N)1+o(1) ≤ n ≤ (log N)5/2+o(1).

UR - http://www.scopus.com/inward/record.url?scp=79959751399&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79959751399&partnerID=8YFLogxK

U2 - 10.1215/00127094-1384809

DO - 10.1215/00127094-1384809

M3 - Article

AN - SCOPUS:79959751399

VL - 159

SP - 145

EP - 185

JO - Duke Mathematical Journal

JF - Duke Mathematical Journal

SN - 0012-7094

IS - 1

ER -