A Singular Value Thresholding Algorithm for Matrix Completion
By Jian-Feng Cai, E.J. Candes, Zuowei Shen. 2008
6,096 citations recorded by the source corpus.
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, produces a sequence of matrices $\{\boldsymbol{X}^k,\boldsymbol{Y}^k\}$, and at each step mainly performs a soft-thresholding operation on the singular values of the matrix $\boldsymbol{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 $\{\boldsymbol{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. On the theoretical side, we provide a convergence analysis showing that the sequence of iterates converges. On the practical side, we provide numerical examples in which $1,000\times1,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 the recent literature on linearized Bregman iterations for $\ell_1$ minimization, and we develop a framework in which one can understand these algorithms in terms of well-known Lagrange multiplier algorithms.
Subfields: Computational Mechanics, Electrical and Electronic Engineering, Numerical Analysis, Statistical Learning Theory
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Mechanics
- Francis R. Bach
- Wotao Yin
- E.J. Candes
- Lei Zhang
- Julien Mairal
- Peter Richtárik
- Martin J. Wainwright
- Prateek Jain
In Electrical and Electronic Engineering
In Numerical Analysis
- Francis R. Bach
- Wotao Yin
- Jieping Ye
- Simon Lacoste-Julien
- Peter Richtárik
- Julien Mairal
- Stephen P. Boyd
- Paul Tseng
In Statistical Learning Theory
- Francis R. Bach
- Robert Tibshirani
- Masashi Sugiyama
- Prateek Jain
- Jieping Ye
- Yuanzhi Li
- Yi Ma
- Andrea Montanari
Citations in the corpus
- Frank-Wolfe Splitting via Augmented Lagrangian Method (2018, background): “On some cases, such as constraints on the trace norm (Cai et al., 2010) or the latent group lasso (Obozinski et al.”
- LoRA: Low-Rank Adaptation of Large Language Models (2021, background): “A lot of machine learning problems have certain intrinsic low-rank structure [7, 13, 23, 24].”
- Data Poisoning Attacks on Factorization-Based Collaborative Filtering (2016, methodology): “Existing approaches in the literature include nearest-neighbor methods, where a user’s (item’s) preference is determined by other users (items) with similar profiles [1], and factorization-based methods where the incomplete preference matrix is assumed to be approximately low-rank [2, 3].”
- Principal Components and Regularized Estimation of Factor Models (2017, background): “9 Theorem 2.1 of Cai et al. (2008) shows that In other words, the optimal approximation of the low rank component of Z under rank constraint is U r D γr V ′ r where D γr is a matrix of thresholded singular values.”
- Spectral Regularization Algorithms for Learning Large Incomplete Matrices (2010, methodology): “In this paper we propose an algorithm Soft-Impute for the nuclear norm regularized least-squares problem (3) that scales to large problems with m,n ≈ 105–106 with around 104–105 or more observed entries.”
- Optimization with Sparsity-Inducing Penalties (2011, background): “, the unique minimizer of (1)2‖M −N‖(2)F + μ‖M‖∗ for a fixed matrix M , may be obtained by computing a singular value decomposition of N and then replacing the singular values by their soft-thresholded versions [29].”
- Guaranteed Matrix Completion via Non-Convex Factorization (2014, background): “Index Terms —Matrix completion, matrix factorization, nonconvex optimization, alternating minimization, SGD, perturbation analysis.”
- The Convex Geometry of Linear Inverse Problems (2010, background): “Proximity operators have already been harnessed for fast algorithms involving the 1 norm [20, 21, 35, 40, 73] and the nuclear norm [12, 51, 71] where these maps can be quickly computed in closed form.”
- Efficient Tensor Completion for Color Image and Video Recovery: Low-Rank Tensor Train (2016, background): “As a result, the 1 optimization problem (23) provides an effective means for the matrix rank optimization problem (21).”
- Split Bregman Methods and Frame Based Image Restoration (2009, methodology): “To see this, we consider a more general approach which has been proposed in [7, 15], by introducing a relative weight γ before the second term as follows”
- Linearized Alternating Direction Method with Adaptive Penalty for Low-Rank Representation (2011, methodology): “, the nuclear norm‖ · ‖∗ [2], Frobenius norm‖ · ‖, l2,1 norm‖ · ‖2,1 [14], andl1 norm‖ · ‖1), andA andB are linear mappings.”
- Sparse Bayesian Methods for Low-Rank Matrix Estimation (2011, methodology): “OPTSPACE and ADMIRA generally underestimate the rank, whereas FPCA and SVT consistently overestimate it.”
- Deep Partial Multi-View Learning (2020, background): “The missing views are basically blockwise and thus low-rank based completion [12], [13] is not applicable, as has been widely recognized in [5], [14].”
- Parallel matrix factorization for low-rank tensor completion (2013, neutral): “LMaFit has been demonstrated superior over many other matrix completion solvers such as APGL [24], SVT [5], and FPCA [17]; (5) appears to be the first convex model for tensor completion, and FaLRTC is the first efficient and also reliable 3 solver of (5); the work [18] about SquareDeal appears the first…”
- Low-rank Solutions of Linear Matrix Equations via Procrustes Flow (2015, methodology): “Let M T 0 = C T 0 Σ T 0 D T T 0 be the Singular Value Decomposition (SVD) of M T 0 . f f Updates of the form (2.1) have a long history in compressed sensing/matrix sensing literature (see e.g. [TG07, GK09, NT09, NV09, BD09, MJD09, CCS10]).”