Bregman Itoh–Abe Methods for Sparse Optimisation

Martin Benning, Erlend S. Riis, Carola‐Bibiane SchönliebApollo 2019 · DOI

TL;DR

This paper introduces a new class of optimization methods, "Bregman Itoh-Abe methods," for solving complex inverse problems, particularly those involving sparse solutions. By combining geometric numerical integration techniques with generalized Bregman distances, these methods offer improved convergence rates and stability, especially for non-smooth and non-convex problems common in image processing and signal recovery.

What Problem Does This Paper Address?

Many real-world problems, such as image denoising or compressed sensing, can be framed as inverse problems. These problems often involve recovering an underlying signal from incomplete or noisy data, which can be mathematically represented as optimization problems. A key challenge is that these optimization problems are frequently non-smooth and non-convex, making them difficult to solve with standard algorithms. Furthermore, incorporating prior knowledge about the signal, such as its sparsity (meaning most of its components are zero), is crucial for obtaining accurate solutions. Existing methods like Bregman iterations and linearised Bregman iterations are popular for this, but they can sometimes struggle with efficiency or stability. This paper aims to bridge this gap by developing a novel optimization framework that leverages the strengths of geometric numerical integration and generalized Bregman distances to tackle these challenging sparse optimization problems more effectively.

Methods

The core contribution of this paper is the development of Bregman Itoh-Abe methods. These methods are derived by discretizing the inverse scale space (ISS) flow, which is a generalization of gradient flows that uses a Bregman distance instead of the standard Euclidean distance. The discretization is achieved using discrete gradient methods, specifically the Itoh-Abe discrete gradient.

Key aspects of the methodology include:

  • Inverse Scale Space (ISS) Flow: This is a continuous-time differential system that generalizes gradient flows by incorporating a Bregman distance, which allows for incorporating prior information (like sparsity) into the optimization process.
  • Bregman Distances: These are generalized distance measures derived from a convex function (the Bregman function), which are crucial for defining the ISS flow and its discrete counterparts.
  • Discrete Gradient Methods: These are numerical integration techniques from geometric integration that preserve the geometric structures of differential systems, such as dissipation. The Itoh-Abe discrete gradient is a derivative-free method that has shown promise for non-smooth, non-convex optimization.
  • Bregman Itoh-Abe Methods: By applying the Itoh-Abe discrete gradient to the ISS flow, the authors derive new iterative algorithms. These methods are designed to be unconditionally dissipative, meaning they maintain stability for any time step, and are shown to achieve rapid convergence rates by exploiting problem structures like sparsity.
  • Clarke Subdifferential Framework: For non-smooth, non-convex problems, the authors use the Clarke subdifferential framework to prove convergence guarantees for their proposed methods.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and numerical experiments using synthetic data generated to represent typical inverse problems.

Key Insights and Ideas

  • Bridging Geometric Integration and Bregman Iterations: The paper successfully unifies concepts from geometric numerical integration (discrete gradients) with established optimization techniques (Bregman iterations) to create a more powerful framework for inverse problems.
  • Unconditional Dissipation for Non-Smooth Problems: The proposed Bregman Itoh-Abe methods inherit the unconditional dissipative property from discrete gradients, ensuring stability even for non-smooth and non-convex objective functions, which is a significant advantage.
  • Exploiting Sparsity for Faster Convergence: The methods are shown to effectively leverage sparsity, a common prior in many inverse problems, leading to significantly faster convergence rates compared to standard methods.
  • Generalization of Existing Methods: The work demonstrates how the Itoh-Abe discrete gradient applied to the ISS flow can generalize existing iterative methods for linear systems, such as the Successive Over-Relaxation (SOR) method, when specific Bregman functions are chosen.
  • Theoretical Guarantees for Non-Convexity: The paper provides rigorous convergence guarantees for these methods in the challenging non-smooth, non-convex setting, which is crucial for practical applications.

Key Results

The paper presents theoretical convergence guarantees for the proposed Bregman Itoh-Abe methods in a Clarke subdifferential framework for non-smooth, non-convex optimization problems.

Numerical Results:

  • Linear Systems: Comparisons with SOR and sparse SOR methods on Gaussian linear systems (with and without noise) show that the sparse SOR method (a specific instance of the Bregman Itoh-Abe method) achieves significantly faster convergence and better support recovery (identifying sparse indices) when sparsity is present.
  • Image Denoising: For a student-t regularized image denoising problem, the Bregman Itoh-Abe method (referred to as BIA) demonstrated faster convergence in terms of both relative objective and relative gradient norm compared to the standard Itoh-Abe method (IA), highlighting the benefit of incorporating sparsity-promoting Bregman functions.

Limitations and Future Work

Limitations:

  • Uniqueness of Updates: While the paper proves existence of updates, uniqueness is guaranteed for convex problems or under specific conditions related to strong convexity and time steps. For general non-convex problems, uniqueness is not always guaranteed, though the authors note this doesn't hinder implementation.
  • Computational Cost: While convergence is improved, the discrete gradient methods can sometimes lead to implicit updates, which might require iterative solvers themselves, potentially increasing computational cost per iteration compared to explicit methods.
  • Generalization of Convergence Rates: The paper proves stationarity guarantees, but explicitly states that future work will focus on proving convergence rates for the Bregman Itoh-Abe methods.

Future Work:

  • Convergence Rate Analysis: Proving explicit convergence rates for the proposed methods.
  • Comparison with Other Methods: Further comparison with related methods, such as the sparse Kaczmarz method.
  • Exploring Other Discrete Gradients: Investigating the use of other discrete gradient methods, like the mean value discrete gradient, within the Bregman Itoh-Abe framework.
  • Applications: Exploring applications in a wider range of inverse problems and imaging tasks.

Summary updated

Abstract

In this paper we propose optimisation methods for variational regularisation problems based on discretising the inverse scale space flow with discrete gradient methods. Inverse scale space flow generalises gradient flows by incorporating a generalised Bregman distance as the underlying metric. Its discrete-time counterparts, Bregman iterations and linearised Bregman iterations are popular regularisation schemes for inverse problems that incorporate a priori information without loss of contrast. Discrete gradient methods are tools from geometric numerical integration for preserving energy dissipation of dissipative differential systems. The resultant Bregman discrete gradient methods are unconditionally dissipative and achieve rapid convergence rates by exploiting structures of the problem such as sparsity. Building on previous work on discrete gradients for non-smooth, non-convex optimisation, we prove convergence guarantees for these methods in a Clarke subdifferential framework. Numerical results for convex and non-convex examples are presented.
BibTeX
@inproceedings{benning2019bregman,
  author = {Martin Benning and Erlend S. Riis and Carola‐Bibiane Schönlieb},
  title = {{Bregman Itoh–Abe Methods for Sparse Optimisation}},
  booktitle = {Apollo},
  year = {2019},
  doi = {10.17863/cam.48272},
}
Figure