A Gradient Descent Algorithm on the Grassman Manifold for Matrix Completion
We consider the problem of reconstructing a low-rank matrix from a small subset of its entries. In this paper, we describe the implementation of an efficient algorithm called OptSpace, based on singular value decomposition followed by local manifold optimization, for solving the low-rank matrix completion problem. It has been shown that if the number of revealed entries is large enough, the output of singular value decomposition gives a good estimate for the original matrix, so that local optimization reconstructs the correct matrix with high probability. We present numerical results which show that this algorithm can reconstruct the low rank matrix exactly from a very small subset of its entries. We further study the robustness of the algorithm with respect to noise, and its performance on actual collaborative filtering datasets.
Code (1)
Tasks
Collaborative FilteringLow-Rank Matrix CompletionMatrix CompletionSimilar Papers 제목 키워드 기반
Scaled Gradients on Grassmann Manifolds for Matrix Completion
This paper describes gradient methods based on a scaled metric on the Grassmann manifold for low-rank matrix completion. The proposed methods significantly improve canonical gradient methods especially on ill-conditioned…
Low-Rank Matrix CompletionMatrix CompletionRiemannian stochastic variance reduced gradient on Grassmann manifold
Stochastic variance reduction algorithms have recently become popular for minimizing the average of a large, but finite, number of loss functions. In this paper, we propose a novel Riemannian extension of the Euclidean s…
Low-Rank Matrix CompletionMatrix CompletionRiemannian optimizationTranslationGrassmann Iterative Linear Discriminant Analysis with Proxy Matrix Optimization
Linear Discriminant Analysis (LDA) is commonly used for dimensionality reduction in pattern recognition and statistics. It is a supervised method that aims to find the most discriminant space of reduced dimension that ca…
Dimensionality ReductionBuilding Deep Networks on Grassmann Manifolds
Learning representations on Grassmann manifolds is popular in quite a few visual recognition tasks. In order to enable deep learning on Grassmann manifolds, this paper proposes a deep network architecture by generalizing…
Adaptive Stochastic Gradient Descent on the Grassmannian for Robust Low-Rank Subspace Recovery and Clustering
In this paper, we present GASG21 (Grassmannian Adaptive Stochastic Gradient for $L_{2,1}$ norm minimization), an adaptive stochastic gradient algorithm to robustly recover the low-rank subspace from a large matrix. In th…
ClusteringStochastic Optimization