Researcher ORCID Identifier
Open Access Senior Thesis
Bachelor of Science
© 2022 William Gilroy
Linear systems are fundamental in many areas of science and engineering. With the advent of computers there now exist extremely large linear systems that we are interested in. Such linear systems lend themselves to iterative methods. One such method is the family of algorithms called Randomized Kaczmarz methods.
Among this family, there exists a Randomized Kaczmarz variant called Randomized
Extended Kaczmarz which solves for least squares solutions in inconsistent linear systems.
Among Kaczmarz variants, Randomized Extended Kaczmarz is unique in that it modifies input system in a special way to solve for the least squares solution. In this work we unpack the geometry underlying Randomized Extended Kaczmarz
(REK) by uniting proofs by Zouzias and Freris (2013) and Du (2018), leading to more insight about why REK works. We also provide novel proofs showing: that REK will converge with an alternative sequence of z updates, and giving a closed form for REK’s original z updates. Lastly we have done some work generalizing the ideas behind REK and QuantileRK (Haddock et al., 2020) to lay foundations for a new Randomized Kaczmarz variant called Weighted Randomized Extended Kaczmarz (WREK) which aim to solve weighted least squares problems with dynamic reweightings.
Gilroy, William, "Check Yourself Before You WREK Yourself: Unpacking and Generalizing Randomized Extended Kaczmarz" (2022). HMC Senior Theses. 264.