  Compressed sensing seeks to invert an underdetermined linear system by
exploiting additional knowledge of the true solution. Over the last decade,
several instances of compressed sensing have been studied for various
applications, and for each instance, reconstruction guarantees are available
provided the sensing operator satisfies certain sufficient conditions. In this
paper, we completely characterize the sensing operators which allow uniformly
stable and robust reconstruction by convex optimization for many of these
instances. The characterized sensing operators satisfy a new property we call
the robust width property, which simultaneously captures notions of widths from
approximation theory and of restricted eigenvalues from statistical regression.
We provide a geometric interpretation of this property, we discuss its
relationship with the restricted isometry property, and we apply techniques
from geometric functional analysis to find random matrices which satisfy the
property with high probability.
