Inertial Nonconvex Alternating Minimizations for the Image Deblurring

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

TL;DR

This paper introduces IADMM (Inertial Alternating Direction Method of Multipliers), a novel algorithm that brings "inertial" acceleration—essentially a momentum-like boost—to nonconvex image deblurring. By combining nonconvex Total Variation (TV) regularization with an accelerated solver, the authors achieve sharper image reconstruction and significantly faster convergence speeds compared to standard convex ADMM methods.

What Problem Does This Paper Address?

Image deblurring aims to recover a sharp image from a blurry, noisy observation. The gold standard for this has long been Total Variation (TV) regularization, which helps preserve edges. Traditionally, researchers use a convex version ($L_1$-norm) because it is mathematically "well-behaved" and easy to solve.

However, nonconvex TV ($L_q$ semi-norms where $0 < q < 1$) actually produces better results, yielding sharper edges and better noise suppression. The catch? Nonconvex problems are notoriously difficult to solve efficiently, and proving that an algorithm will actually converge to a solution is a mathematical minefield. Furthermore, standard solvers lack "inertial" techniques—using information from previous steps to speed up the current one—which are common in convex optimization but tricky to implement in nonconvex settings.

Methods

The authors propose the Inertial Nonconvex ADMM (IADMM). Key components include:

  • Inertial Acceleration: Unlike standard ADMM, which only looks at the current step, IADMM uses a linear combination of the current and previous iterations (controlled by a parameter $\alpha$). This acts like momentum, pushing the algorithm toward the solution faster.
  • Model Modification: Standard deblurring models often fail convergence proofs in nonconvex settings because the gradient operator ($\nabla$) isn't "injective" (reversible). The authors introduce an extended penalty form that modifies the underlying math to ensure the algorithm remains stable and provably convergent.
  • Mathematical Proof: They use the Kurdyka-Łojasiewicz (KŁ) property to rigorously prove that their sequence of iterations will converge to a critical point, providing a theoretical safety net for the nonconvex approach.
  • Probabilistic Parameter Estimation: They provide a fast, FFT-based method to estimate the optimal penalty parameters ($\delta$), avoiding the high computational cost of direct matrix calculations.

Datasets

The algorithm was evaluated on twelve standard test images, including:

  • Classic benchmarks: Cameraman, Lena, and a text image from El Quijote.
  • Medical images: Brain M0 and Heart M1.
  • High-resolution images: Several samples from the USC-SIPI image database.
  • Synthetic Blur: Images were artificially degraded using a $17 \times 17$ Gaussian kernel with a standard deviation of $\sigma=7$.

Key Insights and Ideas

  • The "Aha" Moment on Stability: Nonconvex methods can become unstable once they reach peak precision. The authors discovered that the "residual" (the error between steps) starts to oscillate or grow at this point. They introduced a specific stop control criterion to halt the algorithm exactly when it reaches maximum stability.
  • Momentum in Nonconvexity: While adding momentum (inertia) usually risks making a nonconvex solver diverge, the authors showed that by carefully constructing an auxiliary "energy" function $F$, they could guarantee a "sufficient descent" at every step.
  • Injectivity Matters: A major hurdle for nonconvex ADMM was the non-injective nature of the gradient operator. By adding a small weight parameter $\beta$ to link image components, they "fixed" the operator's properties without degrading the image quality.

Key Results

  • Speedup: IADMM is significantly faster than standard ADMM. For the "Brain" image, IADMM reached the target precision in 49 iterations, whereas standard ADMM took 100 iterations—a 2x efficiency gain.
  • Visual Quality: The nonconvex $L_{1/2}$ model used in IADMM provided noticeably better edge preservation and was more robust to Gaussian noise than the standard convex $L_1$ model.
  • Parameter Sensitivity: The study showed that larger inertial values ($\alpha$) lead to faster convergence but higher instability, suggesting an optimal "sweet spot" (around $\alpha=0.5$ to $0.8$) for most deblurring tasks.

Limitations and Future Work

  • Instability at High Precision: As noted, the algorithm can behave chaotically if allowed to run too long past its convergence point. While the stop-criterion helps, a more inherently stable formulation would be ideal.
  • Automatic Parameter Tuning: While the paper provides a strategy for choosing $\delta$, finding the perfect balance between $\alpha$ and $\delta$ still requires some manual trial and error.
  • Broader Application: The authors suggest that this framework could be extended to other types of image degradation (like "blind" deblurring where the blur kernel is unknown) or different nonconvex penalty functions beyond the $L_q$ semi-norm.

Summary updated

Abstract

In image processing, total variation (TV) regularization models are commonly used to recover the 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-Łojasiewicz property. We also present numerical simulations on the 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},
}

Loading related content...

Figure