Welcome to the GoDec algorithm, a new member of the Matrix Factorization Jungle

Welcome to a new member of the Matrix Factorization Jungle. Tianyi Zhou just blogged and released an implementation of the GoDec algorithm for the Randomized Low-rank and Sparse Matrix Decomposition in the Noisy Case. The Go Decomposition site and attendant code is here. It looks very good, but I particularly dig the third step of the algorithm:

3. Develop randomized low-rank approximation method "bilateral random projection (BRP)" to further accelerate the update in the algorithm;

But the most important question is: In what star studded casino robbing movie are we going see the nerd explain in a one liner that the guards will only see the low rank version of the scene ? That's what I want to know.

The video of the ICML is on Tianyi's blog entry. The attendant ICML paper is : GoDec: Randomized Low-rank and Sparse Matrix Decomposition in Noisy Case by Tianyi Zhou and Dacheng Tao. The abstract reads:

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

Thanks Tianyi !

GoDec has been included in the Matrix Factorization Jungle.

Liked this entry ? subscribe to the Nuit Blanche feed, there's more where that came from