Silvia Gazzola

Silvia Gazzola, Per Christian Hansen, James G. Nagy

This paper describes a new MATLAB software package of iterative regularization methods and test problems for large-scale linear inverse problems. The software package, called IR Tools, serves two related purposes: we provide implementations of a range of iterative solvers, including several recently proposed methods that are not available elsewhere, and we provide a set of large-scale test problems in the form of discretizations of 2D linear inverse problems. The solvers include iterative regularization methods where the regularization is due to the semi-convergence of the iterations, Tikhonov-type formulations where the regularization is explicitly formulated in the form of a regularization term, and methods that can impose bound constraints on the computed solutions. All the iterative methods are implemented in a very flexible fashion that allows the problem's coefficient matrix to be available as a (sparse) matrix, a function handle, or an object. The most basic call to all of the various iterative methods requires only this matrix and the right hand side vector; if the method uses any special stopping criteria, regularization parameters, etc., then default values are set automatically by the code. Moreover, through the use of an optional input structure, the user can also have full control of any of the algorithm parameters. The test problems represent realistic large-scale problems found in image reconstruction and several other applications. Numerical examples illustrate the various algorithms and test problems available in this package.

Silvia Gazzola, Silvia Noschese, Paolo Novati et al.

GMRES is one of the most popular iterative methods for the solution of large linear systems of equations that arise from the discretization of linear well-posed problems, such as Dirichlet boundary value problems for elliptic partial differential equations. The method is also applied to iteratively solve linear systems of equations that are obtained by discretizing linear ill-posed problems, such as many inverse problems. However, GMRES does not always perform well when applied to the latter kind of problems. This paper seeks to shed some light on reasons for the poor performance of GMRES in certain situations, and discusses some remedies based on specific kinds of preconditioning. The standard implementation of GMRES is based on the Arnoldi process, which also can be used to define a solution subspace for Tikhonov or TSVD regularization, giving rise to the Arnoldi-Tikhonov and Arnoldi-TSVD methods, respectively. The performance of the GMRES, the Arnoldi-Tikhonov, and the Arnoldi-TSVD methods is discussed. Numerical examples illustrate properties of these methods.

Silvia Gazzola, Yves Wiaux

Constrained least squares problems arise in a variety of applications, and many iterative methods are already available to compute their solutions. This paper proposes a new efficient approach to solve nonnegative linear least squares problems. The associated KKT conditions are leveraged to form an adaptively preconditioned linear system, which is then solved by a flexible Krylov subspace method. The new method can be easily applied to image reconstruction problems affected by both Gaussian and Poisson noise, where the components of the solution represent nonnegative intensities. {Theoretical insight is given, and} numerical experiments and comparisons are displayed in order to validate the new method, which delivers results of equal or better quality than many state-of-the-art methods for nonnegative least squares solvers, with a significant speedup.

Julianne Chung, Silvia Gazzola

In this paper we develop flexible Krylov methods for efficiently computing regularized solutions to large-scale linear inverse problems with an $\ell_2$ fit-to-data term and an $\ell_p$ penalization term, for $p\geq 1$. First we approximate the $p$-norm penalization term as a sequence of $2$-norm penalization terms using adaptive regularization matrices in an iterative reweighted norm fashion, and then we exploit flexible preconditioning techniques to efficiently incorporate the weight updates. To handle general (non-square) $\ell_p$-regularized least-squares problems, we introduce a flexible Golub-Kahan approach and exploit it within a Krylov-Tikhonov hybrid framework. The key benefits of our approach compared to existing optimization methods for $\ell_p$ regularization are that efficient projection methods replace inner-outer schemes and that expensive regularization parameter selection techniques can be avoided. Theoretical insights are provided, and numerical results from image deblurring and tomographic reconstruction illustrate the benefits of this approach, compared to well-established methods. Furthermore, we show that our approach for $p=1$ can be used to efficiently compute solutions that are sparse with respect to some transformations.

Alberto Bucci, Silvia Gazzola, Leonardo Robol

LSQR and LSMR are iterative methods, based on the Golub-Kahan bidiagonalization algorithm, widely used for large-scale linear least squares problems. FLSQR and FLSMR are flexible variants of LSQR and LSMR, respectively, based on a flexible Golub-Kahan (Arnoldi-like) factorization algorithm, which naturally allow modifications of the solution approximation subspace and/or handling inexact matrix-vector multiplications with the (transpose of the) coefficient matrix, thereby enabling to enforce prior information into the computed solution. The goal of this paper is to introduce sFLSQR and sFLSMR, i.e., sketched variants of FLSQR and FLSMR, respectively, where randomization becomes particularly effective, as it allows to recover short recurrences for the solution approximation. In particular, this paper explores applications to large-scale inverse problems, showing the ability of the new randomized solvers to alleviate computational bottlenecks while preserving reconstruction quality. A theoretical analysis of sFLSQR and sFLSMR is provided, and their performance is validated through numerical experiments.

Matthias J. Ehrhardt, Silvia Gazzola, Sebastian J. Scott

Variational regularization is commonly used to solve linear inverse problems, and involves augmenting a data fidelity by a regularizer. The regularizer is used to promote a priori information and is weighted by a regularization parameter. Selection of an appropriate regularization parameter is critical, with various choices leading to very different reconstructions. Classical strategies used to determine a suitable parameter value include the discrepancy principle and the L-curve criterion, and in recent years a supervised machine learning approach called bilevel learning has been employed. Bilevel learning is a powerful framework to determine optimal parameters and involves solving a nested optimization problem. While previous strategies enjoy various theoretical results, the well-posedness of bilevel learning in this setting is still an open question. In particular, a necessary property is positivity of the determined regularization parameter. In this work, we provide a new condition that better characterizes positivity of optimal regularization parameters than the existing theory. Numerical results verify and explore this new condition for both small and high-dimensional problems.

Silvia Gazzola, Paolo Novati

This paper introduces and analyzes an original class of Krylov subspace methods that provide an efficient alternative to many well-known conjugate-gradient-like (CG-like) Krylov solvers for square nonsymmetric linear systems arising from discretizations of inverse ill-posed problems. The main idea underlying the new methods is to consider some rank-deficient approximations of the transpose of the system matrix, obtained by running the (transpose-free) Arnoldi algorithm, and then apply some Krylov solvers to a formally right-preconditioned system of equations. Theoretical insight is given, and many numerical tests show that the new solvers outperform classical Arnoldi-based or CG-like methods in a variety of situations.