This paper introduces a novel algorithm, the Singular Value Thresholding (SVT) algorithm, to approximate a matrix with the minimum nuclear norm among all matrices satisfying a set of convex constraints. This problem is a convex relaxation of rank minimization and arises in various applications, such as matrix completion, where the goal is to recover a large matrix from a small subset of its entries. The SVT algorithm is designed to efficiently handle problems where the optimal solution has low rank, making it particularly suitable for large-scale matrix completion tasks. The algorithm is iterative and involves a sequence of matrices $\{\mathbf{X}^k, \mathbf{Y}^k\}$, where at each step, a soft-thresholding operation is applied to the singular values of the matrix $\mathbf{Y}^k$. Two key features of the SVT algorithm are its sparsity and low-rank properties. The iterates $\{\mathbf{X}^k\}$ are empirically shown to have low rank, and the iterates $\{\mathbf{Y}^k\}$ are sparse, which allows for efficient storage and computational costs. The paper provides a convergence analysis showing that the sequence of iterates converges to the solution of the optimization problem. Numerical experiments demonstrate that the SVT algorithm can solve problems involving matrices of size $30,000 \times 30,000$ with nearly a billion unknowns in less than 17 minutes on a standard desktop computer. The algorithm is also shown to be effective for large-scale problems, recovering matrices of rank about 10 with nearly a billion unknowns from just 0.4% of their sampled entries. The SVT algorithm is connected to linearized Bregman iterations for $\ell_1$ minimization and is formulated in terms of a well-known Lagrange multiplier algorithm. The paper extends the SVT algorithm to handle general convex constraints and provides a general convergence theorem for the iterations.This paper introduces a novel algorithm, the Singular Value Thresholding (SVT) algorithm, to approximate a matrix with the minimum nuclear norm among all matrices satisfying a set of convex constraints. This problem is a convex relaxation of rank minimization and arises in various applications, such as matrix completion, where the goal is to recover a large matrix from a small subset of its entries. The SVT algorithm is designed to efficiently handle problems where the optimal solution has low rank, making it particularly suitable for large-scale matrix completion tasks. The algorithm is iterative and involves a sequence of matrices $\{\mathbf{X}^k, \mathbf{Y}^k\}$, where at each step, a soft-thresholding operation is applied to the singular values of the matrix $\mathbf{Y}^k$. Two key features of the SVT algorithm are its sparsity and low-rank properties. The iterates $\{\mathbf{X}^k\}$ are empirically shown to have low rank, and the iterates $\{\mathbf{Y}^k\}$ are sparse, which allows for efficient storage and computational costs. The paper provides a convergence analysis showing that the sequence of iterates converges to the solution of the optimization problem. Numerical experiments demonstrate that the SVT algorithm can solve problems involving matrices of size $30,000 \times 30,000$ with nearly a billion unknowns in less than 17 minutes on a standard desktop computer. The algorithm is also shown to be effective for large-scale problems, recovering matrices of rank about 10 with nearly a billion unknowns from just 0.4% of their sampled entries. The SVT algorithm is connected to linearized Bregman iterations for $\ell_1$ minimization and is formulated in terms of a well-known Lagrange multiplier algorithm. The paper extends the SVT algorithm to handle general convex constraints and provides a general convergence theorem for the iterations.