Randomized low-rank approximation and its applications

In this thesis we will present and analyze randomized algorithms for numerical linear algebra problems. An important theme in this thesis is randomized low-rank approximation. In particular, we will study randomized low-rank approximation of matrix functions, the use of randomized low-rank approximation for trace estimation, and randomized low-rank approximation of self-adjoint non-negative trace class operators.Chapters 3 to 5 will be concerned with low-rank approximations of matrix functions. We will present two methods to compute low-rank approximations of matrix functions. In Chapter 4 we will analyze a method called funNyström, which uses a low-rank approximation to $\bm{A}$ to obtain a low-rank approximation to $f(\bm{A})$, where $f$ is a non-negative operator monotone function. In particular, we will show that a near-optimal Nyström low-rank approximation can be used to construct a near-optimal funNyström low-rank approximation. In Chapter 5 we will consider a block-Krylov subspace method to compute randomized low-rank approximations of general matrix-functions. We will provide probabilistic error bounds for the method.Chapters 6 to 8 will be concerned with trace estimation. In Chapter 7 we will present an adaptive version of the Hutch++ algorithm. This algorithm takes an error tolerance as input, and returns an estimate of the trace within the error tolerance with a controllable failure probability, while minimizing the number of matrix-vector products with the matrix. In Chapter 8 we present a single pass version of the Hutch++ algorithm. This algorithm uses the Nyström approximation instead of the randomized SVD in the low-rank approximation phase of Hutch++, and we prove that it satisfies a similar complexity guarantee as Hutch++.Chapter 9 will be concerned with an infinite-dimensional generalization of the Nyström approximation to compute randomized low-rank approximations to self-adjoint non-negative trace class operators. We will provide an error bound for the finite-dimensional Nyström approximation when it is implemented with non-standard Gaussian random vectors. We then use these bounds to prove an error bound for an infinite-dimensional generalization of the Nyström approximation.