Guarantees of Riemannian optimization for low rank matrix completion

Ke Wei, Jian Feng Cai, Tony Fan-Cheong Chan, Shingyu Leung

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


We establish the exact recovery guarantees for a class of Riemannian optimization methods based on the embedded manifold of low rank matrices for matrix completion. Assume m entries of an n×n rank r matrix are sampled independently and uniformly with replacement. We first show 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 m ≥ Cκn1.5r log1.5(n), where Cκ is a numerical constant depending on the condition number of the measured matrix. Then the sampling complexity is further improved to m ≥ Cκnr2 log2(n) 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.
Original languageEnglish (US)
Pages (from-to)233-265
Number of pages33
JournalInverse Problems and Imaging
Issue number2
StatePublished - Feb 14 2020

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: The first author is supported by National Science Foundation of China (NSFC) 11801088 and Shanghai Sailing Program 18YF1401600. The second author is supported by Hong Kong Research Grant Council (HKRGC) General Research Fund (GRF) 16306317.


Dive into the research topics of 'Guarantees of Riemannian optimization for low rank matrix completion'. Together they form a unique fingerprint.

Cite this