A Singular Value Thresholding Algorithm for Matrix Completion

Abstract

This paper introduces a novel algorithm to approximate the matrix with minimum nuclear norm among all matrices obeying a set of convex constraints. This problem may be understood as the convex relaxation of a rank minimization problem, and arises in many important applications as in the task of recovering a large matrix from a small subset of its entries (the famous Netflix problem). Off-the-shelf algorithms such as interior point methods are not directly amenable to large problems of this kind with over a million unknown entries. This paper develops a simple first-order and easy-to-implement algorithm that is extremely efficient at addressing problems in which the optimal solution has low rank. The algorithm is iterative and produces a sequence of matrices (X^k, Y^k) and at each step, mainly performs a soft-thresholding operation on the singular values of the matrix Y^k. There are two remarkable features making this attractive for low-rank matrix completion problems. The first is that the soft-thresholding operation is applied to a sparse matrix; the second is that the rank of the iterates X^k is empirically nondecreasing. Both these facts allow the algorithm to make use of very minimal storage space and keep the computational cost of each iteration low. We provide numerical examples in which 1,000 by 1,000 matrices are recovered in less than a minute on a modest desktop computer. We also demonstrate that our approach is amenable to very large scale problems by recovering matrices of rank about 10 with nearly a billion unknowns from just about 0.4% of their sampled entries. Our methods are connected with linearized Bregman iterations for l1 minimization, and we develop a framework in which one can understand these algorithms in terms of well-known Lagrange multiplier algorithms.

References in corpus (2)

• Sparsity and Incoherence in Compressive Sampling
• Low-rank matrix factorization with attributes

Cited by in corpus (39)

• The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices
• Linearized Alternating Direction Method with Adaptive Penalty for Low-Rank Representation
• A Gradient Descent Algorithm on the Grassman Manifold for Matrix Completion
• Tensor-based formulation and nuclear norm regularization for multi-energy computed tomography
• Matrix Completion from Noisy Entries
• Hessian Schatten-Norm Regularization for Linear Inverse Problems
• Estimation of low-rank tensors via convex optimization
• Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements
• Dynamic Anomalography: Tracking Network Anomalies via Sparsity and Low Rank
• Low-Rank Structure Learning via Log-Sum Heuristic Recovery
• PETRELS: Parallel Subspace Estimation and Tracking by Recursive Least Squares from Partial Observations
• Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices
• Enhanced Low-Rank Matrix Approximation
• Matrix Completion from a Few Entries
• Large-Scale Convex Minimization with a Low-Rank Constraint
• Matrix Completion in Colocated MIMO Radar: Recoverability, Bounds & Theoretical Guarantees
• Matrix Completion With Noise
• Super-Linear Convergence of Dual Augmented-Lagrangian Algorithm for Sparsity Regularized Estimation
• Color Image and Multispectral Image Denoising Using Block Diagonal Representation
• Experimental compressive phase space tomography
• Collaborative Spectrum Sensing from Sparse Observations Using Matrix Completion for Cognitive Radio Networks
• Guaranteed Minimum Rank Approximation from Linear Observations by Nuclear Norm Minimization with an Ellipsoidal Constraint
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Blind Compressed Sensing Over a Structured Union of Subspaces
• ADMiRA: Atomic Decomposition for Minimum Rank Approximation
• Quantum State Tomography with Locally Purified Density Operators and Local Measurements
• Developing Univariate Neurodegeneration Biomarkers with Low-Rank and Sparse Subspace Decomposition
• SET: an algorithm for consistent matrix completion
• Fault Tolerant Matrix Pencil Method for Direction of Arrival Estimation
• Tensor Laplacian Regularized Low-Rank Representation for Non-uniformly Distributed Data Subspace Clustering
• IMP: A Message-Passing Algorithmfor Matrix Completion
• Efficient and Guaranteed Rank Minimization by Atomic Decomposition
• Continuous-variable quantum compressed sensing
• A Geometric Approach to Low-Rank Matrix Completion
• Information Theoretic Bounds for Low-Rank Matrix Completion
• Matrix recovery using Split Bregman
• Sparse Online Low-Rank Projection and Outlier Rejection (SOLO) for 3-D Rigid-Body Motion Registration
• Accurate low-rank matrix recovery from a small number of linear measurements
• Decomposition of Longitudinal Deformations via Beltrami Descriptors