High Dimensional Low-rank Matrix Completion,Algorithms And Applications

Matrix completion aims to recover a low-rank matrix from a samll sampling of its entries.It has a great number of applications in learaning systems,including recommender systems and computer vision.Many classical algorithms cannot scale to the massive sizes of mordern data sets.It is essential for algorithms with parallel and distributed computing architectures.One strategy is to improve the performance of current algorithms.Another strategy is to partition the whole big data set into several smaller data sets which can be tackled by existing algorithms,and then combine the results.In this thesis,a more efficient Singular Value Projection(SVP)algorithm is proposed by applying the Expectation-Maximization(EM)method for Principal Component Analysis(PCA).EM for PCA is an alternating minimization approach for finding the principal subspace,and can be easily implemented in parallel computing.With warm starts,the projection process can be computed efficiently.Under the sparse plus low-rank structure,EM for PCA can be implemented with the complexity in the order linear to the number of observed entries.Another important problem is how to determine the rank of the matrix.An empirical approach based on the Edge Distribution(ED)algorithm is proposed to estimate the rank of the matrix.Numerical experiments show that this method is promising for large-scale data sets.In practice,most real-world data sets exhibit nonuniformly distributed observations.Unfortunately,most existing algorithms are designed based on uniformly distributed observations.The Pareto principle states that most effects are the result of a few dominating causes.This principle also fits most matrix completion problems.In this thesis,a distributed matrix completion approach is proposed to recover a large-scale matrix from a dominating submatrix that is composed of a few most important rows and columns from the original matrix.The method for evaluating the importance of a row or column is inspired by the term frequency-inverse document frequency in natural language processing.The selected submatrix is recovered using an existing base matrix completion algorithm.Then,factors of the completed submatrix are used to retrieve the factors of the whole matrix.Numerical experiments demonstrate the effectiveness of this approach for recovering the matrix from nonuniformly distributed observations.In addition,this framework is naturally applicable for parallel and distributed computing,which is very encouraging for massive-sized data sets.At last,the distributed matrix completion method mentioned above is applied to solve the background modeling problem in video surveillance.In the first step,a heuristic strategy is used to remove the pixels which are possible foreground objects.After this,a video with missing pixels is obtained.In the second step,the background is recovered using the distributed matrix completion algorithm.In this section,a new method for evaluating the importance of pixels and images is proposed.Numerical experiments demonstrate that this approach can effectively reconstruct the background from various critical senses.In addition,this method is suitable for tackling high-resolution videos.