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\|_F^2$ 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.
Problem solved:Low-rank and sparse matrix decomposition in noisy case.
1. Visual analysis, such as background modeling and light/shadow removal
2. Matrix Completion
1. Consider the noisy model $X=L+S+G$, can handle approximated decomposition even when the exact and unique decomposition does not exist;
2. Decomposition robustness to the noise part $G$;
3. Directly constrains the rank of $L$ and the cardinality of $S$, preferable in real applications. The space and time costs can be significantly saved in this case;
4. Uses bilateral random projection (BRP) based low-rank matrix approximation to replace SVD, significantly reduces the time cost.
Talks:1. Prof. Dacheng Tao, GoDec: Randomized Low-rank & Sparse Matrix Decomposition in Noisy Case, Invited speech on The 3rd Pao-Lu Hsu conference, Aug 4, 2011 (Link)
2. Tianyi Zhou, GoDec: Randomized Low-rank & Sparse Matrix Decomposition in Noisy Case, Oral presentation on ICML 2011, Jul 29, 2011 (VEDIO)3. Tianyi Zhou, GoDec: Randomized Low-rank & Sparse Matrix Decomposition in Noisy Case, Statistics Seminar, Department of Statistics, Stanford University, Jul 28, 2011 (Poster)
Experiments:Videos for background modeling experiments in ICML 2011 paper can be found here. Please refer to the paper for other experiments.
Code:Now only MatLab code is available here. New version will be updated soon.