Document Type
Article
Department
Mathematics (CMC)
Publication Date
5-22-2013
Abstract
Consider the problem of reconstructing a multidimensional signal from an underdetermined set of measurements, as in the setting of compressed sensing. Without any additional assumptions, this problem is ill-posed. However, for signals such as natural images or movies, the minimal total variation estimate consistent with the measurements often produces a good approximation to the underlying signal, even if the number of measurements is far smaller than the ambient dimensionality. This paper extends recent reconstruction guarantees for two-dimensional images x ∈ ℂN2 to signals x ∈ ℂNd of arbitrary dimension d ≥ 2 and to isotropic total variation problems. In this paper, we show that a multidimensional signal x ∈ ℂNd can be reconstructed from O(s dlog(Nd)) linear measurements y = Ax using total variation minimization to a factor of the best s-term approximation of its gradient. The reconstruction guarantees we provide are necessarily optimal up to polynomial factors in the spatial dimension d.
Rights Information
© 2013 IEEE
Terms of Use & License Information
DOI
10.1109/TIP.2013.2264681
Recommended Citation
Needell, D., Ward, R., "Near-optimal compressed sensing guarantees for total variation minimization", IEEE Transactions on Image Processing, vol. 22, iss. 10, pp. 3941 - 3949, 2013. doi: 10.1109/TIP.2013.2264681
