Abstracts Physics

Flexible And Robust Iterative Methods For The Partial Singular Value Decomposition

by Steven Goldenberg

The Singular Value Decomposition (SVD) is one of the most fundamental matrix factorizations in linear algebra. As a generalization of the eigenvalue decomposition, the SVD is essential for a wide variety of fields including statistics, signal and image processing, chemistry, quantum physics and even weather prediction. The methods for numerically computing the SVD mostly fall under three main categories: direct, iterative, and streaming. Direct methods focus on solving the SVD in its entirety, making them suitable for smaller dense matrices where the computation cost is tractable. On the other end of the spectrum, streaming methods were created to provide an "on-line" algorithm that computes an approximate SVD as data is created or read-in over time. Consequently, they can also work on extremely large datasets that cannot fit within memory. To do this, they attempt to obtain only a few singular values and rely on probabilistic guarantees which limit their overall accuracy. Iterative SVD solvers fill in the large gap between these two extremes by providing accurate solutions for a subset of singular values on large (often sparse) matrices. In this dissertation, we focus on the development of flexible and robust iterative SVD solvers that provide fast convergence to high precision. We first introduce a novel iterative solver based on the Golub-Kahan and Davidson methods named GKD. GKD efficiently provides high-precision SVD solutions for large sparse matrices as demonstrated through comparisons with the PRIMME software package. Then, we investigate the use of flexible stopping criteria for GKD and other SVD solvers that are tailored to specific applications. Finally, we analyze the effect of SVD stopping criteria on matrix completion algorithms.