Iterative Methods for Solving Factorized Linear Systems
From MaRDI portal
Abstract: Stochastic iterative algorithms such as the Kaczmarz and Gauss-Seidel methods have gained recent attention because of their speed, simplicity, and the ability to approximately solve large-scale linear systems of equations without needing to access the entire matrix. In this work, we consider the setting where we wish to solve a linear system in a large matrix X that is stored in a factorized form, X = UV; this setting either arises naturally in many applications or may be imposed when working with large low-rank datasets for reasons of space required for storage. We propose a variant of the randomized Kaczmarz method for such systems that takes advantage of the factored form, and avoids computing X. We prove an exponential convergence rate and supplement our theoretical guarantees with experimental evidence demonstrating that the factored variant yields significant acceleration in convergence.
Recommendations
- A randomised iterative method for solving factorised linear systems
- scientific article; zbMATH DE number 1049350
- scientific article; zbMATH DE number 819140
- scientific article; zbMATH DE number 88927
- Iterative methods for the solution of large systems of linear equations
- Iterative methods for solving linear matrix equation and linear matrix system
- On the iterative methods for solving linear systems of equations
- New iterative methods for solving linear systems
- scientific article; zbMATH DE number 124176
Cites work
- A randomized Kaczmarz algorithm with exponential convergence
- Applied iterative methods.
- Comments on the randomized Kaczmarz method
- Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
- Exact matrix completion via convex optimization
- Fundamentals of Computerized Tomography
- Low-rank matrix completion using alternating minimization
- Matrix completion from noisy entries
- Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
- Randomized Kaczmarz solver for noisy linear systems
- Randomized extended Kaczmarz for solving least squares
- Randomized methods for linear constraints: convergence rates and conditioning
- Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
- The mathematics of computerized tomography
Cited in
(16)- Regularized randomized iterative algorithms for factorized linear systems
- Stochastic gradient descent for linear systems with missing data
- A new randomized Kaczmarz based kernel canonical correlation analysis algorithm with applications to information retrieval
- scientific article; zbMATH DE number 2222877 (Why is no real title available?)
- Randomized iterative methods for tensor regression under the t-product
- On maximum residual block and two-step Gauss-Seidel algorithms for linear least-squares problems
- Randomized double and triple Kaczmarz for solving extended normal equations
- A two-step randomized Gauss-Seidel method for solving large-scale linear least squares problems
- A randomised iterative method for solving factorised linear systems
- A doubly stochastic block Gauss-Seidel algorithm for solving linear equations
- Accelerated greedy randomized augmented Kaczmarz algorithm for inconsistent linear systems
- Two-sided preconditioned CGLS for the solution of factorized linear systems
- Randomized Kaczmarz methods for t-product tensor linear systems with factorized operators
- On relaxed greedy randomized iterative methods for the solution of factorized linear systems
- Splitting-based randomized iterative methods for solving indefinite least squares problem
- Randomized Kaczmarz for tensor linear systems
This page was built for publication: Iterative Methods for Solving Factorized Linear Systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3130425)
