Performance guarantees for undersampled recursive sparse recovery in large but structured noise

We study the problem of recursively reconstructing a time sequence of sparse vectors S_t from measurements of the form M_t = AS_t +BL_t where A and B are known measurement matrices, and L_t lies in a slowly changing low dimensional subspace. We assume that the signal of interest (S_t) is sparse, and has support which is correlated over time. We introduce a solution which we call Recursive Projected Modified Compressed Sensing (ReProMoCS), which exploits the correlated support change of S_t. We show that, under weaker assumptions than previous work, with high probability, ReProMoCS will exactly recover the support set of S_t and the reconstruction error of S_t is upper bounded by a small time-invariant value. A motivating application where the above problem occurs is in functional MRI imaging of the brain to detect regions that are “activated” in response to stimuli. In this case both measurement matrices are the same (i.e. A = B). The active region image constitutes the sparse vector S_t and this region changes slowly over time. The background brain image changes are global but the amount of change is very little and hence it can be well modeled as lying in a slowly changing low dimensional subspace, i.e. this constitutes L_t.