Algorithms for Matrix Approximation: Sketching, Sampling, and Sparse Optimization

 The approximation of matrices by smaller, simpler, or structured matrices is a fundamental problem in various fields of mathematics and computer science including numerical linear algebra, graph algorithms, computational geometry, signal processing, statistics, machine learning, and optimization. Recently, matrix approximation has been particularly important in modern computing as a key technique for efficiently processing enormous datasets in running time and memory scaling linearly, or even sublinearly, in the size of the dataset. In this thesis, we develop new and improved algorithms for a wide variety of matrix approximation tasks, drawing particularly heavily from sketching and sampling techniques from randomized numerical linear algebra, as well as sparse optimization techniques. We also utilize and develop connections of these problems with the literature of geometric functional analysis. 

We develop and improve foundational tools for matrix approximation, and find novel applications of these building blocks to solve central questions in matrix approximation. Some of the basic tools that we develop and sharpen include nearly optimal constructions of oblivious and non-oblivious subspace embeddings, improved low rank approximation algorithms, and new properties of ℓ1 regularization. Using our improved understanding of these primitives, we obtain a suite of applications such as the first polynomial space algorithms for high-dimensional computational geometry, nearly optimal algorithms for active linear regression, and the first nearly optimal coresets for multiple regression and subspace approximation. Many of our results have implications in big data computing settings, such as streaming, online, and distributed computation