A Singular Value Thresholding Algorithm for Matrix Completion¶
Why this mattered¶
This paper mattered because it helped turn matrix completion from a striking convex-geometry result into a practical computational tool. By 2010, nuclear-norm minimization had become the central convex surrogate for low-rank matrix recovery, but the associated optimization problems were often too large for generic solvers. Cai, Candès, and Shen showed that the special structure of the problem could be exploited directly: repeated singular-value soft thresholding, applied within a first-order iteration, made it possible to attack matrix completion instances at scales that interior-point methods could not plausibly handle.
The paradigm shift was algorithmic as much as theoretical. The paper made low-rank recovery feel like the matrix analogue of sparse recovery by connecting singular-value shrinkage to the soft-thresholding ideas already familiar from compressed sensing and ℓ1 minimization. Its empirical observation that the iterates stayed low-rank, together with the use of sparse sampled-entry data, meant that very large incomplete matrices could be processed without ever storing dense billion-entry objects. This changed what researchers and practitioners could reasonably attempt: recommendation systems, collaborative filtering, system identification, image inpainting, and other incomplete-data problems could be approached through scalable convex optimization rather than only through heuristic factorization.
Its influence also lay in the template it established for later work. Subsequent advances in proximal methods, accelerated first-order algorithms, randomized SVD techniques, robust PCA, and large-scale low-rank modeling all built on the same central insight: spectral regularization becomes practical when the expensive linear-algebra step is structured, truncated, or embedded in an iterative scheme. The SVT algorithm was not the final word on matrix completion, but it was a decisive bridge between the theory of exact recovery and the later ecosystem of scalable low-rank optimization methods.
Abstract¶
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, produces a sequence of matrices {Xk, 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 {Xk} 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 × 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 the recent literature on linearized Bregman iterations for ℓ1 minimization, and we develop a framework in which one can understand these algorithms in terms of well-known Lagrange multiplier algorithms.
Related¶
- cite → Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information — Singular value thresholding cites Candes, Romberg, and Tao's uncertainty principles as a compressed-sensing foundation for exact recovery from incomplete measurements.
- cite → Compressed sensing — Singular value thresholding adapts the compressed-sensing idea of sparse recovery from few samples to low-rank matrix completion.
- cite ← Robust principal component analysis? — Robust PCA uses nuclear-norm minimization and singular-value thresholding ideas developed for matrix completion.