A new retraction for accelerating the Riemannian three-factor low-rank matrix completion algorithm

Zhizhong Li, Deli Zhao, Zhouchen Lin, Edward Y. Chang

Introduction

Low-rank matrix completion is a fundamental problem in data science, involving the estimation of missing entries in a large matrix under the assumption that the complete matrix has a low-rank structure. This technique is widely used in recommendation systems, such as predicting movie ratings based on a sparse set of user reviews.

One of the most effective frameworks for solving this problem is Riemannian optimization. In this approach, the set of all rank-$r$ matrices is treated as a smooth, curved manifold. Optimization algorithms then navigate this surface to find the matrix that best fits the observed data. The state-of-the-art Riemannian Three-Factor Matrix Completion (R3MC) algorithm utilizes a specific factorization ($X = URV^T$) to perform this search. However, a significant computational bottleneck exists in the "line search" phase, where the algorithm must determine the optimal step size along a curve on the manifold.

Methodology: The Innovation of Retraction

To move from a direction calculated in a flat tangent space back onto the curved manifold, Riemannian algorithms use a mathematical map called a retraction. Standard retractions often require expensive iterative searches to find the best point along the retracted curve.

Geometric illustration of the retraction mapping from the tangent space to the manifold.

As shown in Figure 1, the retraction $\phi(t)$ maps a tangent vector $\bar{\xi}_{\bar{x}}$ to a curve on the manifold $\bar{\mathcal{M}}_0^+$. This paper introduces a novel retraction designed with a unique "minimizing property." This property ensures a one-to-one correspondence between points on the tangent line and points on the manifold curve such that they share the same cost function value. Consequently, finding the minimum point on a simple straight line in the tangent space automatically yields the exact minimum on the complex manifold curve, eliminating the need for costly iterative line searches.

The authors integrated this retraction into a nonlinear conjugate-gradient framework, creating A-R3MC (Accelerated R3MC). They developed two variants: A-R3MC1 (using Polak-Ribière+) and A-R3MC2 (using Fletcher-Reeves).

Key Results and Performance

The proposed A-R3MC algorithm was evaluated against several state-of-the-art methods, including LRGeomCG, RTRMC, and the original R3MC, using both synthetic and real-world datasets like MovieLens 10M.

Comparison of A-R3MC variants against state-of-the-art algorithms in terms of cost vs. time.

As illustrated in Figure 5, A-R3MC2 (the red line) demonstrates significantly faster convergence compared to other geometric algorithms. In synthetic tests with varying condition numbers (measures of problem difficulty), A-R3MC2 was often the only algorithm to reach high-precision tolerances (e.g., $10^{-10}$) within a reasonable timeframe. The acceleration is particularly pronounced in large-scale scenarios, such as $200,000 \times 200,000$ matrices, where the efficiency of the new retraction allows the algorithm to scale effectively.

On the MovieLens 10M dataset, A-R3MC achieved the lowest cost among geometric competitors and remained highly competitive in terms of Mean Square Error (MSE), proving its practical utility on real-world, sparse data.

Conclusion

By introducing a retraction that preserves the optimality of steps taken in the tangent space, this work significantly enhances the efficiency of Riemannian matrix completion. The A-R3MC algorithm provides a robust and scalable solution, particularly for ill-conditioned and large-scale problems. Future research may explore applying this "minimizing property" to other manifold geometries and cost functions beyond the Frobenius norm.

Summary updated

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 retraction 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.
BibTeX
@inproceedings{li2015new,
  author = {Zhizhong Li and Deli Zhao and Zhouchen Lin and Edward Y. Chang},
  title = {{A new retraction for accelerating the Riemannian three-factor low-rank matrix completion algorithm}},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year = {2015},
  doi = {10.1109/cvpr.2015.7299083},
}
Figure