

Research Ph.D. ThesesElementwise Matrix Sparsification and Reconstruction
By Abhisek Kundu
We consider the problem of selecting a small number of elements from a matrix A, and construct another matrix B from these elements, such that, B is close to A in some mathematical sense. Specifically, we sample a small number of elements from A ("Sparsification") according to various probability distributions defined on the elements of A, and we feed these samples to some algorithms to produce a matrix that is close to the original one ("Reconstruction"). We propose novel probability distributions on the elements of A, and we consider various reconstruction frameworks to recover A. These methods have applications in many real world problems, such as, 1) computing a fast lowrank approximation (e.g., PCA) of a matrix, 2) recovering a partiallyobserved data (e.g., predicting incomplete ratings in a userrecommendation system), and many more. We consider three topics of research in elementwise sampling from a matrix. First, we show fast computation of lowrank approximation to A via a hybrid(L1,L2) sampling. Second, we consider exact recovery of lowrank matrices via the nuclear norm minimization framework by observing the 'influential entries' of a matrix. Finally, we exploit the CURtype lowrank approximation framework to construct an approximation of the original matrix. A common goal of all these methods is to produce highquality approximation of a matrix using as few elements as possible. All the methods discussed here are provable, and they show good experimental results on synthetic and real data sets. Return to main PhD Theses page 

