Kaczmarz Methods and Structured Matrix Decompositions

In this dissertation, we discuss two distinct topics, both of which leverage randomized algorithms in numerical linear algebra. First we study three variants of the Kaczmarz method, a stochastic iterative method for solving linear systems. We propose a variant of the Kaczmarz method that uses additional memory to save on computation. We provide theoretical analysis and experimental results of the method, highlighting a gap in the literature. Additionally, we propose a variant of the Kaczmarz method in the data streaming setting that has an additional heavy ball momentum term. We prove a convergence bound for this method and analyze its merits experimentally given coherent data. Furthermore, we develop a variant of the Kaczmarz method for solving a latent class regression problem. Next we shift gears and discuss structured matrix factorizations. The first matrix factorization that we propose is a stratified non-negative matrix factorization. The aim of this method is to provide unsupervised dimensionality reduction on non-negative data that may be distributed across different locations. We prove a convergence bound for this method and analyze its performance on synthetic text, image and tabular data. Finally, we propose a hierarchically semi-separable matrix factorization method that uses random matrix sketching.