PaperlayerView exact revision on arXiv

Source-linked AI summary

A provably convergent MM-GKS variant for large-scale inverse problems

Mirjeta Pasha, Eric de Sturler, Misha Kilmer

arXiv:2609.17229v1math.NA

TL;DR

Large-scale edge-preserving inverse reconstruction makes standard MM-GKS costly because changing regularization operators require expanding storage and repeated computation. The paper introduces an alternating expansion-compression variant with provable convergence at small dimension, extends it to streaming data, and demonstrates effectiveness across several imaging applications.

  • Problem

    Standard MM-GKS can require overwhelming memory and computational costs, while prior convergence proofs rely on eventually spanning the full solution space.

  • Method

    The method alternately expands and compresses a generalized Krylov search space, retaining relevant information while dynamically estimating regularization parameters and supporting streaming data.

  • Results

    The proposed variant provably converges to the functional minimum with a fixed small search-space dimension and is effective across image deblurring, dynamic tomography, and streaming CT examples.

  • Takeaways & Limitations

    Bounded search spaces can preserve convergence and reconstruction quality while reducing memory and computational demands for large-scale and streaming inverse problems.

  • Takeaways & Limitations

    The paper presents straightforward implementations, while more efficient choices for memory, flops, and data movement remain future work.

Abstract

from arXiv · show

For high-quality images with sharp edges, a popular choice for edge-preserving regularization is using a general(ized) $\ell_q$-norm of the gradient of the image. This can be implemented efficiently using the $\ell_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.

1. Introduction.

The paper develops a memory-aware MM-GKS variant for edge-preserving reconstruction that keeps search spaces small while preserving convergence and relevant information. It targets large, dynamic, and streaming inverse problems where standard MM-GKS can exceed memory and computational limits.

  • 1. Introduction.: The approach is designed for dynamic inverse problems and streaming settings where data arrive sequentially or memory constraints require processing only data chunks.Applications include image deblurring, dynamic photoacoustic tomography, and streaming X-ray CT.
  • 1. Introduction.: Large-scale MM-GKS can exceed memory capacity and incur prohibitive orthogonalization costs when convergence is slow.Restarting reduces memory but discards important information, may reduce solution quality, and lacks a convergence proof to the target solution.
  • 1. Introduction.: The proposed method alternately expands and compresses the solution subspace, keeping its dimension bounded independently of iteration count while retaining relevant information.This design is particularly suited to streaming data and large dynamic inverse problems.
  • 1. Introduction.: The convergence proof changes the expansion direction and compression rules, enabling convergence to the functional minimum with a fixed small maximum search-space dimension.The method also supports dynamically estimating the regularization parameter with hybrid Krylov techniques.

2. Background.

MM-GKS applies majorization-minimization to a sequence of weighted regularized least-squares problems projected onto generalized Krylov subspaces. Its full-space convergence theory and repeated factorizations create practical costs for large problems.

  • 2. Background.: The weighting matrix is updated from the current solution estimate, so each optimization step changes the regularization operator and ordinarily requires a new Krylov subspace.Hybrid Krylov methods can estimate the regularization parameter from the projected problem when it is unknown.
  • 2. Background.: MM-GKS projects each iterate onto a low-dimensional subspace generated initially by Golub-Kahan bidiagonalization and subsequently expanded with residual directions.The projected solution is represented as x^(k+1) = V_(ℓ+k) z^(k+1), reducing the large problem to a small system.
  • 2. Background.: In exact arithmetic, the new residual direction is orthogonal to the existing basis, although reorthogonalization is typically needed in computer arithmetic.The basis expands until the solution is sufficiently accurate in the standard MM-GKS process.
  • 2. Background.: Standard MM-GKS convergence to the minimizer is established for known λ when the search space eventually spans the full solution space R^n.Constraining the space below n invalidates the earlier proof conditions.

3. A Limited Memory MM-GKS variant with guaranteed convergence.

LM-MM-GKS alternates bounded search-space expansion and compression, using an updated-weight gradient to preserve convergence while reducing memory and computational costs.

  • LM-MM-GKS alternates enlarging and compressing the solution space while keeping memory requirements constant and preserving reconstruction quality.The method also initializes with a better low-dimensional search space.
  • The method extends the search space with the gradient of the updated quadratic majorant, enabling convergence to the minimum of the regularized functional.This differs from standard MM-GKS, which uses the residual associated with the previous weight matrix.
  • Compression retains a small subspace containing the current best solution and the corresponding majorant gradient, guaranteeing strict monotonic decrease for fixed λ.Compression uses an isometric reduced basis and explicitly adds the solution and residual vectors.
  • Straightforward implementations are presented, while choices minimizing storage, floating-point operations, or data movement are left for future work.
  • Storage is bounded independently of iterations because LM-MM-GKS uses at most kmax basis vectors.Repeated QR costs become linear in iteration count, with cubic dependence confined to the modest constant kmax.

4. LM-MM-GKS for Streaming Data (s-LM-MM-GKS).

s-LM-MM-GKS adapts the limited-memory method to streaming data by solving partitioned systems successively and recycling selected information between them.

  • Streaming problems arise when only part of the data is available or when massive systems permit handling only a subset of rows at once.
  • The method partitions A and d into nt subproblems and solves them in succession because simultaneous solution is infeasible.
  • Selected data, an approximate solution, and a compressed solution subspace are recycled from one subproblem to the next.As the matrix changes, the gradient is recomputed separately for each system.
  • The first streaming system is solved with LM-MM-GKS, producing an approximate solution and a typically kmax-dimensional subspace for subsequent systems.

5. Compression approaches.

The paper compares four compression strategies for constructing a small solution subspace, including matrix-based decompositions and solution-oriented approaches.

  • The compression approaches are compared numerically in Section 7.1.
  • Truncated singular value decomposition retains the largest kmin−2 singular values of the projected matrix to form the compression basis.
  • Reduced basis decomposition greedily selects orthonormal directions using residual norms until reaching a tolerance or the kmin−2 column limit.
  • Solution-oriented compression selects indices associated with large projected-solution components from the regularized projected problem.
  • Sparsity-enforcing compression changes the projected regularization, solves a small majorization-minimization problem, and uses the resulting sparse solution only for basis-index selection.

6. Convergence Proof.

The method generates sufficient decrease in a quadratic majorant by expanding the search space with the updated majorant’s gradient, then proves convergence even with a fixed small space dimension.

  • Search-space update: The algorithm minimizes the approximate quadratic majorant over a search space containing the current approximation and the updated majorant’s gradient.This search-space construction preserves the improvement obtained from the descent direction while using the new tangent majorant.
  • Descent mechanism: A nonzero residual defines a descent direction, and minimizing along that direction yields a majorant reduction proportional to the squared gradient norm.The expanded space contains this step, so its constrained minimizer achieves at least the same reduction.
  • Convergence argument: Under a finite uniform bound on the quadratic matrices, the accumulated decrease rules out gradients remaining bounded away from zero.The proof therefore establishes that the gradient norm tends to zero along the iterations.
  • Descent mechanism: The quadratic majorant is tangent to the objective, so its decrease transfers to the original functional and produces monotonic progress.The majorant and objective share the relevant minimizer and update improvement under the stated construction.
  • Convergence guarantee: The resulting theorem proves convergence to the minimum of the regularized functional, or to a stationary point when the functional is non-convex.The theorem is stated for the iterates generated by the majorant minimization scheme.
  • Applications: Across image deblurring, dynamic photoacoustic tomography, and computed tomography, the proposed methods achieve high-quality reconstructions with limited memory.The streaming variant matches full MM-GKS quality with much lower memory, while LM-MM-GKS remains effective when full MM-GKS exceeds memory limits.

7. Numerical experiments.

The experiments evaluate limited-memory and streaming MM-GKS variants for image reconstruction, showing strong reconstruction quality with bounded storage across deblurring, tomography, and dynamic problems.

  • 7.1. Image deblurring.: LM-MM-GKS variants substantially outperform MM-GKS on Hubble deblurring, achieving RREs of 0.047–0.06 and HaarPSI values above 0.975.Results remain stable across compression approaches and kmin values, while MM-GKS is limited to a hypothetical memory capacity of 25 basis vectors.
  • 7.2.1. Test 1.: For Test 1 streaming tomography, full-problem MM-GKS and LM-MM-GKS achieve RREs of 1.27% and 1.42%, respectively, at σ = 0.1%.The full problem requires storing 210 MM-GKS vectors, whereas LM-MM-GKS uses at most 40 and attains comparable quality; streaming s-LM-MM-GKS is designed to approach this benchmark.
  • 7.2.1. Test 1.: s-LM-MM-GKS converges to a substantially lower RRE than HyBR-recycle in Test 1, with the comparison using edge-preserving ℓ1 regularization versus ℓ2 regularization.The convergence histories compare fixed 210 expansion steps per subproblem with an adaptive relative-difference stopping criterion of 10^-3.
  • 7.3. Dynamic photoacoustic tomography (dPAT).: In the dynamic photoacoustic tomography experiment, LM-MM-GKS produces RREs roughly 2.5 to 3 times smaller than MM-GKS and MM-GKSres, with higher SSIM and PSNR across noise levels.The underlying full MM-GKS computation would require approximately 55–60 GB for a 256 × 256 image and over 600 GB for 1024 × 1024 images.
  • Method and scope: The proposed approach alternates search-space expansion and compression, keeping memory bounded independently of iteration count while retaining convergence-relevant information.The paper also provides a streaming variant for data that are unavailable simultaneously or cannot fit in memory.

8. Conclusions and future work.

The proposed methods support memory-efficient reconstruction and integrate incoming with selected older data for streaming problems. Numerical examples across CT, image deblurring, and time-dependent inverse problems illustrate their effectiveness, while future work targets implementation efficiency and dynamic parameter selection.

  • 8. Conclusions and future work.: The methods effectively integrate incoming data with selected older data and support nonlinear edge-preserving reconstruction across CT, image deblurring, and time-dependent inverse problems.The paper reports effectiveness across these application settings.
  • 8. Conclusions and future work.: Future work includes more efficient implementations addressing memory, computational cost, and data movement, plus convergence theory for dynamically selected regularization parameters.
  • 8. Conclusions and future work.: MATLAB code for reproducing the numerical experiments is available on GitHub.
Loading 2609.17229v1…