 Sharp order-s restricted-isometry recovery theorem

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.