Krylov methods for low-rank regularization
From MaRDI portal
Abstract: This paper introduces new solvers for the computation of low-rank approximate solutions to large-scale linear problems, with a particular focus on the regularization of linear inverse problems. Although Krylov methods incorporating explicit projections onto low-rank subspaces are already used for well-posed systems that arise from discretizing stochastic or time-dependent PDEs, we are mainly concerned with algorithms that solve the so-called nuclear norm regularized problem, where a suitable nuclear norm penalization on the solution is imposed alongside a fit-to-data term expressed in the 2-norm: this has the effect of implicitly enforcing low-rank solutions. By adopting an iteratively reweighted norm approach, the nuclear norm regularized problem is reformulated as a sequence of quadratic problems, which can then be efficiently solved using Krylov methods, giving rise to an inner-outer iteration scheme. Our approach differs from the other solvers available in the literature in that: (a) Kronecker product properties are exploited to define the reweighted 2-norm penalization terms; (b) efficient preconditioned Krylov methods replace gradient (projection) methods; (c) the regularization parameter can be efficiently and adaptively set along the iterations. Furthermore, we reformulate within the framework of flexible Krylov methods both the new inner-outer methods for nuclear norm regularization and some of the existing Krylov methods incorporating low-rank projections. This results in an even more computationally efficient (but heuristic) strategy, that does not rely on an inner-outer iteration scheme. Numerical experiments show that our new solvers are competitive with other state-of-the-art solvers for low-rank problems, and deliver reconstructions of increased quality with respect to other classical Krylov methods.
Recommendations
- Flexible Krylov methods for \(\ell_p\) regularization
- Regularization by inexact Krylov methods with applications to blind deblurring
- Tikhonov regularization based on generalized Krylov subspace methods
- On the convergence of Krylov methods with low-rank truncations
- On Krylov projection methods and Tikhonov regularization
Cites work
- A Bidiagonalization-Regularization Procedure for Large Scale Discretizations of Ill-Posed Problems
- A Flexible Inner-Outer Preconditioned GMRES Algorithm
- A low-rank in time approach to PDE-constrained optimization
- A preconditioned low-rank projection method with a rank-reduction scheme for stochastic partial differential equations
- A Singular Value Thresholding Algorithm for Matrix Completion
- CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion
- Choosing regularization parameters in iterative methods for ill-posed problems
- Convergence of fixed-point continuation algorithms for matrix rank minimization
- Convex Analysis
- Discrete inverse problems. Insight and algorithms.
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Fixed point and Bregman iterative methods for matrix rank minimization
- Flexible GMRES for total variation regularization
- Flexible Krylov methods for \(\ell_p\) regularization
- Generalized Arnoldi-Tikhonov method for sparse reconstruction
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- scientific article; zbMATH DE number 6276219 (Why is no real title available?)
- Hybrid and iteratively reweighted regularization by unbiased predictive risk and weighted GCV for projected systems
- IR tools: a MATLAB package of iterative regularization methods and large-scale test problems
- Iterative regularization with minimum-residual methods
- Low-rank matrix recovery via iteratively reweighted least squares minimization
- Low-rank tensor Krylov subspace methods for parametrized linear systems
- Matrix completion from noisy entries
- On Krylov projection methods and Tikhonov regularization
- Recent computational developments in Krylov subspace methods for linear systems
- Regularization methods for large-scale problems
- Smoothed Low Rank and Sparse Matrix Recovery by Iteratively Reweighted Least Squares Minimization
- Smoothing‐Norm Preconditioning for Regularizing Minimum‐Residual Methods
- Wavelet domain image restoration with adaptive edge-preserving regularization
Cited in
(13)- Rank-k modification methods for recursive least squares problems
- Proximal linearization methods for Schatten p-quasi-norm minimization
- Numerical methods for CT reconstruction with unknown geometry parameters
- Regularized computation of approximate pseudoinverse of large matrices using low-rank tensor train decompositions
- An efficient approach for computing optimal low-rank regularized inverse matrices
- Reliable Krylov-based algorithms for matrix null space and rank
- Low-Rank Updates of Matrix Functions II: Rational Krylov Methods
- Regularization by inexact Krylov methods with applications to blind deblurring
- Flexible Krylov methods for \(\ell_p\) regularization
- Optimal regularized inverse matrices for inverse problems
- A framework for studying the regularizing properties of Krylov subspace methods
- Krylov methods for inverse problems: Surveying classical, and introducing new, algorithmic approaches
- Matrix-free Krylov iteration for implicit convolution of numerically low-rank data
This page was built for publication: Krylov methods for low-rank regularization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5146618)
