Please use this identifier to cite or link to this item: https://scholarbank.nus.edu.sg/handle/10635/137525
Title: RANDOMIZED ALGORITHMS FOR LEAST SQUARES AND LOW RANK APPROXIMATION PROBLEMS
Authors: TENG DAN
Keywords: Randomized algorithms, Least squares, Low Rank Approximation
Issue Date: 25-Aug-2017
Citation: TENG DAN (2017-08-25). RANDOMIZED ALGORITHMS FOR LEAST SQUARES AND LOW RANK APPROXIMATION PROBLEMS. ScholarBank@NUS Repository.
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.
URI: http://scholarbank.nus.edu.sg/handle/10635/137525
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
TengD.pdf3.13 MBAdobe PDF

OPEN

NoneView/Download

Page view(s)

223
checked on Sep 25, 2020

Download(s)

10
checked on Sep 25, 2020

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.