Compressive Online Robust Principal Component Analysis Via n-‘1 Minimization

This work considers online robust principal component analysis (RPCA) in time-varying decomposition problems such as video foreground-background separation. We propose a compressive online RPCA algorithm that decomposes recursively a sequence of data vectors (e.g., frames) into sparse and lowrank components.

Different from conventional batch RPCA, which processes all the data directly, our approach considers a small set of measurements taken per data vector (frame). Moreover, our algorithm can incorporate multiple prior information from previous decomposed vectors via proposing an n-ℓ1 minimization method.

At each time instance, the algorithm recovers the sparse vector by solving the n-ℓ1 minimization problem—which promotes not only the sparsity of the vector but also its correlation with multiple previously-recovered sparse vectors—and, subsequently, updates the low-rank component using incremental singular value decomposition.We also establish theoretical bounds on the number of measurements required to guarantee successful compressive separation under the assumptions of static or slowly-changing low-rank components.

We evaluate the proposed algorithm using numerical experiments and online video foreground-background separation experiments. The experimental results show that the proposed method outperforms the existing methods.