Guarantees of Riemannian optimization for low rank matrix recovery

Ke Wei Jian-Feng Cai Tony F Chan Shing-Yu Leung

Numerical Analysis and Scientific Computing mathscidoc:1912.43181

SIAM Journal on Matrix Analysis and Applications, 37, (3), 1198-1222, 2016.9
We establish theoretical recovery guarantees of a family of Riemannian optimization algorithms for low rank matrix recovery, which is about recovering an mimes n rank mimes n matrix from mimes n number of linear measurements. The algorithms are first interpreted as iterative hard thresholding algorithms with subspace projections. Based on this connection, we show that provided the restricted isometry constant mimes n of the sensing operator is less than mimes n, the Riemannian gradient descent algorithm and a restarted variant of the Riemannian conjugate gradient algorithm are guaranteed to converge linearly to the underlying rank mimes n matrix if they are initialized by one step hard thresholding. Empirical evaluation shows that the algorithms are able to recover a low rank matrix from nearly the minimum number of measurements necessary.
No keywords uploaded!
[ Download ] [ 2019-12-21 11:28:03 uploaded by Shing_Yu_Leung ] [ 234 downloads ] [ 0 comments ]
@inproceedings{ke2016guarantees,
  title={Guarantees of Riemannian optimization for low rank matrix recovery},
  author={Ke Wei, Jian-Feng Cai, Tony F Chan, and Shing-Yu Leung},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20191221112803887608741},
  booktitle={SIAM Journal on Matrix Analysis and Applications},
  volume={37},
  number={3},
  pages={1198-1222},
  year={2016},
}
Ke Wei, Jian-Feng Cai, Tony F Chan, and Shing-Yu Leung. Guarantees of Riemannian optimization for low rank matrix recovery. 2016. Vol. 37. In SIAM Journal on Matrix Analysis and Applications. pp.1198-1222. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20191221112803887608741.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved