A New Retraction for Accelerating the Riemannian Three-Factor Low-Rank Matrix Completion Algorithm
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Low-Rank Matrix CompletionMatrix CompletionSimilar Papers 제목 키워드 기반
Low-Rank Riemannian Optimization on Positive Semidefinite Stochastic Matrices with Applications to Graph Clustering
This paper develops a Riemannian optimization framework for solving optimization problems on the set of symmetric positive semidefinite stochastic matrices. The paper first reformulates the problem by factorizing th…
ClusteringGraph ClusteringRiemannian optimizationRiemannian stochastic quasi-Newton algorithm with variance reduction and its convergence analysis
Stochastic variance reduction algorithms have recently become popular for minimizing the average of a large, but finite number of loss functions. The present paper proposes a Riemannian stochastic quasi-Newton algorithm …
Low-Rank Matrix CompletionMatrix CompletionRiemannian Stochastic Recursive Gradient Algorithm with Retraction and Vector Transport and Its Convergence Analysis
Stochastic variance reduction algorithms have recently become popular for minimizing the average of a large, but finite number of loss functions on a Riemannian manifold. The present paper proposes a Riemannian stoc…
Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport
In recent years, stochastic variance reduction algorithms have attracted considerable attention for minimizing the average of a large but finite number of loss functions. This paper proposes a novel Riemannian extension …
Low-Rank Matrix CompletionMatrix CompletionRiemannian optimizationConvergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms
We analyze inexact Riemannian gradient descent (RGD) where Riemannian gradients and retractions are inexactly (and cheaply) computed. Our focus is on understanding when inexact RGD converges and what is the complexity in…
Riemannian optimizationTensor Decomposition