An Implicit Representation and Iterative Solution of Randomly Sketched Linear Systems

DOI10.1137/19M1259481OpenAlexW3168376584MaRDI QIDQ4997835

Mohammad Jahangoshahi, Daniel Adrian Maldonado, Vivak Patel

Publication date: 30 June 2021

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

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

zbMATH Keywords

linear systemsorthogonalizationrandom iterative methodsrandom matrix sketching

Mathematics Subject Classification ID

Probabilistic methods, particle methods, etc. for boundary value problems involving PDEs (65N75) Analysis of algorithms (68W40) Iterative numerical methods for linear systems (65F10) Parallel numerical computation (65Y05) Randomized algorithms (68W20) Orthogonalization in numerical linear algebra (65F25)

Related Items (3)

Towards Practical Large-Scale Randomized Iterative Least Squares Solvers through Uncertainty Quantification ⋮ Randomized Block Adaptive Linear System Solvers ⋮ A weighted randomized sparse Kaczmarz method for solving linear systems

Uses Software

• Matrix Depot

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A randomized Kaczmarz algorithm with exponential convergence
• Linear algebra on high performance computers
• Almost sure convergence of the Kaczmarz algorithm with random measurements
• On the Meany inequality with applications to convergence analysis of several row-action iteration methods
• Rounding error analysis of the classical Gram-Schmidt orthogonalization process
• On the rate of convergence of the alternating projection method in finite dimensional spaces
• Randomized Extended Kaczmarz for Solving Least Squares
• Computational Advertising: Techniques for Targeting Relevant Ads
• Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
• Low-Rank Approximation and Regression in Input Sparsity Time
• Convergence Properties of the Randomized Extended Gauss--Seidel and Kaczmarz Methods
• Randomized Iterative Methods for Linear Systems
• Smallest singular value of a random rectangular matrix
• Row-Action Methods for Huge and Sparse Systems and Their Applications
• Practical Sketching Algorithms for Low-Rank Matrix Approximation
• On Greedy Randomized Kaczmarz Method for Solving Large Sparse Linear Systems
• An improved data stream summary: the count-min sketch and its applications
• Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory
• Analyzing random permutations for cyclic coordinate descent
• Approximate solution of systems of linear equations†
• The method of projections for finding the common point of convex sets
• The Relaxation Method for Linear Inequalities
• The Relaxation Method for Linear Inequalities
• Random permutations fix a worst case for cyclic coordinate descent
• Probability

This page was built for publication: An Implicit Representation and Iterative Solution of Randomly Sketched Linear Systems