|
||||||||||||||||
|
Ph.D. ThesesElement-wise 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 low-rank approximation (e.g., PCA) of a matrix, 2) recovering a partially-observed data (e.g., predicting incomplete ratings in a user-recommendation system), and many more. We consider three topics of research in element-wise sampling from a matrix. First, we show fast computation of low-rank approximation to A via a hybrid-(L1,L2) sampling. Second, we consider exact recovery of low-rank matrices via the nuclear norm minimization framework by observing the 'influential entries' of a matrix. Finally, we exploit the CUR-type low-rank approximation framework to construct an approximation of the original matrix. A common goal of all these methods is to produce high-quality 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.
|
||||||||||||||||
Research
