GoDec: Randomized Low-rank & Sparse Matrix Decomposition in Noisy Case

Publisher:
Omnipress
Publication Type:
Conference Proceeding
Citation:
Proceedings of the 28th International Conference on Machine Learning, 2011, pp. 33 - 40
Issue Date:
2011-01
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2011001843OK.pdf1.07 MB
Adobe PDF
Low-rank and sparse structures have been profoundly studied in matrix completion and compressed sensing. In this paper, we develop 'Go Decomposition' (GoDec) to efficiently and robustly estimate the low-rank part L and the sparse part S of a matrix X = L + S + G with noise G. GoDec alternatively assigns the low-rank approximation of X - S to L and the sparse approximation of X - L to S. The algorithm can be significantly accelerated by bilateral random projections (BRP). We also propose GoDec for matrix completion as an important variant. We prove that the objective value ||X - L - S||2F converges to a local minimum, while L and S linearly converge to local optimums. Theoretically, we analyze the influence of L, S and G to the asymptotic/convergence speeds in order to discover the robustness of GoDec. Empirical studies suggest the efficiency, robustness and effectiveness of GoDec comparing with representative matrix decomposition and completion tools, e.g., Robust PCA and OptSpace.
Please use this identifier to cite or link to this item: