Matrix Completion from Noisy Entries

Abstract

Given a matrix M of low-rank, we consider the problem of reconstructing it from noisy observations of a small, random subset of its entries. The problem arises in a variety of applications, from collaborative filtering (the `Netflix problem') to structure-from-motion and positioning. We study a low complexity algorithm introduced by Keshavan et al.(2009), based on a combination of spectral techniques and manifold optimization, that we call here OptSpace. We prove performance guarantees that are order-optimal in a number of circumstances.

22 pages, 3 figures

References in corpus (7)

• A Singular Value Thresholding Algorithm for Matrix Completion
• Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices
• Collaborative Filtering in a Non-Uniform World: Learning with the Weighted Trace Norm
• 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

Cited by in corpus (32)

• Recommender Systems
• Euclidean Distance Matrices: Essential Theory, Algorithms and Applications
• Matrix estimation by Universal Singular Value Thresholding
• An overview of low-rank matrix recovery from incomplete observations
• A Gradient Descent Algorithm on the Grassman Manifold for Matrix Completion
• Signal Recovery on Graphs: Variation Minimization
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• PETRELS: Parallel Subspace Estimation and Tracking by Recursive Least Squares from Partial Observations
• Machine Learning in Thermodynamics: Prediction of Activity Coefficients by Matrix Completion
• Forward - Backward Greedy Algorithms for Atomic Norm Regularization
• Poisson Matrix Recovery and Completion
• Subspace Evolution and Transfer (SET) for Low-Rank Matrix Completion
• The Phase Transition of Matrix Recovery from Gaussian Measurements Matches the Minimax MSE of Matrix Denoising
• Fast, Robust and Non-convex Subspace Recovery
• Noisy Matrix Completion under Sparse Factor Models
• Localization from Incomplete Euclidean Distance Matrix: Performance Analysis for the SVD-MDS Approach
• Optimal large-scale quantum state tomography with Pauli measurements
• Low Rank Matrix Completion with Exponential Family Noise
• Matrix Completion with Deterministic Sampling: Theories and Methods
• Asymptotic equivalence of quantum state tomography and noisy matrix completion
• Calibration Using Matrix Completion with Application to Ultrasound Tomography
• A Note on Alternating Minimization Algorithm for the Matrix Completion Problem
• Orthogonal Inductive Matrix Completion
• Near-optimal matrix recovery from random linear measurements
• Multitask Learning Strengthens Adversarial Robustness
• Optimal tuning-free convex relaxation for noisy matrix completion
• Matrix Completion and Performance Guarantees for Single Individual Haplotyping
• Privacy-Preserving Multiple Tensor Factorization for Synthesizing Large-Scale Location Traces with Cluster-Specific Features
• Tight Risk Bound for High Dimensional Time Series Completion
• Dynamic Matrix Recovery
• Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling
• Robust Max Entrywise Error Bounds for Tensor Estimation from Sparse Observations via Similarity Based Collaborative Filtering