Restricted isometry property

Remarks

Equivalently, $\delta_s = \max_S \norm{A_S^* A_S - I}_{2 \to 2}$, where $S$ runs over the sets of at most $s$ column indices, $A_S$ keeps the columns in $S$, and the norm is the spectral matrix norm. So $\delta_s$ bounds how far the eigenvalues of all the Gram matrices $A_S^* A_S$ are from $1$. Example: if the columns of $A$ are orthonormal, then $\norm{Ax}_2 = \norm{x}_2$ for all $x$, so $\delta_s = 0$ for every $s$. Non-example: suppose the first two columns of $A$ are equal. Then $x = e_1 - e_2$ is $2$-sparse with $Ax = 0$, so the left inequality needs $\delta \ge 1$, and $A$ has no restricted isometry property of order $2$. The constants increase with the order: $\delta_1 \le \delta_2 \le \cdots \le \delta_N$. If $\delta_{2s} < 1$, then distinct $s$-sparse vectors have distinct images, since their difference is $2s$-sparse.