Timezone: »
Spotlight
Exact and Stable Recovery of Sequences of Signals with Sparse Increments via Differential ℓ1Minimization
Demba Ba · Behtash Babadi · Patrick Purdon · Emery Brown
Thu Dec 06 12:08 PM  12:12 PM (PST) @ Harveys Convention Center Floor, CC
We consider the problem of recovering a sequence of vectors, $(x_k)_{k=0}^K$, for which the increments $x_kx_{k1}$ 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 orderdepending only on $S_k$we show that in the absence of noise a convex program, which minimizes the weighted sum of the $\ell_1$norm of successive differences subject to the linear measurement constraints, recovers the sequence $(x_k)_{k=1}^K$ \emph{exactly}. This is an interesting result because this convex program is equivalent to a standard compressive sensing problem with a highlystructured 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 quadraticallyconstrained 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 timevarying sparsity.
Author Information
Demba Ba (MIT/Harvard)
Behtash Babadi (University of Maryland)
Patrick Purdon (MIT/Harvard)
Emery Brown (MIT/Harvard)
Related Events (a corresponding poster, oral, or spotlight)

2012 Poster: Exact and Stable Recovery of Sequences of Signals with Sparse Increments via Differential ℓ1Minimization »
Thu Dec 6th 10:00 PM  08:00 AM Room Harrah’s Special Events Center 2nd Floor