# American Institute of Mathematical Sciences

April  2020, 14(2): 233-265. doi: 10.3934/ipi.2020011

## Guarantees of riemannian optimization for low rank matrix completion

 1 School of Data Science, Fudan University, Shanghai, China 2 Department of Mathematics, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong SAR, China 3 Office of the President, King Abdullah University of Science and Technology, Thuwal 23955-6900, Kingdom of Saudi Arabia

* Corresponding author: Jian-Feng Cai

Received  January 2019 Revised  October 2019 Published  February 2020

Fund Project: 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.

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\times 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
 \begin{align*} m\geq C_\kappa n^{1.5}r\log^{1.5}(n), \end{align*}
where
 $C_\kappa$
is a numerical constant depending on the condition number of the measured matrix. Then the sampling complexity is further improved to
 \begin{align*} m\geq C_\kappa 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.
Citation: Ke Wei, Jian-Feng Cai, Tony F. Chan, Shingyu Leung. Guarantees of riemannian optimization for low rank matrix completion. Inverse Problems and Imaging, 2020, 14 (2) : 233-265. doi: 10.3934/ipi.2020011
##### References:

show all references

##### References:
Geometric comparison between NIHT (a) and RGrad (b). One more projection is introduced in RGrad
Empirical phase transition curves (a) RGrad, (b) RCG, (c) RCG restarted and (d) GD when $n = 800$. Horizontal axis $p = m/n^2$ and vertical axis $q = (2n-r)r/m$. White denotes successful recovery in all ten random tests, and black denotes failure in all tests
Relative residual (mean and standard deviation over ten random tests) as function of number of iterations for $n = 8000$, $r = 100$, $1/ q = 2$ (a) and $1/ q = 3$ (b). The values after each algorithm are the average computational time (seconds) for convergence
Performance of (a) RGrad, (b) RCG and (c) RCG restarted under different SNR
Comparison of RGrad/RCG and GD on sampling complexity (SC), required assumptions (RA), per-iteration computational cost (PICC), and local convergence rate (LCR). Remarks: 1) (Ⅰ) represents RGD/RCG with the one step hard thresholding initialization and (Ⅱ) represents RGD/RCG with the resampled Riemannian gradient descent initialization; 2) $v_g$ and $v_{cg}$ are both absolute numerical constants which are less than one
 Algorithm SC RA PICC LCR RGrad, RCG (I) $O(\kappa n^{3/2}r\log^{3/2}(n))$ $\textbf{A0}$ $O(|\Omega|r+|\Omega|+nr^2+nr+r^3)$ $v_{g},~v_{cg}$ RGrad, RCG (II) $O(\kappa^6nr^2\log^2(n))$ $\textbf{A0}$ $O(|\Omega|r+|\Omega|+nr^2+nr+r^3)$ $v_{g},~v_{cg}$ GD [54] $O(\kappa^2nr^2\log(n))$ $\textbf{A0}$ $O(|\Omega|r+|\Omega|+nr^2+nr)$ $(1-\frac{C}{\mu^2\kappa^2r^2})^{1/2}$
 Algorithm SC RA PICC LCR RGrad, RCG (I) $O(\kappa n^{3/2}r\log^{3/2}(n))$ $\textbf{A0}$ $O(|\Omega|r+|\Omega|+nr^2+nr+r^3)$ $v_{g},~v_{cg}$ RGrad, RCG (II) $O(\kappa^6nr^2\log^2(n))$ $\textbf{A0}$ $O(|\Omega|r+|\Omega|+nr^2+nr+r^3)$ $v_{g},~v_{cg}$ GD [54] $O(\kappa^2nr^2\log(n))$ $\textbf{A0}$ $O(|\Omega|r+|\Omega|+nr^2+nr)$ $(1-\frac{C}{\mu^2\kappa^2r^2})^{1/2}$
 [1] Wataru Nakamura, Yasushi Narushima, Hiroshi Yabe. Nonlinear conjugate gradient methods with sufficient descent properties for unconstrained optimization. Journal of Industrial and Management Optimization, 2013, 9 (3) : 595-619. doi: 10.3934/jimo.2013.9.595 [2] Shishun Li, Zhengda Huang. Guaranteed descent conjugate gradient methods with modified secant condition. Journal of Industrial and Management Optimization, 2008, 4 (4) : 739-755. doi: 10.3934/jimo.2008.4.739 [3] El-Sayed M.E. Mostafa. A nonlinear conjugate gradient method for a special class of matrix optimization problems. Journal of Industrial and Management Optimization, 2014, 10 (3) : 883-903. doi: 10.3934/jimo.2014.10.883 [4] Gaohang Yu, Lutai Guan, Guoyin Li. Global convergence of modified Polak-Ribière-Polyak conjugate gradient methods with sufficient descent property. Journal of Industrial and Management Optimization, 2008, 4 (3) : 565-579. doi: 10.3934/jimo.2008.4.565 [5] Yangyang Xu, Ruru Hao, Wotao Yin, Zhixun Su. Parallel matrix factorization for low-rank tensor completion. Inverse Problems and Imaging, 2015, 9 (2) : 601-624. doi: 10.3934/ipi.2015.9.601 [6] Feng Bao, Thomas Maier. Stochastic gradient descent algorithm for stochastic optimization in solving analytic continuation problems. Foundations of Data Science, 2020, 2 (1) : 1-17. doi: 10.3934/fods.2020001 [7] Saman Babaie–Kafaki, Reza Ghanbari. A class of descent four–term extension of the Dai–Liao conjugate gradient method based on the scaled memoryless BFGS update. Journal of Industrial and Management Optimization, 2017, 13 (2) : 649-658. doi: 10.3934/jimo.2016038 [8] Xiaming Chen. Kernel-based online gradient descent using distributed approach. Mathematical Foundations of Computing, 2019, 2 (1) : 1-9. doi: 10.3934/mfc.2019001 [9] Ting Hu. Kernel-based maximum correntropy criterion with gradient descent method. Communications on Pure and Applied Analysis, 2020, 19 (8) : 4159-4177. doi: 10.3934/cpaa.2020186 [10] Yacine Chitour, Zhenyu Liao, Romain Couillet. A geometric approach of gradient descent algorithms in linear neural networks. Mathematical Control and Related Fields, 2022  doi: 10.3934/mcrf.2022021 [11] Zhong Wan, Chaoming Hu, Zhanlu Yang. A spectral PRP conjugate gradient methods for nonconvex optimization problem based on modified line search. Discrete and Continuous Dynamical Systems - B, 2011, 16 (4) : 1157-1169. doi: 10.3934/dcdsb.2011.16.1157 [12] Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006 [13] Guanghui Zhou, Qin Ni, Meilan Zeng. A scaled conjugate gradient method with moving asymptotes for unconstrained optimization problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 595-608. doi: 10.3934/jimo.2016034 [14] Henry Adams, Lara Kassab, Deanna Needell. An adaptation for iterative structured matrix completion. Foundations of Data Science, 2021, 3 (4) : 769-791. doi: 10.3934/fods.2021028 [15] Yongge Tian. A survey on rank and inertia optimization problems of the matrix-valued function $A + BXB^{*}$. Numerical Algebra, Control and Optimization, 2015, 5 (3) : 289-326. doi: 10.3934/naco.2015.5.289 [16] Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115 [17] King Hann Lim, Hong Hui Tan, Hendra G. Harno. Approximate greatest descent in neural network optimization. Numerical Algebra, Control and Optimization, 2018, 8 (3) : 327-336. doi: 10.3934/naco.2018021 [18] Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems and Imaging, 2021, 15 (1) : 159-183. doi: 10.3934/ipi.2020076 [19] Yun Cai, Song Li. Convergence and stability of iteratively reweighted least squares for low-rank matrix recovery. Inverse Problems and Imaging, 2017, 11 (4) : 643-661. doi: 10.3934/ipi.2017030 [20] Huiyuan Guo, Quan Yu, Xinzhen Zhang, Lulu Cheng. Low rank matrix minimization with a truncated difference of nuclear norm and Frobenius norm regularization. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022045

2021 Impact Factor: 1.483