Randomized extended Kaczmarz for solving least squares
From MaRDI portal
Publication:2848636
DOI10.1137/120889897zbMATH Open1273.65053arXiv1205.5770OpenAlexW3102157992MaRDI QIDQ2848636FDOQ2848636
Authors: Anastasios Zouzias, Nikolaos M. Freris 
Publication date: 26 September 2013
Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)
Abstract: We present a randomized iterative algorithm that exponentially converges in expectation to the minimum Euclidean norm least squares solution of a given linear system of equations. The expected number of arithmetic operations required to obtain an estimate of given accuracy is proportional to the square condition number of the system multiplied by the number of non-zeros entries of the input matrix. The proposed algorithm is an extension of the randomized Kaczmarz method that was analyzed by Strohmer and Vershynin.
Full work available at URL: https://arxiv.org/abs/1205.5770
Recommendations
- Randomized extended average block Kaczmarz for solving least squares
- Randomized block Kaczmarz method with projection for solving least squares
- Single projection Kaczmarz extended algorithms
- Randomized double and triple Kaczmarz for solving extended normal equations
- On two-subspace randomized extended Kaczmarz method for solving large linear least-squares problems
sparse matrixrandomized algorithmsrandom samplingiterative methodunderdetermined systemoverdetermined systemlinear least squaresLAPACKminimum-length solution
Computational methods for sparse matrices (65F50) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Iterative numerical methods for linear systems (65F10)
Cited In (only showing first 100 items - show all)
- On relaxed greedy randomized coordinate descent methods for solving large linear least-squares problems
- Randomized Kaczmarz with averaging
- A new randomized Kaczmarz based kernel canonical correlation analysis algorithm with applications to information retrieval
- A geometric probability randomized Kaczmarz method for large scale linear systems
- An accelerated randomized Kaczmarz algorithm
- A weighted randomized sparse Kaczmarz method for solving linear systems
- On greedy randomized average block Kaczmarz method for solving large linear systems
- Randomized Iterative Methods for Linear Systems
- Faster Randomized Block Kaczmarz Algorithms
- On Motzkin's method for inconsistent linear systems
- A refinement of an iterative orthogonal projection method
- Enhancement of the Kaczmarz algorithm with projection adjustment
- Projected randomized Kaczmarz methods
- On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems
- A weighted randomized Kaczmarz method for solving linear systems
- A Randomized Tensor Quadrature Method for High Dimensional Polynomial Approximation
- Randomized Kaczmarz Converges Along Small Singular Vectors
- On Adaptive Sketch-and-Project for Solving Linear Systems
- A Randomized Algorithm for Multivariate Function Approximation
- Randomized block Kaczmarz methods with \(k\)-means clustering for solving large linear systems
- A fast Kaczmarz-Kovarik algorithm for consistent least-squares problems
- The randomized Kaczmarz method with mismatched adjoint
- Incremental regularized least squares for dimensionality reduction of large-scale data
- Randomized Block Adaptive Linear System Solvers
- Sequential approximation of functions in Sobolev spaces using random samples
- Convergence Properties of the Randomized Extended Gauss--Seidel and Kaczmarz Methods
- Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
- Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
- On Convergence of the Partially Randomized Extended Kaczmarz Method
- Convergence Analysis of Inexact Randomized Iterative Methods
- A Deterministic Kaczmarz Algorithm for Solving Linear Systems
- Convergence analysis for Kaczmarz-type methods in a Hilbert space framework
- Distributed Algorithms with Finite Data Rates that Solve Linear Equations
- Regularized Kaczmarz Algorithms for Tensor Recovery
- Optimal CUR Matrix Decompositions
- A stochastic Kaczmarz algorithm for network tomography
- Title not available (Why is that?)
- Towards Practical Large-Scale Randomized Iterative Least Squares Solvers through Uncertainty Quantification
- 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 randomised iterative method for solving factorised linear systems
- The extensions of convergence rates of Kaczmarz-type methods
- The Kaczmarz algorithm, row action methods, and statistical learning algorithms
- Randomized Kaczmarz iteration methods: algorithmic extensions and convergence theory
- Approximate Solutions of Linear Systems at a Universal Rate
- A two-step randomized Gauss-Seidel method for solving large-scale linear least squares problems
- A greedy block Kaczmarz algorithm for solving large-scale linear systems
- Subspace correction methods in algebraic multi-level frames
- A doubly stochastic block Gauss-Seidel algorithm for solving linear equations
- Convergence rates for Kaczmarz-type algorithms
- On the generally randomized extended Gauss-Seidel method
- On the regularization effect of stochastic gradient descent applied to least-squares
- On the relation between the randomized extended Kaczmarz algorithm and coordinate descent
- Single projection Kaczmarz extended algorithms
- Randomized Extended Average Block Kaczmarz for Solving Least Squares
- Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
- On two-subspace randomized extended Kaczmarz method for solving large linear least-squares problems
- Randomized block Kaczmarz method with projection for solving least squares
- A Fast Block Coordinate Descent Method for Solving Linear Least-Squares Problems
- Iterative Methods for Solving Factorized Linear Systems
- A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility
- Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study
- A Kaczmarz Algorithm for Solving Tree Based Distributed Systems of Equations
- On the error estimate of the randomized double block Kaczmarz method
- Randomized Kaczmarz solver for noisy linear systems
- Hildreth's algorithm with applications to soft constraints for user interface layout
- A note on convergence rate of randomized Kaczmarz method
- Block Kaczmarz method with inequalities
- A randomized Kaczmarz algorithm with exponential convergence
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Sequential function approximation on arbitrarily distributed point sets
- On Relaxed Greedy Randomized Augmented Kaczmarz Methods for Solving Large Sparse Inconsistent Linear Systems
- Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory
- A new greedy Kaczmarz algorithm for the solution of very large linear systems
- Rows versus Columns: Randomized Kaczmarz or Gauss--Seidel for Ridge Regression
- Linear convergence of the randomized sparse Kaczmarz method
- Random reordering in SOR-type methods
- Choosing relaxation parameter in randomized Kaczmarz method
- On extended Kaczmarz methods with random sampling and maximum-distance for solving large inconsistent linear systems
- A randomized sparse Kaczmarz solver for sparse signal recovery via minimax-concave penalty
- On constrained Kaczmarz algorithm with momentum for image reconstruction
- Faster randomized block sparse Kaczmarz by averaging
- Surrounding the solution of a linear system of equations from all sides
- Maximal residual extended Kaczmarz and Gauss-Seidel methods-convergence properties and applications
- A modified partially randomized extended Kaczmarz iteration method
- A class of pseudoinverse-free greedy block nonlinear Kaczmarz methods for nonlinear systems of equations
- On adaptive stochastic heavy ball momentum for solving linear systems
- Optimization of random feature method in the high-precision regime
- On a fast deterministic block Kaczmarz method for solving large-scale linear systems
- Machine learning with kernels for portfolio valuation and risk management
- Sampled limited memory methods for massive linear inverse problems
- Accelerating the distributed Kaczmarz algorithm by strong over-relaxation
- On multi-step extended maximum residual Kaczmarz method for solving large inconsistent linear systems
- Stochastic iterative methods for online rank aggregation from pairwise comparisons
- Tensor randomized extended Kaczmarz methods for large inconsistent tensor linear equations with t-product
- Average block column action methods for solving least squares problems
- A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitation
- Greedy Kaczmarz Algorithm Using Optimal Intermediate Projection Technique for Coherent Linear Systems
- Kaczmarz-type methods for solving matrix equations
- A randomized block Douglas-Rachford method for solving linear matrix equation
Uses Software
This page was built for publication: Randomized extended Kaczmarz for solving least squares
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848636)
