A New Retraction for Accelerating the Riemannian Three-Factor Low-Rank Matrix Completion Algorithm

Zhizhong Li, Deli Zhao, Zhouchen Lin, Edward Y. Chang; The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015, pp. 4530-4538

Abstract


The Riemannian three-factor matrix completion (R3MC) algorithm is one of the state-of-the-art geometric optimization methods for the low-rank matrix completion problem. It is a nonlinear conjugate-gradient method optimizing on a quotient Riemannian manifold. In the line search step, R3MC approximates the minimum point on the searching curve by minimizing on the line tangent to the curve. However, finding the exact minimum point by iteration is too expensive. We address this issue by proposing a new retrac with a minimizing property. This special property provides the exact minimization for the line search by establishing correspondences between points on the searching curve and points on the tangent line. Accelerated R3MC, which is R3MC equipped with this new retraction, outperforms the original algorithm and other geometric algorithms for matrix completion in our empirical study.

Related Material


[pdf]
[bibtex]
@InProceedings{Li_2015_CVPR,
author = {Li, Zhizhong and Zhao, Deli and Lin, Zhouchen and Chang, Edward Y.},
title = {A New Retraction for Accelerating the Riemannian Three-Factor Low-Rank Matrix Completion Algorithm},
booktitle = {The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)},
month = {June},
year = {2015}
}