Inertial nonconvex alternating minimizations for the image deblurring

Tao Sun, Roberto Barrio, Marcos Rodríguez, Hao Jiang

Abstract

In image processing, Total Variation (TV) regularization models are commonly used to recover blurred images. One of the most efficient and popular methods to solve the convex TV problem is the Alternating Direction Method of Multipliers (ADMM) algorithm, recently extended using the inertial proximal point method. Although all the classical studies focus on only a convex formulation, recent articles are paying increasing attention to the nonconvex methodology due to its good numerical performance and properties. In this paper, we propose to extend the classical formulation with a novel nonconvex Alternating Direction Method of Multipliers with the Inertial technique (IADMM). Under certain assumptions on the parameters, we prove the convergence of the algorithm with the help of the Kurdyka-{\L}ojasiewicz property. We also present numerical simulations on classical TV image reconstruction problems to illustrate the efficiency of the new algorithm and its behavior compared with the well established ADMM method.

Introduction

Image deblurring is a fundamental task in image processing, aimed at recovering a sharp image from a blurry and noisy observation. Total Variation (TV) regularization has long been the gold standard for this task due to its ability to preserve edges. While convex TV models ($L_1$-norm) are mathematically well-behaved and widely used, nonconvex TV models ($L_q$ semi-norms with $0 < q < 1$) often yield superior results, including sharper edges and better noise suppression.

However, nonconvex optimization presents significant challenges: solvers are often inefficient, and proving convergence is mathematically complex. Furthermore, standard solvers typically lack "inertial" acceleration—a technique that uses information from previous iterations to speed up the current step. This paper introduces the Inertial Alternating Direction Method of Multipliers (IADMM) to address these limitations.

Methodology: The IADMM Algorithm

The proposed IADMM algorithm integrates inertial acceleration into a nonconvex ADMM framework. Key innovations include:

  1. Inertial Acceleration: By using a linear combination of current and previous iterations (controlled by parameter $\alpha$), the algorithm gains momentum, accelerating convergence toward the solution.
  2. Extended Penalty Form: To ensure stability and convergence in nonconvex settings where the gradient operator ($\nabla$) is not injective, the authors introduced an extended penalty form that modifies the underlying mathematical structure.
  3. Convergence Proof: Leveraging the Kurdyka-Łojasiewicz (KŁ) property, the authors rigorously proved that the sequence of iterations converges to a critical point.
  4. Parameter Estimation: A fast, FFT-based method was developed to estimate optimal penalty parameters ($\delta$), avoiding computationally expensive direct matrix inversions.

Experimental Results

The IADMM algorithm was evaluated against standard ADMM using twelve benchmark images, ranging from classic test images like Cameraman and Lena to medical scans and high-resolution samples from the USC-SIPI database.

Convergence and Performance

Numerical simulations demonstrate that IADMM significantly outperforms standard ADMM in terms of speed and accuracy. As shown in Figure 2, IADMM (especially with $\alpha=0.5$) converges much faster than its non-inertial counterparts.

Convergence comparison of IADMM and standard ADMM showing objective function, real error, SNR, and residual trends.

A critical observation was the behavior of the residual at high precision. The authors identified that the residual starts to oscillate or grow once peak precision is reached. To handle this, they implemented a specific stop control criterion (indicated by black dots in Figure 2d) to halt the algorithm at the point of maximum stability.

Quantitative Comparison

The efficiency gains are quantified across various datasets. For instance, in the "Brain" image (M0), IADMM reached the target precision in 49 iterations, while standard ADMM required 100 iterations—a 2x speedup.

Table summarizing iterations, error, SNR, and residuals for IADMM and ADMM across various test images.

The results indicate that the nonconvex $L_{1/2}$ model used in IADMM provides better edge preservation and robustness to Gaussian noise compared to the standard convex $L_1$ model. Sensitivity analysis also revealed that while larger inertial values ($\alpha$) accelerate convergence, they can introduce instability, suggesting an optimal range of $\alpha \in [0.5, 0.8]$.

Conclusion

The IADMM framework successfully combines the performance benefits of nonconvex TV regularization with the speed of inertial acceleration. By addressing the stability issues inherent in nonconvex optimization through an extended penalty form and a robust stop criterion, the authors have provided a practical and theoretically sound tool for high-quality image deblurring. Future work may explore automatic parameter tuning and extending the framework to blind deblurring or other nonconvex penalty functions.

Summary updated

Abstract

In image processing, Total Variation (TV) regularization models are commonly used to recover blurred images. One of the most efficient and popular methods to solve the convex TV problem is the Alternating Direction Method of Multipliers (ADMM) algorithm, recently extended using the inertial proximal point method. Although all the classical studies focus on only a convex formulation, recent articles are paying increasing attention to the nonconvex methodology due to its good numerical performance and properties. In this paper, we propose to extend the classical formulation with a novel nonconvex Alternating Direction Method of Multipliers with the Inertial technique (IADMM). Under certain assumptions on the parameters, we prove the convergence of the algorithm with the help of the Kurdyka-{\L}ojasiewicz property. We also present numerical simulations on classical TV image reconstruction problems to illustrate the efficiency of the new algorithm and its behavior compared with the well established ADMM method.
BibTeX
@article{sun2019inertial,
  author = {Tao Sun and Roberto Barrio and Marcos Rodríguez and Hao Jiang},
  title = {{Inertial nonconvex alternating minimizations for the image deblurring}},
  journal = {IEEE Trans. Image Process.},
  year = {2019},
  url = {https://openreview.net/forum?id=GSAiN9fPyl},
}
Figure