A New Alternating Minimization Algorithm for Total Variation Image Reconstruction

TLDR

The authors propose an alternating minimization algorithm, with a continuation scheme, for recovering images from blurry and noisy observations using total variation regularization. The algorithm is derived from a new half‑quadratic model applicable to both anisotropic and isotropic TV, runs each iteration with three fast Fourier transforms, and incorporates a continuation scheme to accelerate convergence. The algorithm converges strongly—finite for some variables and fast exponential for others—and, according to extensive numerical tests, outperforms state‑of‑the‑art methods, running orders of magnitude faster than lagged diffusivity for TV deblurring, with extensions discussed.

Abstract

We propose, analyze, and test an alternating minimization algorithm for recovering images from blurry and noisy observations with total variation (TV) regularization. This algorithm arises from a new half-quadratic model applicable to not only the anisotropic but also the isotropic forms of TV discretizations. The per-iteration computational complexity of the algorithm is three fast Fourier transforms. We establish strong convergence properties for the algorithm including finite convergence for some variables and relatively fast exponential (or q-linear in optimization terminology) convergence for the others. Furthermore, we propose a continuation scheme to accelerate the practical convergence of the algorithm. Extensive numerical results show that our algorithm performs favorably in comparison to several state-of-the-art algorithms. In particular, it runs orders of magnitude faster than the lagged diffusivity algorithm for TV-based deblurring. Some extensions of our algorithm are also discussed.