Search

This study investigates the iterative refinement method applied to the solution of linear discrete inverse problems by considering its application to the Tikhonov problem in mixed precision. Previous works on mixed precision iterative refinement methods for the solution of symmetric positive definite linear systems and least-squares problems have shown regularization to be a key requirement when computing low precision factorizations. For problems that are naturally severely ill-posed, we formulate the iterates of iterative refinement in mixed precision as a filtered solution using the preconditioned Landweber method with a Tikhonov-type preconditioner. Through numerical examples simulating various mixed precision choices, we showcase the filtering properties of the method and the achievement of comparable or superior accuracy compared to results computed in double precision as well as another approximate method., Comment: 22 pages

In this study, we introduce two new Krylov subspace methods for solving rectangular large-scale linear inverse problems. The first approach is a modification of the Hessenberg iterative algorithm that is based off an LU factorization and is therefore referred to as the least squares LU (LSLU) method. The second approach incorporates Tikhonov regularization in an efficient manner; we call this the Hybrid LSLU method. Both methods are inner-product free, making them advantageous for high performance computing and mixed precision arithmetic. Theoretical findings and numerical results show that Hybrid LSLU can be effective in solving large-scale inverse problems and has comparable performance with existing iterative projection methods.

This paper introduces LSEMINK, an effective modified Newton-Krylov algorithm geared toward minimizing the log-sum-exp function for a linear model. Problems of this kind arise commonly, for example, in geometric programming and multinomial logistic regression. Although the log-sum-exp function is smooth and convex, standard line search Newton-type methods can become inefficient because the quadratic approximation of the objective function can be unbounded from below. To circumvent this, LSEMINK modifies the Hessian by adding a shift in the row space of the linear model. We show that the shift renders the quadratic approximation to be bounded from below and that the overall scheme converges to a global minimizer under mild assumptions. Our convergence proof also shows that all iterates are in the row space of the linear model, which can be attractive when the model parameters do not have an intuitive meaning, as is common in machine learning. Since LSEMINK uses a Krylov subspace method to compute the search direction, it only requires matrix-vector products with the linear model, which is critical for large-scale problems. Our numerical experiments on image classification and geometric programming illustrate that LSEMINK considerably reduces the time-to-solution and increases the scalability compared to geometric programming and natural gradient descent approaches. It has significantly faster initial convergence than standard Newton-Krylov methods, which is particularly attractive in applications like machine learning. In addition, LSEMINK is more robust to ill-conditioning arising from the nonsmoothness of the problem. We share our MATLAB implementation at https://github.com/KelvinKan/LSEMINK.

We demonstrate the ability of hybrid regularization methods to automatically avoid the double descent phenomenon arising in the training of random feature models (RFM). The hallmark feature of the double descent phenomenon is a spike in the regularization gap at the interpolation threshold, i.e. when the number of features in the RFM equals the number of training samples. To close this gap, the hybrid method considered in our paper combines the respective strengths of the two most common forms of regularization: early stopping and weight decay. The scheme does not require hyperparameter tuning as it automatically selects the stopping iteration and weight decay hyperparameter by using generalized cross-validation (GCV). This also avoids the necessity of a dedicated validation set. While the benefits of hybrid methods have been well-documented for ill-posed inverse problems, our work presents the first use case in machine learning. To expose the need for regularization and motivate hybrid methods, we perform detailed numerical experiments inspired by image classification. In those examples, the hybrid scheme successfully avoids the double descent phenomenon and yields RFMs whose generalization is comparable with classical regularization approaches whose hyperparameters are tuned optimally using the test data. We provide our MATLAB codes for implementing the numerical experiments in this paper at https://github.com/EmoryMLIP/HybridRFM.

Adaptive optics (AO) corrected ood imaging of the retina is a popular technique for studying the retinal structure and function in the living eye. However, the raw retinal images are usually of poor contrast and the interpretation of such images requires image deconvolution. Different from standard deconvolution problems where the point spread function (PSF) is completely known, the PSF in these retinal imaging problems is only partially known which leads to the more complicated myopic (mildly blind) deconvolution problem. In this paper, we propose an efficient numerical scheme for solving this myopic deconvolution problem with total variational (TV) regularization. First, we apply the alternating direction method of multipliers (ADMM) to tackle the TV regularizer. Specifically, we reformulate the TV problem as an equivalent equality constrained problem where the objective function is separable, and then minimize the augmented Lagrangian function by alternating between two (separated) blocks of unknowns to obtain the solution. Due to the structure of the retinal images, the subproblems with respect to the fidelity term appearing within each ADMM iteration are tightly coupled and a variation of the Linearize And Project (LAP) method is designed to solve these subproblems efficiently. The proposed method is called the ADMM-LAP method. Theoretically, we establish the subsequence convergence of the ADMM-LAP method to a stationary point. Both the theoretical complexity analysis and numerical results are provided to demonstrate the efficiency of the ADMM-LAP method.

We present a new inner-outer iterative algorithm for edge enhancement in imaging problems. At each outer iteration, we formulate a Tikhonov-regularized problem where the penalization is expressed in the 2-norm and involves a regularization operator designed to improve edge resolution as the outer iterations progress, through an adaptive process. An efficient hybrid regularization method is used to project the Tikhonov-regularized problem onto approximation subspaces of increasing dimensions (inner iterations), while conveniently choosing the regularization parameter (by applying well-known techniques, such as the discrepancy principle or the ${\mathcal L}$-curve criterion, to the projected problem). This procedure results in an automated algorithm for edge recovery that does not involve regularization parameter tuning by the user, nor repeated calls to sophisticated optimization algorithms, and is therefore particularly attractive from a computational point of view. A key to the success of the new algorithm is the design of the regularization operator through the use of an adaptive diagonal weighting matrix that effectively enforces smoothness only where needed. We demonstrate the value of our approach on applications in X-ray CT image reconstruction and in image deblurring, and show that it can be computationally much more attractive than other well-known strategies for edge preservation, while providing solutions of greater or equal quality.

In this paper we propose an approach to approximate a truncated singular value decomposition of a large structured matrix. By first decomposing the matrix into a sum of Kronecker products, our approach can be used to approximate a large number of singular values and vectors more efficiently than other well known schemes, such as randomized matrix algorithms or iterative algorithms based on Golub-Kahan bidiagonalization. We provide theoretical results and numerical experiments to demonstrate the accuracy of our approximation and show how the approximation can be used to solve large scale ill-posed inverse problems, either as an approximate filtering method, or as a preconditioner to accelerate iterative algorithms.

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.

This paper focuses on efficient computational approaches to compute approximate solutions of a linear inverse problem that is contaminated with mixed Poisson--Gaussian noise, and when there are additional outliers in the measured data. The Poisson--Gaussian noise leads to a weighted minimization problem, with solution-dependent weights. To address outliers, the standard least squares fit-to-data metric is replaced by the Talwar robust regression function. Convexity, regularization parameter selection schemes, and incorporation of non-negative constraints are investigated. A projected Newton algorithm is used to solve the resulting constrained optimization problem, and a preconditioner is proposed to accelerate conjugate gradient Hessian solves. Numerical experiments on problems from image deblurring illustrate the effectiveness of the methods., Comment: 24 pages, 13 figures