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.
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.
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