Stable Image Reconstruction Using Total Variation Minimization

This paper presents near-optimal guarantees for stable and robust image recovery from undersampled noisy measurements using total variation minimization. In particular, we show that from $O(s\log(N))$ nonadaptive linear measurements, an image can be reconstructed to within the best $s$-term approximation of its gradient up to a logarithmic factor, and this factor can be removed by taking slightly more measurements. Along the way, we prove a strengthened Sobolev inequality for functions lying in the null space of a suitably incoherent matrix.