Guarantees of Riemannian Optimization for Low Rank Matrix Completion

Abstract

We study the Riemannian optimization methods on the embedded manifold of low rank matrices for the problem of matrix completion, which is about recovering a low rank matrix from its partial entries. Assume $m$ entries of an $n\times n$ rank $r$ matrix are sampled independently and uniformly with replacement. We first prove that with high probability the Riemannian gradient descent and conjugate gradient descent algorithms initialized by one step hard thresholding are guaranteed to converge linearly to the measured matrix provided \begin{align*} m\geq C_κn^{1.5}r\log^{1.5}(n), \end{align*} where $C_{\kappa }$ is a numerical constant depending on the condition number of the underlying matrix. The sampling complexity has been further improved to \begin{align*} m\geq C_κnr^2\log^{2}(n) \end{align*} via the resampled Riemannian gradient descent initialization. The analysis of the new initialization procedure relies on an asymmetric restricted isometry property of the sampling operator and the curvature of the low rank matrix manifold. Numerical simulation shows that the algorithms are able to recover a low rank matrix from nearly the minimum number of measurements.

References in corpus (3)

• Blind Deconvolution Meets Blind Demixing: Algorithms and Performance Bounds
• Low-rank Matrix Completion using Alternating Minimization
• Guarantees of Riemannian Optimization for Low Rank Matrix Recovery

Cited by in corpus (15)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Provable Tensor-Train Format Tensor Completion by Riemannian Optimization
• Solving systems of phaseless equations via Riemannian optimization with optimal sampling complexity
• Guarantees of Riemannian Optimization for Low Rank Matrix Recovery
• Tensor train completion: local recovery guarantees via Riemannian optimization
• On Convergence of the Alternating Projection Method for Matrix Completion and Sparse Recovery Problems
• Global Riemannian Acceleration in Hyperbolic and Spherical Spaces
• Towards the optimal construction of a loss function without spurious local minima for solving quadratic equations
• Spectral Compressed Sensing via Projected Gradient Descent
• Fast and Provable Algorithms for Spectrally Sparse Signal Reconstruction via Low-Rank Hankel Matrix Completion
• Optimal low rank tensor recovery
• Riemannian Conjugate Gradient Descent Method for Third-Order Tensor Completion
• Painless Breakups -- Efficient Demixing of Low Rank Matrices