Online Matrix Completion and Online Robust PCA
share
This work studies two interrelated problems - online robust PCA (RPCA) and online low-rank matrix completion (MC). In recent work by Candès et al., RPCA has been defined as a problem of separating a low-rank matrix (true data), L:=[ℓ_1, ℓ_2, ...ℓ_t, ... , ℓ_t_] and a sparse matrix (outliers), S:=[x_1, x_2, ... x_t, ..., x_t_] from their sum, M:=L+S. Our work uses this definition of RPCA. An important application where both these problems occur is in video analytics in trying to separate sparse foregrounds (e.g., moving objects) and slowly changing backgrounds. While there has been a large amount of recent work on both developing and analyzing batch RPCA and batch MC algorithms, the online problem is largely open. In this work, we develop a practical modification of our recently proposed algorithm to solve both the online RPCA and online MC problems. The main contribution of this work is that we obtain correctness results for the proposed algorithms under mild assumptions. The assumptions that we need are: (a) a good estimate of the initial subspace is available (easy to obtain using a short sequence of background-only frames in video surveillance); (b) the ℓ_t's obey a `slow subspace change' assumption; (c) the basis vectors for the subspace from which ℓ_t is generated are dense (non-sparse); (d) the support of x_t changes by at least a certain amount at least every so often; and (e) algorithm parameters are appropriately set
READ FULL TEXT