"On the Provable Convergence of Alternating Minimization for Matrix Completion"
Moritz Hardt
(IBM Research)
Tuesday, February 18th, 2014, 2:00pm
EBU3B, Room 4140
Abstract:
Matrix Completion is the problem of recovering an unknown low-rank matrix from a subset of its entries. The problem has received considerable attention in Computer Science, Machine Learning, Statistics and Signal Processing and over the past years both due to its mathematical appeal and its applicability. Alternating Minimization is an empirically successful yet non-convex optimization heuristic for Matrix Completion. We give a new variant of Alternating Minimization that provably recovers an unknown low-rank matrix from a random subsample of its entries under a standard incoherence assumption. Compared to previous work our results reduce the formal sample complexity requirements of the Alternating Minimization approach by at least a quartic factor in the rank and the condition number of the unknown matrix. These improvements apply even in the noisy setting where the matrix is only close to low-rank in the Frobenius norm.
