This article 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 suitably incoherent matrices.
© 2013 Society for Industrial and Applied Mathematics
Needell, D., Ward, R., "Stable Image Reconstruction Using Total Variation Minimization," SIAM J. Imaging Sci., 6(2), 1035–1058, 2013. doi: 10.1137/120868281