New flexible and inexact Golub-Kahan algorithms for inverse problems

Silvia Gazzola, Malena Sabaté Landman · 2025

Read New flexible and inexact Golub-Kahan algorithms for inverse problems by Silvia Gazzola, Malena Sabaté Landman (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-18865.txt.

Introduction

Malena Sabaté Landman and Silvia Gazzola introduce algorithms for large inverse problems. A hidden image or object must be recovered from blurred, indirect data. Their methods rest on new Golub-Kahan factorizations. They are flexible and inexact by design. The factorizations build small subspaces that capture the problem's essentials. Solutions come from reweighted least squares problems inside those subspaces.

Residual subspaces carry preconditioners that may change each round. They may also be applied only inexactly. That is where the flexibility comes from. The design handles general measures of fit. It is not tied to standard squared error. Imaging experiments tested the methods. Image deblurring and computed tomography were the test beds. The methods proved effective and competitive with popular alternatives. Practitioners gain another Krylov-style option for hard reconstructions.

Catalog record

CREATORSilvia Gazzola, Malena Sabaté Landman
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-18865

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

New flexible and inexact Golub-Kahan algorithms for inverse problems Silvia Gazzola, Malena Sabaté Landman Abstract This paper introduces a new class of algorithms for solving large-scale linear inverse problems based on new flexible and inexact Golub-Kahan factorizations. The proposed methods iteratively compute regularized solutions by approximating a solution to (re)weighted least squares problems via projection onto adaptively generated subspaces, where the constraint subspaces for the residuals are (formally) equipped with iteration-dependent preconditioners or inexactness. The new solvers offer a flexible and inexact Krylov subspace alternative to other existing Krylov-based approaches for handling general data fidelity functionals, e.g., those expressed in the p p -norm. Numerical experiments in imaging applications, such as image deblurring and computed tomography, highlight the effectiveness and competitiveness of the proposed methods with respect to other popular methods. Keywords . Flexible and inexact Krylov subspace methods, Golub-Kahan factorizations, covariance preconditioning, p p -norm data fitting, image deblurring, computed tomography. 1 Introduction Discrete linear inverse problems are formulated as the solution of large-scale linear systems of equations of the form {\bf A}{\bf x}_{\text{\scriptsize{true}}}+{\bf n}={\bf b}\,, (1.1) where the discretized forward operator {\bf A}\in\mathbb{R}^{m\times n} is large-scale with ill-determined rank, {\bf x}_{\text{\scriptsize{true}}}\in\mathbb{R}^{n} is the unknown quantity of interest, and {\bf n}\in\mathbb{R}^{m} are some unknown perturbations (noise) affecting the available data {\bf b}\in\mathbb{R}^{m} . Such problems arise in many relevant applications in Science and Engineering, including image deblurring and computed tomography. Due to the ill-posedness of {\bf A} and the presence of noise in {\bf b} , one should regularize ( 1.1 ) in order to recover a meaningful approximation of {\bf x}_{\text{\scriptsize{true}}}\in\mathbb{R}^{n} , i.e., replace the ill-posed linear system by a nearby problem, whose solutions is more stable with respect to perturbations in the data. We refer to [ 19 , 22 , 25 ] for more details on discrete inverse problems and classical regularization methods. Many iterative solvers that look for an approximation \bar{\bf x}^{\ast}=\argmin_{{\bf x}\in\mathbb{R}^{n}}\nicefrac{{1}}{{2}}\|{\bf A}{\bf x}-{\bf b}\|_{2}^{2} (1.2) of {\bf x}_{\text{\scriptsize{true}}} in ( 1.1 ), including many Krylov subspace methods, are known to have regularizing properties achieved by early termination. Namely, the first iterations are unaffected by noise and the approximate solution approaches the true solution, but this stops once the noisy components and the unwanted solution of the unregularized least squares (LS) problem ( 1.2 ) start to be recovered. This type of behavior is usually referred to as semiconvergence; see [ 20 , 22 ] . Among Krylov methods, the mathematically equivalent CGLS and LSQR can handle rectangular matrices in ( 1.2 ) and their regularizing properties are well understood; see [ 23 ] and [ 21 , Chapter 6] . Essentially, when applying such methods to ( 1.2 ), we are trying to ‘fit as much of the data, fitting the minimum amount of noise’. Even if such solvers can be efficiently employed with additional (often Tikhonov-like) regularization with the goal of mitigating semiconvergence, for simplicity this is not considered in this paper; see [ 8 ] for more details. In this paper we consider iterative regularization methods that solve generalizations of problem ( 1.2 ), whereby some statistical information about the noise {\bf n} affecting the data in ( 1.1 ) is encoded into the problem formulation to enable more accurate recovery of {\bf x}_{\text{\scriptsize{true}}} . More specifically, if {\bf R}\in\mathbb{R}^{m\times m} is the noise covariance matrix (symmetric positive definite (SPD) by construction), the well-known Gauss-Markov theorem prescribes to solve the weighted LS problem \bar{\bf x}^{\ast}=\argmin_{{\bf x}\in\mathbb{R}^{n}}\nicefrac{{1}}{{2}}\|{\bf A}{\bf x}-{\bf b}\|_{{\bf R}^{-1}}^{2}, (1.3) to find the best linear unbiased estimator (BLUE); see [ 33 ] and [ 18 , Chapter 10] . Note that this reduces to ( 1.2 ) if the noise is Gaussian white since, in this case, {\bf R}=\sigma^{2}{\bf I} , where \sigma is the standard deviation. In many situations, the covariance matrix {\bf R} is not (fully) known but can be learned from the data. Indeed, often {\bf R} is assumed to have a parametric form whose parameters can be estimated by solving an optimization problem. However, this usually requires computing intermediate approximations of the solution \bar{{\bf x}}^{\ast} for an intermediate set of parameters, so these solvers typically rely on nested cycles of iterations (inner for approximating \bar{\bf x}^{\ast} , outer for updating {\bf R} ). Moreover, in some instances, {\bf R} might depend explicitly on the noiseless measurements, as in methods that approximate Poisson noise and other heteroskedastic distributions; see, e.g., [ 1 ] and [ 18 , Chapter 10] . Similarly, the solution of ( 1.1 ), where the noise distribution has an underlying sparsity assumption, can be well recovered by considering a p -norm data fit, so that \bar{{\bf x}}^{\ast}=\argmin_{{\bf x}\in\mathbb{R}^{n}}\nicefrac{{1}}{{p}}\|{\bf A}{\bf x}-{\bf b}\|_{p}^{p}, (1.4) with 0<p\leq 1 . This is the case, for instance, of impulse or salt-and-pepper noise. More generally, the value of p is linked to the assumption of the noise following a given Generalized Error Distribution, so that, from a statistical viewpoint, solving ( 1.4 ) corresponds to computing the maximum likelihood estimator; see [ 2 , 5 ] , and the references therein. Although sophisticated non-smooth and possibly non-convex optimization methods exist to handle these cases (see, e.g., [ 11 , 12 , 30 ] ), we consider an Iteratively Reweighted Least Squares (IRLS) approach; see [ 3 , Section 4.5.2] and, specifically for regularized inverse problems, [ 28 , 32 ] . IRLS methods can be regarded as specific instances of majorization-minimization (MM) methods, where a sequence of majorizing functions for ( 1.4 ) is constructed at successive approximations of \bar{\bf x}^{\ast} , each obtained by minimizing the corresponding majorant. More specifically, given an approximation \widetilde{{\bf x}} of a solution of ( 1.1 ), the objective function in ( 1.4 ) can be approximated by considering the objective function in ( 1.3 ) with weights {\bf R}^{-1}=({\bf W}(\widetilde{{\bf x}}))^{2}={\rm diag\!}\left(\left(({\bf A}\widetilde{{\bf x}}-{\bf b})^{2}+\tau^{2}\right)^{\frac{p-2}{2}}\right). (1.5) Note that all the above operations on vectors are performed entry-wise and the smoothing parameter \tau>0 is considered to avoid possible divisions by zero caused by the lack of smoothness of the objective function in ( 1.4 ) at zero. The choice of weights in ( 1.5 ) allows to interpret ( 1.3 ) as the tangent majorant of a smooth approximation of the original function at \widetilde{{\bf x}} (ignoring additive and multiplicative constants). Classical IRLS solvers consider a sequence of LS problems of the form ( 1.3 ), and iteratively update the matrix {\bf R}^{-1} by taking as \widetilde{{\bf x}} the solution of the previous LS problem ( 1.3 ) in the sequence, typically starting from {\bf R}^{-1}=({\bf W}({\bf 0}))^{2} . Since, in a general large-scale setting, each problem in the sequence is solved by CGLS or LSQR, IRLS solvers are actually inner-outer iterative schemes, whereby the weights are updated at each outer iteration. However, recently, more efficient IRLS formulations have been proposed, which enable to update the weights only after one iteration of the minimization algorithm has been performed (instead of a full solve). These solvers are typically based on ‘non-standard’ (such as flexible [ 7 , 15 ] or generalized [ 26 ] ) Krylov methods, and have been successfully considered to handle nonnegativity constraints in ( 1.2 ) [ 6 ] (possibly

Read the complete text