Near-optimal compressed sensing guarantees for total variation minimization
This provides theoretical guarantees for compressed sensing in high-dimensional domains like imaging and video, though it is an incremental extension of existing 2D results to arbitrary dimensions.
The paper tackles the problem of reconstructing multidimensional signals from underdetermined measurements in compressed sensing, showing that total variation minimization can achieve near-optimal guarantees with O(sd*log(N^d)) measurements, matching the best s-term approximation of the gradient up to polynomial factors.
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 to signals of arbitrary dimension d>1 and to isotropic total variation problems. To be precise, we show that a multidimensional signal x can be reconstructed from O(sd*log(N^d)) linear measurements using total variation minimization to within 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.