Matrix Factorization From a Few Dominators.

Abstract

The Pareto principle states that most effects are the result of a few dominating causes. This principle also fits most matrix completion problems. In practice, most real-world data sets exhibit nonuniformly distributed observations. Unfortunately, most existing algorithms are designed based on uniformly distributed observations. In this brief, we propose a matrix factorization approach 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 factorization algorithm. Then, factors of the completed submatrix are used to retrieve the factors of the whole matrix via a linear regression model. Numerical experiments demonstrate the effectiveness of our approach for recovering the matrix from nonuniformly distributed observations. In addition, our framework is naturally applicable for parallel and distributed computing, which is very encouraging for massive-sized data sets.