Generalized Sinkhorn Iterations for Regularizing Inverse Problems Using Optimal Mass Transport

Johan Karlsson, Axel RinghSIAM J. Imaging sci 2017 · DOI

TL;DR

This paper introduces a novel computational framework for solving inverse problems by leveraging optimal mass transport (OMT) as a regularizer. They extend the efficient Sinkhorn iterations to compute the proximal operator of OMT costs, enabling the solution of complex inverse problems like limited-angle CT reconstruction with improved accuracy and reduced artifacts compared to traditional methods.

What Problem Does This Paper Address?

Inverse problems, such as image reconstruction in medical imaging, often suffer from ill-posedness, meaning small errors in measurements can lead to large errors in the reconstructed solution. Regularization techniques are crucial to stabilize these problems and incorporate prior knowledge. While optimal mass transport (OMT) offers a powerful geometric framework for comparing and modeling data (e.g., deformations), its computational intractability for large-scale problems has limited its application. Existing methods for OMT often rely on approximations like entropic regularization, which can be solved efficiently using Sinkhorn iterations. However, applying these OMT-based regularizers to complex inverse problems, especially those with limited data, remained a significant challenge. This paper aims to bridge this gap by developing efficient algorithms to integrate OMT priors into inverse problem solving.

Methods

The core of this work lies in two main contributions:

  1. Generalized Sinkhorn Iterations for OMT Proximal Operators: The authors extend the Sinkhorn iteration algorithm, originally designed for entropic regularized OMT, to efficiently compute the proximal operator of the OMT cost. This is achieved by reformulating the problem in a dual space and using block-coordinate ascent, leading to a computationally efficient algorithm that scales well with problem size.
  2. Douglas-Rachford Splitting for Inverse Problems: They then integrate this OMT proximal operator computation into a Douglas-Rachford type splitting algorithm. This framework is highly versatile for solving optimization problems that are sums of simpler functions, allowing them to combine the OMT prior with other regularization terms (like Total Variation) and data fidelity terms (like L2 norm) to tackle inverse problems.

Datasets

The paper uses standard phantoms for evaluation:

  • Shepp-Logan Phantom: A common benchmark in CT imaging.
  • Hand Image Phantom: A more complex, natural image.

These phantoms are used to simulate realistic inverse problems, specifically limited-angle CT reconstruction, by generating synthetic measurement data.

Key Insights and Ideas

  • OMT as a Geometric Prior: The paper highlights that OMT naturally captures geometric relationships and deformations between images, making it a powerful prior for tasks where spatial consistency and structural integrity are important. This is in contrast to L2 priors, which can lead to "fade-in-fade-out" artifacts when the prior and data mismatch.
  • Sinkhorn Iterations for Proximal Operators: The generalization of Sinkhorn iterations to compute proximal operators is a significant algorithmic advancement. It allows for efficient handling of the OMT cost within larger optimization frameworks.
  • Splitting Methods Unlock Complexity: The use of Douglas-Rachford splitting effectively decomposes complex inverse problems into manageable subproblems, where the OMT proximal operator can be efficiently computed. This enables the integration of sophisticated priors into practical reconstruction pipelines.
  • Improved Reconstruction with OMT: The results demonstrate that OMT priors can lead to reconstructions with fewer artifacts and better preservation of structural information, especially in challenging scenarios like limited-angle CT.

Key Results

The paper demonstrates the effectiveness of their approach through numerical simulations in computerized tomography:

  • Reduced Artifacts: Reconstructions using the OMT prior exhibit significantly fewer artifacts, particularly the "fade-in-fade-out" effect seen with L2 priors, and less blurring compared to TV-regularization in limited-angle scenarios.
  • Better Prior Adherence: The OMT prior helps to align the reconstructed image with the structural information of the prior, even when the data is sparse, without rigidly enforcing the prior's exact values.
  • Computational Efficiency: The generalized Sinkhorn iterations and the Douglas-Rachford splitting framework allow for the efficient solution of these complex inverse problems, making OMT-based regularization practical. For instance, they solve problems with millions of variables efficiently.

Limitations and Future Work

  • Computational Cost of OMT: While their method is efficient, the core OMT computation still involves matrix operations (e.g., with K and KT) which can be bottlenecks. They mention that for regular grids, FFT can speed this up, but this is not universally applicable.
  • Ill-Conditioning with Small ε: The entropic regularization parameter ε can lead to ill-conditioning when very small. While they acknowledge stabilization techniques exist, they did not implement them to maintain FFT compatibility.
  • Generalization to Unbalanced Transport: The current work primarily focuses on balanced mass transport. Extending the framework to handle unbalanced masses would broaden its applicability.
  • Multi-Marginal OMT and Barycenters: The authors suggest that their methodology can be extended to problems with multiple OMT terms, such as computing barycenters from noisy measurements, which is a promising direction for future work.
  • Application to Other Domains: While demonstrated on CT, the framework is general and could be applied to other inverse problems in image processing, computer vision, and machine learning.

Summary updated

BibTeX
@article{karlsson2017generalized,
  author = {Johan Karlsson and Axel Ringh},
  title = {{Generalized Sinkhorn Iterations for Regularizing Inverse Problems Using Optimal Mass Transport}},
  journal = {SIAM J. Imaging sci},
  year = {2017},
  doi = {10.1137/17m111208x},
}
Figure