PaperlayerView exact revision on arXiv

Source-linked AI summary

A Singular Value Thresholding Algorithm for Matrix Completion

Jian-Feng Cai, Emmanuel J. Candes, Zuowei Shen

arXiv:0810.3286v1math.OC

TL;DR

Recovering large low-rank matrices from sparse observations is challenging, so the paper introduces singular value thresholding for nuclear-norm minimization. The algorithm converges under stated step-size conditions and efficiently recovers large matrices, including 30,000×30,000 rank-10 matrices from about 0.4% of sampled entries in 17 minutes.

  • Problem

    Recovering large low-rank matrices from very limited information, such as sampled entries, is a central matrix-completion challenge across applications.

  • Method

    The paper develops singular value thresholding, an iterative nuclear-norm minimization algorithm using soft-thresholding to generate low-rank matrix iterates.

  • Results

    30,000×30,000 rank-10 matrices were recovered from about 0.4% of sampled entries in about 17 minutes on a modest CPU.

  • Takeaways & Limitations

    The algorithm is easy to implement and effective in computational cost and storage requirements for matrix completion and related nuclear-norm problems.

  • Takeaways & Limitations

    The low-rank property of the iterates is empirical because the authors cannot prove it holds in general.

Abstract

from arXiv · show

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 and produces a sequence of matrices (X^k, 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 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. We provide numerical examples in which 1,000 by 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 linearized Bregman iterations for l1 minimization, and we develop a framework in which one can understand these algorithms in terms of well-known Lagrange multiplier algorithms.

1 Introduction

The paper introduces singular value thresholding (SVT), a simple first-order method for nuclear-norm minimization that targets very large, low-rank matrix-recovery problems. Its sparse iterates, low-rank solutions, and adaptability to convex constraints support efficient matrix completion, including noisy settings.

  • Algorithm and scope: SVT approximately solves nuclear-norm minimization and is designed for very large problems whose solutions have low rank.It is presented as a simple first-order algorithm for problems involving linear operators on matrices.
  • Algorithm and scope: Each iteration soft-thresholds the singular values of Y^k, updates using sampled-entry residuals, and requires at most one singular value decomposition.For sufficiently large τ, the iterates converge to a solution that nearly minimizes the matrix-completion objective.
  • Implementation advantages: Sparse Y^k matrices and low-rank X^k matrices reduce computation and storage, since Y^k vanishes outside the observed-entry set and only principal factors need retention.The sparse structure also enables rapid evaluation of the shrink function.
  • Numerical evidence: 30,000×30,000 matrices with close to a billion unknowns were solved in 17 minutes on a standard desktop computer using SVT.The reported system had a 1.86 GHz dual-core CPU, Matlab multithreading, and 3 GB of memory.
  • Extensions: SVT extends to convex constraints fi(X) ≤ 0 with Lipschitz convex functionals, including affine constraints and recovery from sampled entries contaminated with noise.The paper states that the generalized iterations resemble the matrix-completion iteration in the affine case.

2 The Singular Value Thresholding Algorithm

The singular value thresholding (SVT) algorithm alternates singular-value shrinkage with sparse constraint updates to approximate nuclear-norm minimizers. Its low-rank iterates and sparse updates support efficient matrix completion, while an Uzawa formulation provides convergence tools and extensions.

  • Thresholding and convergence: The shrinkage operator soft-thresholds singular values toward zero and is the proximity operator associated with the nuclear norm.For a sufficiently large τ, the iterates converge to a matrix that nearly minimizes the original nuclear-norm problem.
  • Algorithm: SVT iteratively computes X^k = D_τ(Y^{k−1}) and updates Y^k = Y^{k−1} + δ_kP_Ω(M − X^k).Each iteration requires an SVD and elementary matrix operations, making the method easy to implement.
  • Computational properties: The iterates empirically have low rank when the solution has low rank, reducing storage by allowing each matrix to be stored in SVD form.The low-rank behavior is empirical rather than proven in general.
  • Computational properties: Y^k remains sparse outside Ω, so updates cost O(m) when |Ω| = m and can use sparse matrix techniques.Only singular values greater than τ are needed; Lanczos methods can exploit sparse matrix-vector products to accelerate the computation.
  • Connections: SVT extends iterative soft-thresholding by discovering both sparse singular vectors and bases for sparse representations.The method is inspired by linearized Bregman iterations for minimum-ℓ1-norm problems.
  • Lagrange multiplier interpretation: Recasting SVT as Uzawa’s algorithm supplies mathematical tools for convergence and extends the framework to nuclear-norm minimization under convex constraints.The same framework also recasts linear Bregman iterations as a special form of Uzawa’s algorithm.

3 General Formulation

Section 3 generalizes SVT from matrix completion to linear equality and convex inequality constraints, including a noisy Dantzig-selector-style matrix problem. It also establishes that the proximal formulation approaches nuclear-norm minimization as τ grows.

  • 3 General Formulation: SVT approximately minimizes the nuclear norm subject to convex constraints.This section presents the algorithm’s general formulation beyond matrix completion.
  • 3.1 Linear equality constraints: For linear equality constraints A(X) = b, Uzawa’s iteration operates through a linear transformation A and its adjoint A∗.When A is a sampling operator, the iteration reduces to the matrix-completion update because A∗A = PΩ.
  • 3.2 General convex constraints: For convex constraints fi(X) ≤ 0, SVT alternates proximal minimization with projected nonnegative subgradient updates.The projection [·]+ keeps the dual variables in the nonnegative orthant.
  • 3.2 General convex constraints: As τ →∞, the solution of the constrained proximal problem converges to a nuclear-norm minimizer under the same constraints.The theorem at the end of the section establishes this limiting relationship.
  • 3.2 General convex constraints: Linear inequality constraints are handled by representing them with convex functionals and applying the same projected dual-update framework.For affine F(X) = b − A(X), this extension is straightforward.
  • 3.3 Example: The Dantzig-selector extension minimizes nuclear norm subject to componentwise residual bounds |vec(A∗(r))| ≤ vec(E).The tolerance array E is adjusted to fit the noise statistics; for white noise, its entries may use a multiple of σ.
  • 3.3 Example: In matrix completion, the noisy-constraint iteration simplifies because A∗A = PΩ, and low-rank solutions yield low-rank iterates Xk.The resulting method is described as easy to implement.
  • 3.4 When the proximal problem gets close: Under convex, lower semi-continuous constraints, the proximal solutions converge to the unique minimum-Frobenius-norm solution among nuclear-norm minimizers.The proof uses boundedness and shows equality of both nuclear and Frobenius norms, implying convergence to X∞.

4 Convergence Analysis

The section proves that SVT iterates converge to unique solutions under bounded step sizes, first for matrix completion and then for general convex constraints. It also gives a linear-constraint corollary and notes that the general bound may contain an avoidable factor of two.

  • Matrix completion: The sequence {∥PΩ(Yk − Y⋆)∥F} is nonincreasing and therefore converges to a limit.This property follows within the matrix-completion convergence proof.
  • General convex constraints: Under strong duality and 0 < inf δk ≤ sup δk < 2/∥L(F)∥2, general SVT iterates {Xk} converge to the unique solution of (3.4).The result assumes F is Lipschitz with constant L(F).
  • Linear constraints: For linear constraints, if 0 < inf δk ≤ sup δk < 2/∥A∥2, iterates from (3.3) converge to the unique solution of (3.1).The linear-constraint problem is reduced to the general convex-constraint formulation.
  • Linear constraints: Theorem 4.4 yields the stricter linear-constraint bound 0 < inf δk ≤ sup δk < 1/∥A∥2, but an identical argument to Theorem 4.2 removes the extra factor of two.The paper omits the details of this sharper argument.

5 Implementation and Numerical Results

This section presents implementation choices that make the SVT algorithm practically effective for matrix completion and reports numerical simulations demonstrating its performance.

  • Implementation details: The implementation discusses numerical evaluation of the singular value thresholding operator, step-size selection, and stopping-criterion selection.These details are presented as components needed to make SVT practically effective for matrix completion.
  • Numerical results: Numerical simulations are introduced to demonstrate the performance and effectiveness of the SVT algorithm.

5.1 Implementation details

The implementation applies singular-value thresholding to sparse iterates using PROPACK, while selecting practical step sizes and exploiting incremental singular-value computations. It also specifies initialization shortcuts and stopping criteria for efficient matrix completion recovery.

  • Singular-value computation: PROPACK efficiently computes the dominant singular values and vectors needed for thresholding sparse SVT iterates, reducing storage and computational costs.The Matlab package is used despite a reported speedup of about ten over Matlab’s ‘svds’; a Fortran implementation is expected to run about 3 to 4 times faster.
  • Singular-value computation: Because PROPACK requires the number of singular values in advance, each iteration increases the requested rank by an increment ℓ after computing the previous singular vectors.Previously computed Lanczos vectors need not be recomputed; modifying PROPACK to evaluate only a few new singular values would decrease runtimes.
  • Step-size selection: The implementation uses a constant step size δ, with convergence guaranteed for 0 < δ < 2 but experiments using the larger heuristic choice δ = 1.2p^-1.The conservative bound is typically slow; the heuristic choice is justified using a near-isometry argument that is not rigorous because iterates depend on the sampled set.
  • Initialization: The algorithm can skip the initial zero iterates, since X^k = 0 and Y^k = kδPΩ(M) through k0, then begin by computing X^(k0+1).This skipping strategy is a special case of a kicking device, although kicking was rarely triggered in the numerical experiments.
  • Stopping criteria: SVT may stop when the KKT residual falls below a tolerance such as 10^-4 or when the duality-gap upper bound falls below a specified tolerance.The duality-based criterion is impractical for very large problems when iterates are stored in reduced SVD form, because projecting them can require substantial storage.

5.2 Numerical results

The numerical experiments show that SVT efficiently recovers large low-rank matrices, with short runtimes, low reconstruction error, and iterates whose ranks quickly reach the true rank. The method also performs well with noisy data and linear inequality constraints when stopped appropriately.

  • Exact constraints: Fewer than 200 SVT iterations suffice for convergence in all experiments, including recovery of a 30,000×30,000 rank-10 matrix from about 0.4% sampled entries in about 17 minutes.A 1,000×1,000 rank-10 matrix is recovered in less than a minute.
  • Exact constraints: All reported relative reconstruction errors are less than 2 × 10^-4, matching the observed order of the sampled-data error, approximately 10^-4.The stopping criterion is therefore consistent with the empirical reconstruction accuracy.
  • Iterate ranks: The rank of X^k is empirically nondecreasing and quickly reaches the true rank r, after which iterations search among rank-r solutions.This low-rank behavior is identified as crucial for the algorithm’s speed.
  • Noisy data: The relative error between recovered and true matrices is approximately equal to the noise ratio when SVT is stopped early on noisy sampled entries.Early stopping seeks a solution that is both data-consistent and low-rank, whereas the limiting iterate need not remain low-rank.
  • Inequality constraints: About 150 iterations are needed for noiseless inequality-constrained recovery at tolerance ε = 10^-4, compared with about 200 iterations for noisy data.The noisy and noiseless cases have similar iteration times and total running times because iterate ranks remain nondecreasing.
  • Inequality constraints: The relative error is 0.0769 for undersampled noisy recovery with the matrix equivalent of the Dantzig selector, close to the noise ratio of about 0.08.The passage characterizes this recovery as accurate from a statistical point of view.

6 Discussion

The discussion highlights SVT’s practical efficiency when the minimum nuclear-norm solution is also lowest-rank, while identifying open questions about iterate ranks, singular-value shrinkage, and parameter continuation.

  • Practical effectiveness: SVT is easy to implement and effective in computational cost and storage when the minimum nuclear-norm solution is also the lowest-rank solution.The algorithm exploits low-rank iterates under this condition.
  • Open problems: Whether SVT iterates are low-rank in a majority of cases when the minimum nuclear-norm solution is low-rank remains an open question.The paper explicitly leaves open whether this behavior can be proved or disproved generally.
  • Computing Dτ(Y): Alternative randomized low-rank approximation methods may evaluate Dτ(Y) efficiently on sparse inputs, but their speed and accuracy for SVT remain to be established.These methods can use truncated SVDs retaining singular values greater than τ.
  • Computing Dτ(Y): Iterative methods for general matrix functions f(Y) are another potential route for computing Dτ(Y).The paper identifies investigating such existing or future methods as a valuable research direction.
  • Parameter continuation: A continuation strategy can increase τ sequentially because larger τ generally slows convergence, beginning from a value that yields a low-rank solution and rapid convergence.The proposed schedule uses solutions from previous problems as the starting point for subsequent ones.
Loading 0810.3286v1…