TY - JOUR
T1 - Analysis of Singular Value Thresholding Algorithm for Matrix Completion
AU - Lei, Yunwen
AU - Zhou, Ding-Xuan
PY - 2019/12
Y1 - 2019/12
N2 - 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.
AB - 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.
KW - Bregman distance
KW - Matrix completion
KW - Mirror descent
KW - Singular value thresholding
UR - http://www.scopus.com/inward/record.url?scp=85069666259&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85069666259&origin=recordpage
U2 - 10.1007/s00041-019-09688-8
DO - 10.1007/s00041-019-09688-8
M3 - 21_Publication in refereed journal
VL - 25
SP - 2957
EP - 2972
JO - Journal of Fourier Analysis and Applications
JF - Journal of Fourier Analysis and Applications
SN - 1069-5869
IS - 6
ER -