Greedy algorithms for matrix approximation via the interlacing polynomial method

Abstract

With high-dimensional datasets becoming increasingly common across various fields, dimensionality reduction has become a crucial process. Low-rank matrix approximation is an essential technique for this purpose. One class of low-rank approximation techniques involves generalized column and row subset selection, where specific columns and rows are chosen from source matrices to approximate the column and row space of the target matrix, respectively. In this thesis, we explore novel greedy algorithms for generalized column and row subset selection. We introduce greedy algorithms for three specific cases: column subset selection (CSS), generalized column subset selection (GCSS), and sparse coding. Our algorithms build on the theoretical work by Cai et al. [14], which uses the interlacing polynomial method to establish tight bounds for the error in these low-rank matrix approximation problems. The development of our new greedy algorithms is directly inspired by the proof steps of the main theorems presented in [14]. Experimental results indicate that our new greedy algorithms achieve superior accuracy compared to existing methods, although they are more computationally intensive.

Date of Award	2024
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology
Supervisor	Ke WANG (Supervisor) & Jianfeng CAI (Supervisor)