Singular Value Thresholding Algorithm for Matrix Completion
Algorithms AIMech:SingularValueThresholdingAlgorithmForMatrixCompletion DRAFT
Aliases: Singular Value Thresholding, SVT Algorithm for Matrix Completion, Uzawa Singular Value Soft-Thresholding, Cai-Candes-Shen SVT Algorithm
Singular Value Thresholding Algorithm for Matrix Completion (SVT) is a first-order primal-dual Uzawa/linearized-Bregman optimization method introduced by Cai, Candes, and Shen (2010) for large-scale low-rank matrix completion from a sampled entry subset Omega subset {1,...,n_1} x {1,...,n_2}. Rather than solving the unregularized nuclear-norm program directly via interior-point semidefinite programming, SVT solves the Moreau-Yosida regularized problem min_X tau ||X||_* + (1/2) ||X||_F^2 subject to P_Omega(X) = P_Omega(M) by alternating a singular value shrinkage step X^k = D_tau(Y^{k-1}) and a sparse dual ascent step Y^k = Y^{k-1} + delta_k P_Omega(M - X^k), where D_tau(Y) = U diag(max(sigma_i - tau, 0)) V^* is the closed-form proximal operator of tau ||.||_* (Theorem 2.1). Because Y^k is supported exclusively on Omega and only singular values exceeding tau are needed, SVT maintains both sparse dual matrices and low-rank primal iterates throughout execution.
Identity Notes & Concept Scope
Distinct from exact nuclear-norm theoretical duality certificates (AIMech:ExactMatrixCompletionViaConvexOptimizationNuclearNorm), Grassmannian manifold alternating minimization OptSpace (AIMech:OptSpaceDegreeTrimmingSpectralProjectionAndGrassmannManifoldMatrixCompletion), and Hard-Thresholded AltMinComplete (AIMech:AltMinSenseAndAltMinCompleteAlternatingMinimizationForLowRankMatrixSensingAndCompletion). Specifically captures the Cai-Candes-Shen (2010) SVT algorithm (Equations 1.4-1.5 and Algorithm 1), the nuclear-norm proximal shrinkage theorem D_tau(Y) = argmin_X {(1/2)||X - Y||_F^2 + tau ||X||_*} (Theorem 2.1), the equivalence between the regularized objective min tau ||X||_* + (1/2)||X||_F^2 and the nuclear-norm solution as tau -> infinity (Theorem 3.1), and global convergence under 0 < inf delta_k <= sup delta_k < 2 (Theorem 4.1).
Claims & Grounded Evidence
3 Claims
Mechanism
#claim-01
For any matrix Y = U Sigma V^* and threshold tau >= 0, Theorem 2.1 proves that the singular value soft-thresholding operator D_tau(Y) = U D_tau(Sigma) V^* with D_tau(Sigma) = diag(max(sigma_i - tau, 0)) is the unique global minimizer of the proximal nuclear-norm functional (1/2)||X - Y||_F^2 + tau ||X||_* because Y - D_tau(Y) = tau(U_0 V_0^* + W) with U_0^* W = 0, W V_0 = 0, and ||W||_2 <= 1 lies in the subdifferential tau * partial ||D_tau(Y)||_*.
Scope
#claim-02
Theorem 3.1 proves that the unique solution Z_tau of the strongly convex surrogate min_X {tau ||X||_* + (1/2)||X||_F^2 : P_Omega(X) = P_Omega(M)} converges as tau -> infinity to the minimum-Frobenius-norm solution X_hat of the pure nuclear-norm problem min_X {||X||_* : P_Omega(X) = P_Omega(M)} (and coincides with X_hat for finite tau > tau_0 when Omega is finite), while Theorem 4.1 establishes that the Uzawa iterates X^k = D_tau(Y^{k-1}), Y^k = Y^{k-1} + delta_k P_Omega(M - X^k) converge globally to Z_tau whenever the step sizes satisfy 0 < inf_k delta_k <= sup_k delta_k < 2.
Limitation
#claim-03
Selecting a large threshold tau is required so that the regularized optimum Z_tau closely approximates the pure nuclear-norm minimizer and keeps intermediate iterates low rank, but large tau slows down asymptotic convergence; conversely, step sizes delta_k violating the theoretical stability condition delta_k < 2 (outside the empirical undersampled scaling delta = 1.2 * n_1 n_2 / |Omega|) can cause the dual updates to diverge.
⚠️ Curated Limitations & Negative Results
- Faces a trade-off in choosing the regularization threshold tau: large tau guarantees low-rank intermediate iterates and small bias relative to pure nuclear-norm minimization but increases the number of first-order iterations required for high-precision convergence.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:DimensionalityReduction
Dimensionality Reduction
|
related_match | SVT recovers low-rank matrix structure via iterative singular value soft-thresholding. |
AIO:PrincipalComponentAnalysis
Principal Component Analysis
|
related_match | Each SVT iteration computes truncated singular vectors exceeding threshold tau. |
Evidence Sources & Primary Literature
3 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
r317-primary-pdf
|
Jian-Feng Cai, Emmanuel J. Candes, Zuowei Shen
|
primary paper
full_text
|
ID: https://doi.org/10.1137/080738970
sha256:5f7f969ec4ca…
|
r317-arxiv-abs
|
Jian-Feng Cai, Emmanuel J. Candes, Zuowei Shen
|
primary paper
abstract_only
|
ID: https://arxiv.org/abs/0810.3286v1
sha256:8261ef4b72cb…
|
r317-metadata-cr
|
Jian-Feng Cai, Emmanuel J. Candes, Zuowei Shen
|
primary paper
abstract_only
|
ID: https://doi.org/10.1137/080738970
sha256:8923fa446e33…
|
Ontology & Grounding Topology
Open in interactive network graph →Curation Provenance
Curator: Antigravity
Method: ai_assisted
Model: Gemini
Created: 2026-10-19T06:26:00Z
Updated: 2026-10-19T06:26:00Z
Source File:
data/curated/SingularValueThresholdingAlgorithmForMatrixCompletion.yaml
· Schema:
curated_concept.yaml
Explore across X-Mech
Related computational & biological Mechs:
Embedding Map
Network Graph
ProteinTraitsMech (ESM-2 pLM)
DUFMech (Domain pLM)
TraitMech
CultureMech
All 14 X-Mech Repositories