Leveraging recent advances in additive combinatorics, we exhibit explicit matrices satisfying the Restricted Isometry Property with better parameters. Namely, for $varepsilon=3.26cdot 10^{-7}$, large $k$ and $k^{2-varepsilon} le Nle k^{2+varepsilon}$, we construct $n times N$ RIP matrices of order $k$ with $k = Omega( n^{1/2+varepsilon/4} )$.
Download