Make the Most of What You Have: Resource-Efficient Randomized Algorithms for Matrix Computations

In recent years, randomized algorithms have established themselves as fundamental tools in computational linear algebra, with applications in scientific computing, machine learning, and quantum information science. Many randomized matrix algorithms proceed by first collecting information about a matrix and then processing that data to perform some computational task. This thesis addresses the following question: How can one design algorithms that use this information as efficiently as possible, reliably achieving the greatest possible speed and accuracy for a limited data budget? This question is timely, as randomized algorithms are increasingly being deployed in production software and in applications where accuracy and reliability is critical. The first part of this thesis focuses on the problem of low-rank approximation for positive-semidefinite matrices, motivated by applications to accelerating kernel and Gaussian process machine learning methods. Here, the goal is to compute an accurate approximation to a matrix after accessing as few entries of the matrix as possible. This part of the thesis explores the randomly pivoted Cholesky (RPCholesky) algorithm for this task, which achieves a level of speed and reliability greater than other methods for the same problem. The second part of this thesis considers the task of estimating attributes of an implicit matrix accessible only by matrix–vector products, motivated by applications in quantum physics, network science, and machine learning. This thesis describes the leave-one-out approach to developing matrix attribute estimation algorithms, and develops optimized trace, diagonal, and row-norm estimation algorithms for this computational model. The third part of this thesis considers randomized algorithms for overdetermined linear least squares problems, which arise in statistics and machine learning. Randomized algorithms for linear-least squares problems are asymptotically faster than any known deterministic algorithm, but recent work of [Meier et al., SIMAX '24] raised questions about the accuracy of these methods when implemented in floating point arithmetic. This thesis shows these issues are resolvable by developing fast randomized least-squares problem achieving backward stability, the gold-standard accuracy and stability guarantee for a numerical algorithm.