Regularized randomized iterative algorithms for factorized linear systems

DOI10.1016/J.AMC.2023.128468MaRDI QIDQ6128669zbMATH OpenOpenAlexFDO

Authors Kui Du

Publication date 16 April 2024

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2204.10722

zbMATH Keywords

factorized linear systemslinear convergencerandomized Gauss-Seidelrandomized Kaczmarzsparse (least squares) solutions

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Randomized algorithms (68W20) Convex programming (90C25)

Abstract: Randomized iterative algorithms for solving a factorized linear system, $mathbfAmathbfBmathbfx=mathbfb$ with $mathbfAin{mathbbR}^{mimesell}$, $mathbfBin{mathbbR}^{ellimesn}$, and $mathbfbin{mathbbR}^m$, have recently been proposed. They take advantage of the factorized form and avoid forming the matrix $mathbfC=mathbfAmathbfB$ explicitly. However, they can only find the minimum norm (least squares) solution. In contrast, the regularized randomized Kaczmarz (RRK) algorithm can find solutions with certain structures from consistent linear systems. In this work, by combining the randomized Kaczmarz algorithm or the randomized Gauss--Seidel algorithm with the RRK algorithm, we propose two novel regularized randomized iterative algorithms to find (least squares) solutions with certain structures of $mathbfAmathbfBmathbfx=mathbfb$. We prove linear convergence of the new algorithms. Computed examples are given to illustrate that the new algorithms can find sparse (least squares) solutions of $mathbfAmathbfBmathbfx=mathbfb$ and can be better than the existing randomized iterative algorithms for the corresponding full linear system $mathbfCmathbfx=mathbfb$ with $mathbfC=mathbfAmathbfB$.

Recommendations

• Iterative Methods for Solving Factorized Linear Systems
• On relaxed greedy randomized iterative methods for the solution of factorized linear systems
• A randomised iterative method for solving factorised linear systems
• An accelerated randomized Kaczmarz algorithm
• Randomized extended average block Kaczmarz for solving least squares

Cited in

(2)

• Two-sided preconditioned CGLS for the solution of factorized linear systems
• Surrogate hyperplane regularized iterative methods for sparse and structured solutions of factorized linear systems

This page was built for publication: Regularized randomized iterative algorithms for factorized linear systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6128669)