A provably convergent MM-GKS variant for large-scale inverse problems
Abstract
For high-quality images with sharp edges, a popular choice for edge-preserving regularization is using a general(ized) ℓq-norm of the gradient of the image. This can be implemented efficiently using the ℓ2-norm and a sequence of weighted gradients, with weights derived from the current solution estimate. We can solve the resulting sequence of regularized least squares problems using hybrid Krylov subspace methods, which efficiently compute the regularization parameter using the problem projected on the Krylov subspace. However, each update of the regularization operator requires a new Krylov subspace. The majorization-minimization generalized Krylov subspace method (MM-GKS) addresses this problem by using a single, generalized, Krylov subspace (GKS). Unfortunately, for large-scale problems, if convergence is not fast, MM-GKS has overwhelming memory requirements and computational costs. We propose a variant of MM-GKS that alternately compresses and expands the search space while maintaining strict monotonic convergence. We show that our method provably converges to the minimum of the selected functional, even if the search space dimension is kept very small. This substantially improves on previous theoretical results for MM-GKS, where the convergence proof relies on the basis for the solution space (eventually) spanning the full space. We show that our method can solve large-scale problems efficiently both in terms of memory requirements and computational complexity. We further generalize our proposed method to handle streaming problems, where the data is either not all available simultaneously or needs to be treated as such because of the extreme memory requirements. We use numerical examples from image deblurring, dynamic photoacoustic tomography, and streaming X-ray computed tomography (CT) to illustrate the effectiveness of our proposed methods.
Related
- A Provably Convergent and Practical Algorithm for Gromov--Wasserstein Optimal Transport
- Optical Fourier Transform-Based Preconditioning for Large-Scale Inverse Problems
- A super-convergent quasi-discontinuous Galerkin method for advection-diffusion problems
- A globally convergent stochastic semismooth Newton method for strongly convex problems in Hilbert spaces
- Averaged Mirror Descent and Dual Gradient Methods: Convergent Algorithms for Entropic Gromov-Wasserstein Problems
BibTeX
@misc{pasha2026provably,
title = {{A provably convergent MM-GKS variant for large-scale inverse problems}},
author = {Mirjeta Pasha and Eric de Sturler and Misha Kilmer},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17229},
eprint = {2609.17229},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17229},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A provably convergent MM-GKS variant for large-scale inverse problems
AU - Mirjeta Pasha
AU - Eric de Sturler
AU - Misha Kilmer
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17229
UR - https://arxiv.org/abs/2609.17229
AB - For high-quality images with sharp edges, a popular choice for edge-preserving regularization is using a general(ized) ℓ_q-norm of the gradient of the image. This can be implemented efficiently using the ℓ_2-norm and a sequence of weighted gradients, with weights derived from the current solution estimate. We can solve the resulting sequence of regularized least squares problems using hybrid Krylov subspace methods, which efficiently compute the regularization parameter using the problem projected on the Krylov subspace. However, each update of the regularization operator requires a new Krylov subspace. The majorization-minimization generalized Krylov subspace method (MM-GKS) addresses this problem by using a single, generalized, Krylov subspace (GKS). Unfortunately, for large-scale problems, if convergence is not fast, MM-GKS has overwhelming memory requirements and computational costs. We propose a variant of MM-GKS that alternately compresses and expands the search space while maintaining strict monotonic convergence. We show that our method provably converges to the minimum of the selected functional, even if the search space dimension is kept very small. This substantially improves on previous theoretical results for MM-GKS, where the convergence proof relies on the basis for the solution space (eventually) spanning the full space. We show that our method can solve large-scale problems efficiently both in terms of memory requirements and computational complexity. We further generalize our proposed method to handle streaming problems, where the data is either not all available simultaneously or needs to be treated as such because of the extreme memory requirements. We use numerical examples from image deblurring, dynamic photoacoustic tomography, and streaming X-ray computed tomography (CT) to illustrate the effectiveness of our proposed methods.
ER -