Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published April 2018 | public
Book Section - Chapter

An Improved Initialization for Low-Rank Matrix Completion Based on Rank-L Updates

Abstract

Given a data matrix with partially observed entries, the low-rank matrix completion problem is one of finding a matrix with the lowest rank that perfectly fits the given observations. While there exist convex relaxations for the low-rank completion problem, the underlying problem is inherently nonconvex, and most algorithms (alternating projection, Riemannian optimization, etc.) heavily depend on the initialization. This paper proposes an improved initialization that relies on successive rank-l updates. Further, the paper proposes theoretical guarantees under which the proposed initialization is closer to the unknown optimal solution than the all zeros initialization in the Frobenius norm. To cope with the problem of local minima, the paper introduces and uses random norms to change the position of the local minima while preserving the global one. Using a Riemannian optimization routine, simulation results reveal that the proposed solution succeeds in completing Gaussian partially observed matrices with a random set of revealed entries close to the information-theoretical limits, thereby significantly improving on prior methods.

Additional Information

© 2018 IEEE. The authors would like to thank Dr. Philipp Walk for his helpful comments and suggestions.

Additional details

Created:
August 19, 2023
Modified:
March 5, 2024