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

author: Demba Ba, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, MIT
published: Jan. 14, 2013,   recorded: December 2012,   views: 2715


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


We consider the problem of recovering a sequence of vectors, (xk)k=0K, for which the increments xk−xk−1 are Sk-sparse (with Sk typically smaller than S1), based on linear measurements (yk=Akxk+ek)k=1K, where Ak and ek denote the measurement matrix and noise, respectively. Assuming each Ak obeys the restricted isometry property (RIP) of a certain order - depending only on Sk - 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 (xk)k=1K \emph{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.

See Also:

Download slides icon Download slides: machine_ba_sparse_01.pdf (476.4 KB)

Download article icon Download article: machine_ba_sparse_01.pdf (143.7 KB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: