Primal-Dual methods for sparse constrained matrix completion


Yu Xin, Tommi Jaakkola ;
Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, PMLR 22:1323-1331, 2012.


We develop scalable algorithms for regular and non-negative matrix completion. In particular, we base the methods on trace-norm regularization that induces a low rank predicted matrix. The regularization problem is solved via a constraint generation method that explicitly maintains a sparse dual and the corresponding low rank primal solution. We provide a new dual block coordinate descent algorithm for solving the dual problem with a few spectral constraints. Empirical results illustrate the effectiveness of our method in comparison to recently proposed alternatives.

Related Material