Explicit RIP matrices: an update
Leveraging recent advances in additive combinatorics, we exhibit explicit matrices satisfying the Restricted Isometry Property with better parameters. Namely, for ε=3.26· 10^-7, large k and k^2-ε≤ N≤ k^2+ε, we construct n × N RIP matrices of order k with k = Ω( n^1/2+ε/4 ).
READ FULL TEXT