Recursive robust PCA or recursive sparse recovery in large but structured noise

摘要

We study the recursive robust principal components' analysis (PCA) problem. Here, “robust” refers to robustness to both independent and correlated sparse outliers. If the outlier is the signal-of-interest, this problem can be interpreted as one of recursively recovering a time sequence of sparse vectors, St, in the presence of large but structured noise, Lt: the noise needs to lie in a “slowly changing” low dimensional subspace. We study a novel solution called Recursive Projected CS (ReProCS). Under mild assumptions, we show that, with high probability (w.h.p.), at all times, ReProCS can exactly recover the support set of St; and the reconstruction errors of both St and Lt are upper bounded by a time-invariant and small value.