RANDOMIZED ALGORITHMS FOR LEAST SQUARES AND LOW RANK APPROXIMATION PROBLEMS

Abstract

In the thesis, we look at the implementation of randomized algorithms on two major topics in scientific computing - least squares (LS) and low rank approximation (LR) problems. By studying the properties of a random sketching matrix, we derive theorems composed of sufficient conditions for a general random matrix to produce a sketch that solves the two problems within the relative-error bound. Later inspired by features of the existing randomized and deterministic methods, we develop two new randomized algorithms – sparse subsampled randomized Hadamard transform (SpSRHT) mainly designed for least squares problems and sparse frequent-directions (SpFD) algorithm which solves the low rank approximation problems. Each algorithm is analyzed in detail with theoretical guarantee and improvement from the existing methods. The effectiveness and efficiency are also demonstrated by experimental results on synthetic and real world datasets as well as applications on network analysis.