A Gradient Descent Algorithm on the Grassman Manifold for Matrix Completion

Abstract

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.

arXiv comment26 pages, 15 figures

References in corpus (15)

• Quantum state tomography via compressed sensing
• A Simpler Approach to Matrix Completion
• Scalable Tensor Factorizations for Incomplete Data
• Matrix Completion from Noisy Entries
• A Singular Value Thresholding Algorithm for Matrix Completion
• Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices
• Matrix Completion from a Few Entries
• Guaranteed Rank Minimization via Singular Value Projection
• Matrix Completion With Noise
• Exact Matrix Completion via Convex Optimization
• Fixed Point and Bregman Iterative Methods for Matrix Rank Minimization
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• ADMiRA: Atomic Decomposition for Minimum Rank Approximation
• SET: an algorithm for consistent matrix completion
• Uniqueness of Low-Rank Matrix Completion by Rigidity Theory

Cited by in corpus (34)

• Macroscopic Traffic Flow Modeling with Physics Regularized Gaussian Process: A New Insight into Machine Learning Applications
• Understanding Urban Dynamics via Context-aware Tensor Factorization with Neighboring Regularization
• CSDI: Conditional Score-based Diffusion Models for Probabilistic Time Series Imputation
• Truncated tensor Schatten p-norm based approach for spatiotemporal traffic data imputation with complicated missing patterns
• Leveraging Side Observations in Stochastic Bandits
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• Correlating sparse sensing for large-scale traffic speed estimation: A Laplacian-enhanced low-rank tensor kriging approach
• Robust Low-rank Matrix Completion via an Alternating Manifold Proximal Gradient Continuation Method
• Greed is Super: A Fast Algorithm for Super-Resolution
• Influence-guided Data Augmentation for Neural Tensor Completion
• Robust Factorization of Real-world Tensor Streams with Patterns, Missing Values, and Outliers
• Spatiotemporal Implicit Neural Representation as a Generalized Traffic Data Learner
• MADMM: a generic algorithm for non-smooth optimization on manifolds
• "Slow-Scanning" in Ground-Based Mid-Infrared Observation
• Low-rank optimization with trace norm penalty
• Estimation of Missing Data in Intelligent Transportation System
• Riemannian Perspective on Matrix Factorization
• Robust Tensor Recovery with Fiber Outliers for Traffic Events
• Estimating Traffic Speeds using Probe Data: A Deep Neural Network Approach
• Incremental Bayesian tensor learning for structural monitoring data imputation and response forecasting
• Matrix Factorization via Deep Learning
• Ad Hoc Microphone Array Calibration: Euclidean Distance Matrix Completion Algorithm and Theoretical Guarantees
• Non-recurrent Traffic Congestion Detection with a Coupled Scalable Bayesian Robust Tensor Factorization Model
• A probabilistic model for missing traffic volume reconstruction based on data fusion
• Exploring Algorithmic Limits of Matrix Rank Minimization under Affine Constraints
• Rank Aggregation via Nuclear Norm Minimization
• Data-Driven Intersection Management Solutions for Mixed Traffic of Human-Driven and Connected and Automated Vehicles
• Regularized Kaczmarz Algorithms for Tensor Recovery
• Ocean Reverberation Suppression via Matrix Completion with Sensor Failure
• HMLasso: Lasso with High Missing Rate
• Simultaneous Measurement Imputation and Outcome Prediction for Achilles Tendon Rupture Rehabilitation
• Efficient Optimization Algorithms for Robust Principal Component Analysis and Its Variants
• Minimum $n$-Rank Approximation via Iterative Hard Thresholding
• Multi-Tensor Network Representation for High-Order Tensor Completion