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

Shravas Rao

A matrix $\Phi \in {\mathbb{R}}^{Q\times N}$ satisfies the restricted isometry property if $\Vert \Phi x{\Vert }_2^2$ is approximately equal to $\Vert x{\Vert }_2^2$ for all $k$-sparse vectors $x$. We give a c…