Fast Singular Value Projection for Low-Rank Matrix Completion

Abstract

Matrix completion problem aims to recover a low-rank matrix from a sampling of its entries. Singular value projection (SVP) is a projected gradient descent method, which iteratively makes an orthogonal projection onto a set of low-rank matrices. In this paper, we propose a more efficient SVP by applying the expectation-maximization (EM) algorithm for principal component analysis (PCA). EM for PCA is an alternating minimization approach for finding the principal subspace. With warm starts, the projection process can be computed efficiently. Under the sparse plus low-rank structure, we show that 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. We thus propose an empirically approach based on the edge distribution (ED) algorithm to estimate the rank. An imputation method is used in ED to enhance its applicability for matrix completion problem. Numerical experiments show that our method is promising for a wide range of problems.