Mathematical and Computational Framework for Matrix Completion with Nonuniform Sampling in Resource Constrained Environments

Matrix completion (MC) concerns the problem of recovering a low rank matrix from a given small fraction of its entries. It is a recurring problem in collaborative filtering, dimensionality reduction, and multi-class learning and has a long history in mathematics. While the general problem of finding the lowest rank matrix satisfying a set of equality constraints is NP-hard, there are quite general settings where it is possible to perfectly recover all of the missing entries of a low-rank matrix by solving a convex optimization problem. One of our team (Recht) has shown how this convex programming heuristic can be used to reconstruct most n x n matrices of rank r from most collections of entries, provided that the number of entries exceeds C n r log2n for some small, positive numerical constant C. This work extended mathematical results from compressive sensing, in particular building upon its geometric ideas. We propose a nine month research program with three lines of investigation: (i) extend current MC approaches to incorporate nonuniform sampling matrices and resource constraints; (ii) implementation of on-line MC algorithms; and (iii) extend current MC approaches to incorporate regularization schemes beyond rank and sparsity.