Satisfying the Restricted Isometry Property with the Optimal Number of Rows and Slightly Less Randomness

A matrix $\mathrm{\Phi }\in {\mathbb{R}}^{Q\times N}$ satisfies the restricted isometry property if $\mathrm{\parallel }\mathrm{\Phi }x{\mathrm{\parallel }}_2^2$ is approximately equal to $\mathrm{\parallel }x{\mathrm{\parallel }}_2^2$ for all $k$-sparse vectors $x$. We give a construction of RIP matrices with the optimal $Q=O(k\log (N\mathrm{/}k))$ rows using $O(k\log (N\mathrm{/}k)\log (k))$ bits of randomness. The main technical ingredient is an extension of the Hanson-Wright inequality to $\epsilon$-biased distributions.