UCLA

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.