Randomized Extended Kaczmarz is a Limit Point of Sketch-and-Project
share
The sketch-and-project (SAP) framework for solving systems of linear equations has unified the theory behind popular projective iterative methods such as randomized Kaczmarz, randomized coordinate descent, and variants thereof. We show that the randomized extended Kaczmarz (REK) method - so far not shown to lie within this framework - cannot be formulated as a SAP method, a surprising result as it is of a very similar flavor. We show, in fact, that REK may instead be recovered as a limit point of a particular family of SAP methods. We provide an extensive theoretical analysis of said family, including convergence guarantees and further connections to REK. We follow this with an array of experiments demonstrating these methods and their connections in practice.
READ FULL TEXT