Source-linked AI summary
A Gradient Descent Algorithm on the Grassman Manifold for Matrix Completion
Raghunandan H. Keshavan, Sewoong Oh
TL;DR
The paper studies recovery of low-rank matrices from sparse observations, including noisy and approximately low-rank settings. It develops OptSpace procedures based on SVD initialization and manifold optimization, adds rank estimation and an incremental variant, and evaluates them on synthetic and collaborative-filtering data. The experiments report exact reconstruction in sparse-observation settings, while real data expose departures from low-rank and uniform-sampling assumptions.
Problem
The paper asks how to reconstruct low-rank or approximately low-rank matrices from a small set of observed entries, including in noisy settings.
Method
OptSpace combines singular value decomposition with local manifold optimization and adds Rank Estimation and Incremental OptSpace procedures.
Results
The experiments report exact reconstruction from a very small subset of entries and evaluate performance on collaborative-filtering datasets.
Takeaways & Limitations
The procedures broaden applicability by estimating unknown rank and addressing ill-conditioned matrices.
Takeaways & Limitations
Real-data evaluation is limited because the Jester rating matrix is not low-rank or approximately low-rank, and samples are not uniformly random.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper addresses matrix completion for exact and approximate low-rank recovery, emphasizing practical algorithms beyond computationally intractable rank minimization. It develops OptSpace procedures, including rank estimation and Incremental OptSpace, and evaluates them against competing methods and real-world data.
- Motivation: Matrix completion reconstructs a low-rank matrix from a small subset of observed entries, with applications including collaborative filtering, structure from motion, and sensor localization.The low-rank assumption is motivated by a small number of factors contributing to user preferences.
- Problem scope: Exact completion seeks recovery under exact observations, whereas approximate completion addresses noisy observations or matrices that are only approximately low rank.Approximate completion evaluates reconstruction using root mean squared error.
- Contributions: The paper develops efficient OptSpace-based procedures with Rank Estimation and Incremental OptSpace modifications for broader application and better performance.Rank Estimation removes the requirement that the original rank be known, while Incremental OptSpace targets ill-conditioned matrices.
- Evaluation: The study compares reconstruction algorithms empirically and applies the proposed approach to real-world data, including collaborative-filtering datasets.The authors motivate empirical comparison because theoretical guarantees are only up to constants.
2 The model definition
The model observes selected entries of a matrix and seeks a low-rank estimate matching them. Exact rank-constrained recovery is conceptually optimal but computationally intractable, motivating convex relaxations and efficient OptSpace optimization.
- Exact completion: For exact completion, the matrix has rank r ≪ min{m, n}, and observed entries are known exactly.The matrix admits factors U, V, and diagonal Σ with compatible dimensions.
- Observed-data model: A subset E of the m × n entries is observed, and the goal is to estimate the original matrix from the observed values and indices.The estimate is constrained to be low rank.
- Exact recovery: When enough entries are observed and a unique rank-r completion exists, rank minimization recovers the original matrix.The optimization searches for the lowest-rank matrix matching the observations.
- Computational limitation: The rank-minimization formulation is optimal in principle but NP-hard, making it unsuitable for large matrices.Known algorithms require doubly exponential time in n; one cited application involves a 5 · 10^5 × 2 · 10^4 matrix.
- Approximate completion: Approximate completion relaxes exact observation constraints for noisy or only approximately low-rank matrices, while nuclear-norm methods provide convex alternatives.The nuclear norm is the sum of a matrix's singular values.
- Efficient solution: OptSpace is presented as an efficient method closely related to the approximate completion formulation and is compared numerically with competing algorithms.The comparison covers exact and approximate completion problems.
3 Algorithm
OptSpace initializes manifold optimization with a trimmed sparse SVD, estimates the target rank, and then minimizes a non-convex cost over Grassmann manifolds. Its extensions address rank uncertainty and ill-conditioned matrices.
- Manifold formulation: OptSpace minimizes a cost function over factor matrices whose columns represent r-dimensional subspaces.Because the cost is invariant under orthogonal changes of basis, optimization occurs on Grassmann manifolds.
- OptSpace pipeline: The algorithm trims over-represented rows and columns, estimates rank, computes a rank-r SVD projection, and applies gradient descent to return the reconstructed matrix.The SVD supplies the initial factors for local optimization.
- Trimming: Trimming removes entries in rows or columns whose observed degree exceeds twice the average degree.Without trimming, spurious singular values from over-represented rows and columns can dominate the principal components.
- Rank Estimation: Rank Estimation selects the index minimizing a cost based on the singular values of the trimmed observation matrix.The method relies on separation between the first r structural singular values and later spurious ones.
- Rank Estimation: If ε > C(κ)r for a rank-r matrix with bounded condition number κ, Rank Estimation correctly estimates r with high probability.Here ε represents the average degree per row or column for a square matrix.
- Cost function: The squared-difference cost is used throughout, while positive regularization is observed to help when matrix entries are corrupted by noise.The reported experiments use λ = 0.
- Ill-conditioned matrices: Incremental OptSpace searches for singular vectors sequentially and empirically performs substantially better than OptSpace on ill-conditioned matrices.The modification addresses inaccurate initial guesses for singular vectors associated with the smallest singular values.
4 Numerical results with randomly generated matrices
OptSpace shows rapid convergence and strong exact-recovery performance on randomly generated matrices, outperforming competing methods especially on hard problems. Its incremental variant improves robustness to ill-conditioned matrices, while noise experiments characterize degradation across observation and noise settings.
- Convergence: Prediction error decays exponentially with Manifold Optimization iterations for rank-10, n=1000 matrices at ϵ=100 and ϵ=200.Prediction error remains close to fit error, supporting the stopping criterion.
- Exact recovery thresholds: For rank-4 matrices, OptSpace’s reconstruction threshold is upper bounded by |E| = Cn(log n)^2 and lies close to the lower bound |E| = Cn log n.The extra logarithmic factor is attributed to Gaussian factors whose incoherence parameter scales like log n.
- Algorithm comparisons: OptSpace outperforms FPCA, SVT, and ADMiRA on random rank-10 matrices, consistently across various matrix sizes and ranks.The comparison uses reconstruction rates versus |E|/n and includes a theoretical lower bound.
- Algorithm comparisons: On hard problems, OptSpace outperforms other algorithms on most instances, whereas all algorithms achieve similar performance on easy problems.The results average performance over five instances; hard cases use sample sizes no greater than 2.6 times the degrees of freedom.
- Conditioning: Incremental OptSpace improves significantly over OptSpace and achieves results comparable to other algorithms for matrices with varying condition numbers.The modification targets robustness when the condition number κ is high.
- Approximate completion: After one iteration, OptSpace often has lower RMSE than convex relaxation, and after about 10 iterations it becomes indistinguishable from the information-theoretic lower bound.The experiment uses rank-2 matrices and compares performance as observed entries and iterations vary.
- Noise robustness: Under standard Gaussian noise, OptSpace is close to the oracle bound across observed-entry levels, while FPCA has the largest RMSE.ADMiRA and OptSpace become similar when |E|/n ≥ 400 because both estimate the correct rank.
5 Numerical results with real data matrices
The experiments evaluate matrix completion on Jester and MovieLens data, then examine how real rating matrices depart from low-rank and incoherence assumptions. Incremental OptSpace performs competitively on Jester, while movie-factor row-weight disparity challenges incoherence.
- Jester experiments: The Jester dataset contains 4.1 × 10^6 ratings for 100 jokes from 73,421 users, with experiments subsampling 100, 1000, 2000, or 4000 users.Two ratings per user are randomly selected as a test set.
- Jester experiments: Incremental OptSpace achieves lower NMAE than random prediction and, even with 100 users, than nearest-neighbor and Eigentaste results using 18,000 users.Its NMAE tends to decrease as the number of users increases; random prediction has NMAE 0.333, while nearest neighbor and Eigentaste have 0.187.
- MovieLens experiments: MovieLens experiments use 80,000 ratings from 942 users and 1,682 movies to estimate a 20,000-rating test set, comparing Incremental OptSpace, FPCA, and ADMiRA.The comparison reports NMAE for the three methods.
- Structure of real data: The complete Jester submatrix with 14,116 users and 100 jokes is not low-rank or approximately low-rank, and its observations are not uniformly sampled.These properties are identified as difficulties in applying common matrix-completion assumptions to real data.
- Incoherence diagnostics: For incoherence diagnostics, randomly generated factors are more incoherent than movie-rating factors, and movie factors show greater row-weight disparity than user factors.A curve close to a straight line indicates a smaller µ0; curvature indicates disparity among factor row weights.
A Proof of Proposition 3.1
The proof analyzes the factorized reconstruction through a cost function and establishes a sufficient condition under which the target rank uniquely minimizes that cost. The argument relies on a high-probability lemma and bounds for competing ranks.
- Proof setup: The reconstructed matrix is factorized using a diagonal singular-value matrix Σ = diag(Σ1, . . . , Σr).The proof begins from this factorization and a key lemma.
- Proof setup: Lemma A.1 supplies a high-probability bound involving the singular values and Mmax, where Mmax is the largest matrix entry.The lemma is cited as previously proved, and Σq is understood to be zero for q > r.
- Cost comparison: Applying the lemma to the cost function R(i) yields bounds used to compare the target rank with alternative ranks.The proof proceeds by applying the result to R(i) and performing further calculus.
- Cost comparison: For ǫ > C r max, the proof establishes R(r) < R(i) for every i ≠ r, completing the proposition’s argument.The supplied passage states this inequality as the desired condition and conclusion.