Soft-Impute Iterative Soft-Thresholded SVD for Large Matrix Completion

Soft-Impute Iterative Soft-Thresholded SVD for Large Matrix Completion is a convex spectral-regularization and majorization-minimization (EM-style) algorithm introduced by Mazumder, Hastie, and Tibshirani (2010) for solving the nuclear-norm regularized least-squares matrix completion problem min_{Z in R^{m x n}} f_lambda(Z) = (1/2) ||P_Omega(X) - P_Omega(Z)||_F^2 + lambda ||Z||_* across a warm-started path of regularization parameters lambda_1 > lambda_2 > ... > lambda_K. At each iteration, Algorithm 1 forms the surrogate completed matrix W^{old} = P_Omega(X) + P_Omega^perp(Z^{old}) by filling in missing entries with the current low-rank estimate Z^{old} and updates Z^{new} = S_lambda(W^{old}) = U D_lambda V^T via the singular value soft-thresholding operator D_lambda = diag(max(d_i - lambda, 0)) (Lemma 1). To scale to Netflix-sized matrices without destroying sparsity, Section 3.1 exploits the exact sparse-plus-low-rank decomposition W^{old} = [P_Omega(X) - P_Omega(Z^{old})] + Z^{old}, where the first term has |Omega| << m n nonzeros and the second term has low rank r << min(m, n), allowing Lanczos/PROPACK matrix-vector products in O(|Omega| r + (m + n) r^2) time per SVD step. Lemmas 2-5 and Theorem 1 prove that the Soft-Thresholded SVD operator S_lambda is non-expansive in Frobenius norm (||S_lambda(W_1) - S_lambda(W_2)||_F <= ||W_1 - W_2||_F), generates monotonically decreasing objectives f_lambda(Z^{k+1}) <= f_lambda(Z^k) - (1/2)||P_Omega(Z^{k+1} - Z^k)||_F^2, satisfies ||Z^{k+1} - Z^k||_F -> 0, and converges from any starting point to a global minimizer Z_lambda^* of f_lambda(Z).