Low-rank Matrix Completion using Alternating Minimization

Abstract

Alternating minimization represents a widely applicable and empirically successful approach for finding low-rank matrices that best fit the given data. For example, for the problem of low-rank matrix completion, this method is believed to be one of the most accurate and efficient, and formed a major component of the winning entry in the Netflix Challenge. In the alternating minimization approach, the low-rank target matrix is written in a bi-linear form, i.e. $X=U{V}^{†}$; the algorithm then alternates between finding the best $U$ and the best $V$. Typically, each alternating step in isolation is convex and tractable. However the overall problem becomes non-convex and there has been almost no theoretical understanding of when this approach yields a good result. In this paper we present first theoretical analysis of the performance of alternating minimization for matrix completion, and the related problem of matrix sensing. For both these problems, celebrated recent results have shown that they become well-posed and tractable once certain (now standard) conditions are imposed on the problem. We show that alternating minimization also succeeds under similar conditions. Moreover, compared to existing results, our paper shows that alternating minimization guarantees faster (in particular, geometric) convergence to the true matrix, while allowing a simpler analysis.

References in corpus (1)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization

Cited by in corpus (13)

• Universal Matrix Completion
• Statistical guarantees for the EM algorithm: From population to sample-based analysis
• Guarantees of Riemannian Optimization for Low Rank Matrix Completion
• Completing Any Low-rank Matrix, Provably
• The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences
• Ranking and synchronization from pairwise measurements via SVD
• A Non-convex One-Pass Framework for Generalized Factorization Machine and Rank-One Matrix Sensing
• Guarantees of Riemannian Optimization for Low Rank Matrix Recovery
• Rank $2r$ iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries
• Matrix Completion from $O(n)$ Samples in Linear Time
• Identifying Influential Entries in a Matrix
• Coordinate Descent Algorithms
• A Quadratically Convergent Algorithm for Structured Low-Rank Approximation