A convergence proof of the split Bregman method for regularized least-squares problems

Hung Nien, Jeffrey A. FesslerarXiv 2014 · OpenReview

TL;DR

This paper provides a rigorous convergence proof for the Split Bregman (SB) method when applied to image reconstruction problems with quadratic data-fitting terms. It demonstrates that the SB method is a specific instance of the more general Alternating Direction Method of Multipliers (ADMM) and analyzes how a two-split ADMM can outperform the SB method by carefully tuning its parameters.

What Problem Does This Paper Address?

Image reconstruction, particularly in fields like medical imaging (CT, MRI), often involves solving inverse problems where we try to recover an image from incomplete or noisy measurements. These problems are frequently ill-posed, meaning small errors in the data can lead to large errors in the reconstructed image. To address this, regularization techniques are employed, which add a penalty term to the optimization problem that favors "well-behaved" solutions (e.g., smooth images).

The Split Bregman (SB) method is a popular algorithm for solving these regularized problems, especially when the regularization involves L1-norms (like Total Variation or Compressed Sensing). It works by splitting the problem into simpler subproblems. However, existing convergence proofs for SB often rely on strong assumptions, such as the system matrix having "full column rank" or requiring exact solutions to subproblems. These assumptions are frequently violated in practical applications like X-ray CT, where the system's Hessian is shift-variant and solving subproblems exactly can be computationally prohibitive. This paper aims to bridge this gap by providing a convergence proof for the SB method under more practical conditions and exploring how a generalized ADMM approach can offer advantages.

Methods

The core of this paper is establishing an equivalence between the Split Bregman (SB) method and a more general framework called the Alternating Direction Method of Multipliers (ADMM).

  1. SB as a Special Case of ADMM: The authors show that the SB method, when applied to problems with a quadratic data-fitting term, can be viewed as a specific instance of a two-split ADMM algorithm. This connection is crucial because ADMM has well-established convergence guarantees, even with inexact updates.
  2. Convergence Proof for Inexact Updates: By leveraging the ADMM framework, the paper provides a straightforward convergence proof for the SB method that explicitly allows for inexact solutions to its subproblems. This is a significant improvement over previous proofs that required exact updates.
  3. Convergence Rate Analysis: To explore potential performance gains, the authors conduct a detailed convergence rate analysis of a two-split ADMM algorithm applied to a quadratically regularized image restoration problem. This analysis helps understand how the ADMM's penalty parameters (ρ and η) influence the convergence speed.
  4. Parameter Tuning: Based on the convergence rate analysis, the paper investigates how to select the optimal penalty parameters for both the SB method and the two-split ADMM to achieve faster convergence.

Datasets

The paper uses a synthetic image restoration problem for numerical experiments. The "dataset" consists of:

  • A true image.
  • A noisy and blurred version of the true image, generated using a degradation matrix (A) and a masked finite difference matrix (C).

No new benchmark datasets are introduced.

Key Insights and Ideas

  • SB is ADMM in disguise: The most significant insight is that the Split Bregman method is not fundamentally different from ADMM but rather a specific parameterization of a two-split ADMM. This connection unlocks the robust convergence guarantees of ADMM for SB.
  • Inexactness is okay (with caveats): The paper proves that SB can converge even if its subproblems are not solved exactly, as long as the errors are "summable." This is critical for practical applications where exact solutions are often infeasible.
  • ADMM can be faster: By analyzing a two-split ADMM, the authors show that it can converge faster than the SB method, especially when the SB method's penalty parameter is suboptimal. This suggests that a more flexible ADMM approach offers an advantage.
  • Parameter tuning matters: The convergence rate analysis highlights the sensitivity of the algorithms to penalty parameters. Optimal parameter selection can lead to significant speedups, and the paper provides guidance on how to tune these parameters.
  • Full column rank is not always necessary: Unlike some prior SB convergence proofs, this work relaxes the "full column rank" assumption on the matrix Θ, making the proof applicable to a wider range of practical problems.

Key Results

  • Convergence Proof: The paper establishes that the Split Bregman method is a convergent ADMM algorithm for regularized least-squares problems with quadratic data-fitting terms, even with inexact updates.
  • Convergence Rate Analysis: For quadratically regularized image restoration, the analysis shows that the two-split ADMM algorithm can achieve faster convergence than the SB method, particularly when the SB method's penalty parameter is not optimally chosen.
  • Parameter Selection Guidance: The paper derives optimal penalty parameters for the SB method and the two-split ADMM in the quadratic case, demonstrating how to balance convergence speed and stability.
  • Numerical Verification: Experimental results (Figure 5.2) confirm the theoretical findings, showing that different parameter settings lead to varying convergence rates and that the two-split ADMM can indeed outperform the SB method.

Limitations and Future Work

  • Quadratic Data-Fitting Term: The convergence proof and detailed convergence rate analysis are primarily for problems with a quadratic data-fitting term. The paper acknowledges that the convergence of SB for general convex data-fitting terms remains an open problem.
  • Non-Quadratic Regularizers: While the analysis provides insights into parameter tuning for quadratic cases, it doesn't directly apply to non-quadratic, edge-preserving regularizers. However, the authors suggest it might offer some intuition for pixels in flat regions where the cost function is nearly quadratic.
  • Future Work: The authors express interest in investigating the convergence rate of ADMM algorithms when inexact solvers are used for the subproblems, and how this affects the overall convergence rate. They also plan to explore the convergence rate for more complex proximal operators.

Summary updated

Abstract

The split Bregman (SB) method [T. Goldstein and S. Osher, SIAM J. Imaging Sci., 2 (2009), pp. 323-43] is a fast splitting-based algorithm that solves image reconstruction problems with general l1, e.g., total-variation (TV) and compressed sensing (CS), regularizations by introducing a single variable split to decouple the data-fitting term and the regularization term, yielding simple subproblems that are separable (or partially separable) and easy to minimize. Several convergence proofs have been proposed, and these proofs either impose a "full column rank" assumption to the split or assume exact updates in all subproblems. However, these assumptions are impractical in many applications such as the X-ray computed tomography (CT) image reconstructions, where the inner least-squares problem usually cannot be solved efficiently due to the highly shift-variant Hessian. In this paper, we show that when the data-fitting term is quadratic, the SB method is a convergent alternating direction method of multipliers (ADMM), and a straightforward convergence proof with inexact updates is given using [J. Eckstein and D. P. Bertsekas, Mathematical Programming, 55 (1992), pp. 293-318, Theorem 8]. Furthermore, since the SB method is just a special case of an ADMM algorithm, it seems likely that the ADMM algorithm will be faster than the SB method if the augmented Largangian (AL) penalty parameters are selected appropriately. To have a concrete example, we conduct a convergence rate analysis of the ADMM algorithm using two splits for image restoration problems with quadratic data-fitting term and regularization term. According to our analysis, we can show that the two-split ADMM algorithm can be faster than the SB method if the AL penalty parameter of the SB method is suboptimal. Numerical experiments were conducted to verify our analysis.
BibTeX
@misc{nien2014convergence,
  author = {Hung Nien and Jeffrey A. Fessler},
  title = {{A convergence proof of the split Bregman method for regularized least-squares problems}},
  year = {2014},
  eprint = {1402.4371},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1402.4371},
}
Figure