Subspace Evolution and Transfer (SET) for Low-Rank Matrix Completion

Abstract

We describe a new algorithm, termed subspace evolution and transfer (SET), for solving low-rank matrix completion problems. The algorithm takes as its input a subset of entries of a low-rank matrix, and outputs one low-rank matrix consistent with the given observations. The completion task is accomplished by searching for a column space on the Grassmann manifold that matches the incomplete observations. The SET algorithm consists of two parts -- subspace evolution and subspace transfer. In the evolution part, we use a gradient descent method on the Grassmann manifold to refine our estimate of the column space. Since the gradient descent algorithm is not guaranteed to converge, due to the existence of barriers along the search path, we design a new mechanism for detecting barriers and transferring the estimated column space across the barriers. This mechanism constitutes the core of the transfer step of the algorithm. The SET algorithm exhibits excellent empirical performance for both high and low sampling rate regimes.

References in corpus (4)

• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Matrix Completion from a Few Entries
• Guaranteed Rank Minimization via Singular Value Projection
• A Geometric Approach to Low-Rank Matrix Completion

Cited by in corpus (16)

• An overview of low-rank matrix recovery from incomplete observations
• Subspace Learning and Imputation for Streaming Big Data Matrices and Tensors
• PETRELS: Parallel Subspace Estimation and Tracking by Recursive Least Squares from Partial Observations
• Online Robust Subspace Tracking from Partial Information
• Alternating Least-Squares for Low-Rank Matrix Reconstruction
• Low-Rank Positive Semidefinite Matrix Recovery from Corrupted Rank-One Measurements
• Robust Low-rank Matrix Completion via an Alternating Manifold Proximal Gradient Continuation Method
• Low-rank matrix completion by Riemannian optimization---extended version
• MC2G: An Efficient Algorithm for Matrix Completion with Social and Item Similarity Graphs
• Accelerated 2D magnetic resonance spectroscopy of single spins using matrix completion
• Riemannian Perspective on Matrix Factorization
• Two Newton methods on the manifold of fixed-rank matrices endowed with Riemannian quotient geometries
• A Riemannian gossip approach to subspace learning on Grassmann manifold
• Asymptotic Log-Det Rank Minimization via (Alternating) Iteratively Reweighted Least Squares
• Minimum $n$-Rank Approximation via Iterative Hard Thresholding
• Community Detection and Matrix Completion with Social and Item Similarity Graphs