Randomized Extended Kaczmarz is a Limit Point of Sketch-and-Project
From MaRDI portal
Linear equations (linear algebraic aspects) (15A06) Random matrices (algebraic aspects) (15B52) Iterative numerical methods for linear systems (65F10) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Complexity and performance of numerical algorithms (65Y20) Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10) Randomized algorithms (68W20) Analysis of algorithms (68W40)
Abstract: 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. The randomized extended Kaczmarz (REK) method is a popular extension of randomized Kaczmarz for solving inconsistent systems, which has not yet been shown to lie within the SAP framework. In this work we show that, in a certain sense, REK may be expressed as the limit point of a family of SAP methods, but we argue that it is unlikely that REK can be translated into a SAP method itself. We provide an extensive theoretical analysis of the family of methods comprising said limit, including convergence guarantees and further connections to REK. We follow this with an array of experiments demonstrating these methods and their connections in practice.
This page was built for publication: Randomized Extended Kaczmarz is a Limit Point of Sketch-and-Project
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6380009)
