2012 AcceleratedSingularValueThresho

• (Hu et al., 2012) ⇒ Yao Hu, Debing Zhang, Jun Liu, Jieping Ye, and Xiaofei He. (2012). “Accelerated Singular Value Thresholding for Matrix Completion.” In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2012). ISBN:978-1-4503-1462-6 doi:10.1145/2339530.2339581

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222012%22+Accelerated+Singular+Value+Thresholding+for+Matrix+Completion
• http://dl.acm.org/citation.cfm?id=2339530.2339581&preflayout=flat#citedby

Quotes

Author Keywords

• Adaptive line search scheme; data mining; matrix completion; nesterov's method; singular value thresholding

Abstract

Recovering a large matrix from a small subset of its entries is a challenging problem arising in many real world applications, such as recommender system and image in-painting. These problems can be formulated as a general matrix completion problem. The Singular Value Thresholding (SVT) algorithm is a simple and efficient first-order matrix completion method to recover the missing values when the original data matrix is of low rank. SVT has been applied successfully in many applications. However, SVT is computationally expensive when the size of the data matrix is large, which significantly limits its applicability. In this paper, we propose an Accelerated Singular Value Thresholding (ASVT) algorithm which improves the convergence rate from O (1/N) for SVT to O (1/N²), where N is the number of iterations during optimization. Specifically, the dual problem of the nuclear norm minimization problem is derived and an adaptive line search scheme is introduced to solve this dual problem. Consequently, the optimal solution of the primary problem can be readily obtained from that of the dual problem. We have conducted a series of experiments on a synthetic dataset, a distance matrix dataset and a large movie rating dataset. The experimental results have demonstrated the efficiency and effectiveness of the proposed algorithm.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2012 AcceleratedSingularValueThresho	Jieping Ye Jun Liu Xiaofei He Yao Hu Debing Zhang			Accelerated Singular Value Thresholding for Matrix Completion				10.1145/2339530.2339581		2012