Performance guarantees for ReProCS - Correlated low-rank matrix entries case

摘要

Online or recursive robust PCA can be posed as a problem of recovering a sparse vector, St, and a dense vector, Lt, which lies in a slowly changing low-dimensional subspace, from Mt ≔ St+Lt on-the-fly as new data comes in. For initialization, it is assumed that an accurate knowledge of the subspace in which L0 lies is available. In recent works, Qiu et al proposed and analyzed a novel solution to this problem called recursive projected compressed sensing or ReProCS. In this work, we relax one limiting assumption of Qiu et al's result. Their work required that the Lt's be mutually independent over time. However this is not a practical assumption, e.g., in the video application, Lt is the background image sequence and one would expect it to be correlated over time. In this work we relax this and allow the Lt's to follow an autoregressive model. We are able to show that under mild assumptions and under a denseness assumption on the unestimated part of the changed subspace, with high probability (w.h.p.), ReProCS can exactly recover the support set of St at all times; the reconstruction errors of both St and Lt are upper bounded by a time invariant and small value; and the subspace recovery error decays to a small value within a finite delay of a subspace change time.