Restricted isometry property

The restricted isometry property controls $\Vert Ax{\Vert }_2^2/\Vert x{\Vert }_2^2$ uniformly over sparse vectors. It supplies quantitative near-orthogonality of disjoint sparse coordinate combinations, not merely normalization of individual columns.

The order-s restricted isometry constant is the smallest nonnegative $\delta$ satisfying $(1-\delta )\Vert x{\Vert }_2^2\le \Vert Ax{\Vert }_2^2\le (1+\delta )\Vert x{\Vert }_2^2$ for every vector with at most $s$ nonzero coordinates. Equivalently it is ${\max }_{|S|\le s}\Vert A_S^{\ast }{A}_S-I{\Vert }_{2\to 2}$. The sparse-vector quantifier is essential, and the constant can equal zero.

For $s\ge 2$ and $\delta ={\delta }_s(A)<1/3$, noisy basis pursuit has error $\Vert \hat{x}-x_0{\Vert }_2\le C_1\eta +C_2{\sigma }_s(x_0)/\sqrt{s}$, with constants depending only on $\delta$. One admissible pair isThese constants follow from Theorem 3.3 of the sharp restricted-isometry recovery analysis, with the actual noise bounded by the tolerance $\eta$. The restriction $s\ge 2$ is necessary: equal unit columns give ${\delta }_1=0$ without unique recovery. The coefficient of the approximation term cannot universally be one.