Guarantees of Riemannian Optimization for Low Rank Matrix Recovery

We establish theoretical recovery guarantees of a family of Riemannian optimization algo-rithms for low rank matrix recovery, which is about recovering an m × n rank r matrix from p < mn number of linear measurements. The algorithms are first interpreted as the iterative hard thresholding algorithms with subspace projections. Then based on this connection, we prove that if the restricted isometry constant R3r of the sensing operator is less than Cκ/ r where Cκ depends on the condition number of the matrix, the Riemannian gradient descent method and a restarted variant of the Riemannian conjugate gradient method are guaranteed to converge to the measured rank r matrix provided they are initialized by one step hard thresh-olding. Empirical evaluation shows that the algorithms are able to recover a low rank matrix from nearly the minimum number of measurements necessary