Analysis of Singular Value Thresholding Algorithm for Matrix Completion

Yunwen Lei*, Ding Xuan Zhou

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

7 Citations (Scopus)


This paper provides analysis for convergence of the singular value thresholding algorithm for solving matrix completion and affine rank minimization problems arising from compressive sensing, signal processing, machine learning, and related topics. A necessary and sufficient condition for the convergence of the algorithm with respect to the Bregman distance is given in terms of the step size sequence {δk}k∈N as ∑k=1∞δk=∞. Concrete convergence rates in terms of Bregman distances and Frobenius norms of matrices are presented. Our novel analysis is carried out by giving an identity for the Bregman distance as the excess gradient descent objective function values and an error decomposition after viewing the algorithm as a mirror descent algorithm with a non-differentiable mirror map.

Original languageEnglish
Pages (from-to)2957-2972
Number of pages16
JournalJournal of Fourier Analysis and Applications
Issue number6
Publication statusPublished - Dec 2019

Scopus Subject Areas

  • Analysis
  • Mathematics(all)
  • Applied Mathematics

User-Defined Keywords

  • Bregman distance
  • Matrix completion
  • Mirror descent
  • Singular value thresholding


Dive into the research topics of 'Analysis of Singular Value Thresholding Algorithm for Matrix Completion'. Together they form a unique fingerprint.

Cite this