1Unmixing Incoherent Structures of Big Data by Randomized or Greedy Decomposition

Learning big data by matrix decomposition always suffers from expensive computation, mixing of complicated structures and noise. In this paper, we study more adaptive models and efficient algorithms that decompose a data matrix as the sum of semantic components with incoherent structures. We firstly introduce “GO decomposition (GoDec)”, an alternating projection method estimating the low-rank part L and the sparse part S from data matrix X = L + S + G corrupted by noise G. Two acceleration strategies are proposed to obtain scalable unmixing algorithm on big data: 1) Bilateral random projection (BRP) is developed to speed up the update of L in GoDec by a closed-form built from left and right random projections of X−S in lower dimensions; 2) Greedy bilateral (GreB) paradigm updates the left and right factors of L in a mutually adaptive and greedy incremental manner, and achieve significant improvement in both time and sample complexities. Then we proposes three nontrivial variants of GoDec that generalizes GoDec to more general data type and whose fast algorithms can be derived from the two strategies: 1) for motion segmentation, we further decompose the sparse S (moving objects) as the sum of multiple row-sparse matrices, each of which is a low-rank matrix after specific geometric transformation sequence and defines a motion shared by multiple objects; 2) for multi-label learning, we further decompose the low-rank L into subcomponents with separable subspaces, each corresponds to the mapping a single label in feature space. Then the prediction can be effectively conducted by group lasso on the subspace ensemble; 3) for estimating scoring functions of each user in recommendation system, we further decompose the low-rank L as WZT, where the rows of W is the linear scoring functions and the rows of Z are the items represented by available features. Empirical studies show the efficiency, robustness and effectiveness of the proposed methods in real applications. Index Terms Low-rank and sparse matrix decomposition, bilateral random projection, greedy bilateral paradigm, multi-label learning, background modeling, motion segmentation, recommendation systems I