Surrounding the solution of a linear system of equations from all sides

DOI10.1090/QAM/1587MaRDI QIDQ4997183zbMATH OpenOpenAlexFDO

Authors Stefan Steinerberger

Publication date 28 June 2021

Published in Quarterly of Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Kaczmarz methodlinear systemsrandom geometry

Mathematics Subject Classification ID

Linear equations (linear algebraic aspects) (15A06) Theory of matrix inversion and generalized inverses (15A09) Random convex sets and integral geometry (aspects of convex geometry) (52A22) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Geometric probability and stochastic geometry (60D05) Iterative numerical methods for linear systems (65F10) Large-scale problems in mathematical programming (90C06)

Abstract: Suppose $Ainmathbb{R}^{nimesn}$ is invertible and we are looking for the solution of $Ax=b$. Given an initial guess $x_{1}inmathbbR$, we show that by reflecting through hyperplanes generated by the rows of $A$, we can generate an infinite sequence $(x_k{)}_{k=1}^{infty}$ such that all elements have the same distance to the solution, i.e. $|x_k-x|=|x_1-x|$. If the hyperplanes are chosen at random, averages over the sequence converge and ${\displaystyle }$ mathbb{E} left| x - frac{1}{m} sum_{k=1}^{m}{ x_k} ight| leq frac{1 + |A|_F |A^{-1}|}{sqrt{m}} cdot|x-x_1|.${\displaystyle }$ The bound does not depend on the dimension of the matrix. This introduces a purely geometric way of attacking the problem: are there fast ways of estimating the location of the center of a sphere from knowing many points on the sphere? Our convergence rate (coinciding with that of the Random Kaczmarz method) comes from averaging, can one do better?

Recommendations

• Enclosing Solutions of Linear Equations
• scientific article; zbMATH DE number 3883493
• scientific article; zbMATH DE number 5056125
• scientific article; zbMATH DE number 61062
• On the Solution of Circulant Linear Systems
• scientific article; zbMATH DE number 56825
• scientific article; zbMATH DE number 3894801
• scientific article; zbMATH DE number 58447
• A note on solutions of linear systems
• scientific article; zbMATH DE number 3847215

Cites work

• A derandomization approach to recovering bandlimited signals across a wide range of random sampling rates
• A new greedy Kaczmarz algorithm for the solution of very large linear systems
• A randomized Kaczmarz algorithm with exponential convergence
• Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
• AIR tools -- a MATLAB package of algebraic iterative reconstruction methods
• An accelerated randomized Kaczmarz algorithm
• Component averaging: An efficient iterative parallel algorithm for large and sparse unstructured problems
• Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
• Convergence rates for Kaczmarz-type algorithms
• scientific article; zbMATH DE number 3856876 (Why is no real title available?)
• scientific article; zbMATH DE number 3919670 (Why is no real title available?)
• scientific article; zbMATH DE number 4001918 (Why is no real title available?)
• scientific article; zbMATH DE number 4021000 (Why is no real title available?)
• On Adaptive Sketch-and-Project for Solving Linear Systems
• On Diagonally Relaxed Orthogonal Projection Methods
• On the rate of convergence of the alternating projection method in finite dimensional spaces
• Paved with good intentions: analysis of a randomized block Kaczmarz method
• Preasymptotic convergence of randomized Kaczmarz method
• Randomized block Kaczmarz method with projection for solving least squares
• Randomized extended Kaczmarz for solving least squares
• Randomized iterative methods for linear systems
• Randomized Kaczmarz Converges Along Small Singular Vectors
• Randomized Kaczmarz solver for noisy linear systems
• Randomized Kaczmarz with averaging
• Randomized methods for linear constraints: convergence rates and conditioning
• Semi-convergence properties of Kaczmarz's method
• Stochastic gradient descent for linear systems with missing data
• Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
• The rate of convergence for the method of alternating projections. II
• Two-subspace projection method for coherent overdetermined systems

Cited in

(12)

• Restarted randomized surrounding methods for solving large linear equations
• A Deterministic Kaczmarz Algorithm for Solving Linear Systems
• Approximate Solutions of Linear Systems at a Universal Rate
• The Reflection Method for the Numerical Solution of Linear Systems
• Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency
• A randomized block Douglas-Rachford method for solving linear matrix equation
• Reflective block Kaczmarz algorithms for least squares
• The randomized circumcentered-reflection iteration method for solving consistent linear equations
• A unified convergence analysis of random sketch methods for rank deficient linear systems
• A Kaczmarz-inspired method for orthogonalization
• Accelerating randomized surrounding method with momentum for consistent linear systems
• Kaczmarz Kac walk

Describes a project that uses

Uses Software

• AIR tools

This page was built for publication: Surrounding the solution of a linear system of equations from all sides

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