A lower bound guaranteeing exact matrix completion via singular value thresholding algorithm

作者：Zhang, H^*; Cheng, L Z; Zhu, W

来源：Applied and Computational Harmonic Analysis, 2011, 31(3): 454-459.

DOI：10.1016/j.acha.2011.04.004

• Convex optimization
• Exact matrix completion
• Nuclear norm
• SVT algorithm

In this paper, we give a lower bound guaranteeing exact matrix completion via singular value thresholding (SVT) algorithm. The analysis shows that when the parameter in SVT algorithm is beyond some finite scalar, one can recover some unknown low-rank matrices exactly with high probability by solving a strictly convex optimization problem. Furthermore, we give an explicit expression for such a finite scalar. This result in the paper not only has theoretical interests, but also guides us to choose suitable parameters in the SVT algorithm.

• 出版日期2011-11
• 单位湘潭大学; 中国人民解放军国防科学技术大学