Approximation of Positive Semidefinite Matrices Using the Nyström Method

Positive semidefinite matrices arise in a variety of fields, including statistics, signal processing, and machine learning. Unfortunately, when these matrices are high-dimensional and/or must be operated upon many times, expensive calculations such as the spectral decomposition quickly become a computational bottleneck. A common alternative is to replace the original positive semidefinite matrices with low-rank approximations whose spectral decompositions can be more easily computed. In this thesis, we develop approaches based on the Nyström method, which approximates a positive semidefinite matrix using a data-dependent orthogonal projection. As the Nyström approximation is conditioned on a given principal submatrix of its argument, it essentially recasts low-rank approximation as a subset selection problem. We begin by deriving the Nyström approximation and developing a number of fundamental results, including new characterizations of its spectral properties and approximation error. We then address the problem of subset selection through a study of randomized sampling algorithms. We provide new bounds for the approximation error under uniformly rando