2024/11/10 by Stefan Steinerberger, Steinerberger, Stefan · 1 citation
Computer Science · #FOS: Mathematics #Gaussian Processes and Bayesian Inference #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Probability (math.PR) #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2411.06614
openalex publication_date 2024/11/10 · openalex created_date 2024/11/15 · openalex updated_date 2026/07/28
The Kaczmarz method is a way to iteratively solve a linear system of equations Ax = b. One interprets the solution x as the point where hyperplanes intersect and then iteratively projects an approximate solution onto these hyperplanes to get better and better approximations. We note a somewhat related idea: one could take two random hyperplanes and project one into the orthogonal complement of the other. This leads to a sequence of linear systems A(k) x = b(k) which is fast to compute, preserves the original solution and whose small singular values grow like σℓ(A(k)) ∼ exp(k/n2) ⋅ σℓ(A).