Recursive sparse recovery in large but structured noise — Part 2

We study the problem of recursively recovering a time sequence of sparse vectors, S_t, from measurements M_t := S_t + L_t that are corrupted by structured noise L_t which is dense and can have large magnitude. The structure that we require is that L_t should lie in a low dimensional subspace that is either fixed or changes “slowly enough” and the eigenvalues of its covariance matrix are “clustered”. We do not assume any model on the sequence of sparse vectors. Their support sets and their nonzero element values may be either independent or correlated over time (usually in many applications they are correlated). The only thing required is that there be some support change every so often. We introduce a novel solution approach called Recursive Projected Compressive Sensing with cluster-PCA (ReProCS-cPCA) that addresses some of the limitations of earlier work. Under mild assumptions, we show that, with high probability, ReProCS-cPCA can exactly recover the support set of S_t at all times; and the reconstruction errors of both S_t and L_t are upper bounded by a time-invariant and small value.