Unmixing Incoherent Structures of Big Data by Randomized or Greedy Decomposition
This work addresses computational bottlenecks in matrix decomposition for big data applications, offering incremental improvements in efficiency for data analysis tasks.
The paper tackles the problem of decomposing big data matrices into semantic components with incoherent structures, addressing computational expense and noise, and proposes adaptive models and efficient algorithms like GoDec with acceleration strategies such as BRP and GreB, achieving significant improvements in time and sample complexities.
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......