Explicit constructions of RIP matrices and related problems
Explicit constructions of RIP matrices and related problems
We give a new explicit construction of n×N matrices satisfying the Restricted Isometry Property (RIP). Namely, for some ϵ>0, large N, 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 …