Randomized Iterative Methods for Linear Systems
Randomized Iterative Methods for Linear Systems
We develop a novel, fundamental, and surprisingly simple randomized iterative method for solving consistent linear systems. Our method has six different but equivalent interpretations: sketch-and-project, constrain-and-approximate, random intersect, random linear solve, random update, and random fixed point. By varying its two parameters---a positive definite matrix (defining geometry), and a random …