Restricted isometry property

Summary

A matrix has the restricted isometry property of order $s$ when it nearly preserves the length of every vector with at most $s$ nonzero entries. The size of the distortion is measured by the restricted isometry constant $\delta_s$. If $\delta_{2s}$ is small, $s$-sparse vectors can be recovered stably from their images by $\ell^1$ minimization. This is the basis of compressed sensing. Computing $\delta_s$ exactly is hard, but random Gaussian matrices have small constants with high probability.