Exact and Stable Recovery of Sequences of Signals with Sparse Increments via Differential _1-Minimization

Abstract

We consider the problem of recovering a sequence of vectors, (x_k)_k=0^K, for which the increments x_k-x_k-1 are S_k-sparse (with S_k typically smaller than S_1), based on linear measurements (y_k = A_k x_k + e_k)_k=1^K, where A_k and e_k denote the measurement matrix and noise, respectively. Assuming each A_k obeys the restricted isometry property (RIP) of a certain order---depending only on S_k---we show that in the absence of noise a convex program, which minimizes the weighted sum of the _1-norm of successive differences subject to the linear measurement constraints, recovers the sequence (x_k)_k=1^K exactly. This is an interesting result because this convex program is equivalent to a standard compressive sensing problem with a highly-structured aggregate measurement matrix which does not satisfy the RIP requirements in the standard sense, and yet we can achieve exact recovery. In the presence of bounded noise, we propose a quadratically-constrained convex program for recovery and derive bounds on the reconstruction error of the sequence. We supplement our theoretical analysis with simulations and an application to real video data. These further support the validity of the proposed approach for acquisition and recovery of signals with time-varying sparsity.

Tasks

Reproductions