Dynamic sparse state estimation using ℓ1-ℓ1 minimization: Adaptive-rate measurement bounds, algorithms and applications

João F. C. Mota, Nikos Deligiannis, Aswin C. Sankaranarayanan, Volkan Cevher, Miguel R. D. Rodrigues

Abstract

This paper introduces a recursive algorithm for tracking sparse, time-varying signals using a technique called $\ell_1$-$\ell_1$ minimization. By leveraging a dynamical model to predict the next state, the algorithm adaptively calculates the minimum number of measurements required for accurate reconstruction, significantly outperforming standard compressed sensing methods in data efficiency.

Introduction

In fields like video surveillance, medical imaging (MRI), and radar, tracking signals that change over time is a critical task. These signals are frequently "sparse," meaning most of their components are zero (e.g., the moving foreground in a static security video).

The challenge is twofold: first, taking full measurements is often expensive or slow, necessitating "Compressed Sensing" (CS) to reconstruct signals from minimal linear measurements. Second, standard CS often treats each time step as an independent problem, failing to utilize temporal logic. While the Kalman filter is a classic tool for tracking, it struggles with the non-Gaussian noise and strict sparsity constraints typical of these applications. This research bridges the gap by determining how many fewer measurements are required when a prediction of the signal is available from previous frames.

Methodology

The authors propose a recursive framework based on $\ell_1$-$\ell_1$ minimization.

The Core Optimization

Instead of just looking for a sparse signal as in standard $\ell_1$ minimization, the proposed method solves: $$\min_x \|x\|_1 + \|x - w\|_1$$ subject to the measurements taken. Here, $w$ represents "side information"—a prediction of the current state based on the previous estimate and a dynamical model. This objective function encourages the solution to be both sparse and close to the prediction.

Adaptive Measurement Rate

A standout feature of this work is the adaptive measurement scheme. Most CS systems use a fixed number of measurements ($m$). This paper utilizes theoretical bounds to estimate the "quality" of the prediction $w$ on-the-fly. The algorithm calculates parameters ($h$ and $\xi$) that measure how well the prediction matches the actual signal's support and sign, then computes a lower bound on the number of measurements needed for the next time step. A "safeguard" parameter ($\delta$) and an exponential moving average ensure system stability even if a single reconstruction is slightly inaccurate.

Experimental Setup

The researchers evaluated their approach using the "Hall" video sequence, a standard benchmark in computer vision.

A frame from the Hall video sequence used for compressive background subtraction experiments.

For the experiments, the first 18 frames (containing no foreground) were removed, and the video was downsampled to $128 \times 128$ resolution. The algorithm was applied to compressive background subtraction, where the goal is to reconstruct only the moving people (the sparse foreground) while the static background is already known.

Key Results and Insights

Adaptive measurement rate $m_k$ and estimate $\phi_k$ compared to theoretical oracle bounds for the Hall video sequence.
  • Data Reduction: The algorithm required significantly fewer measurements than standard $\ell_1$ minimization. In video experiments, it maintained high-quality tracking with a measurement rate far below the standard "CS bound."
  • The "Oracle" Alignment: As shown in the results, the proposed adaptive scheme (the blue line) tracks the theoretical "Oracle" bound (the minimum measurements needed if the signal were known perfectly) very closely. This suggests the algorithm is highly efficient at extracting information.
  • High Precision: In noiseless scenarios, the relative reconstruction error was remarkably low (between $10^{-7}$ and $10^{-8}$), limited only by the precision of the numerical solver (ADMM).
  • Stability: By using motion-compensated extrapolation to predict movement between frames, the algorithm successfully tracked moving subjects with minimal data.

Limitations and Future Work

While effective, the algorithm's efficiency relies heavily on the accuracy of the dynamical model ($f_k$). If the signal changes unpredictably, the measurement savings diminish. Furthermore, the theoretical bounds assume i.i.d. Gaussian measurement matrices, which may not perfectly match real-world hardware like single-pixel cameras. Finally, because the probability of perfect reconstruction across long sequences can decrease over time, future work may explore "reset" mechanisms or more sophisticated safeguards for indefinite tracking.

Summary updated

Abstract

We propose a recursive algorithm for estimating time-varying signals from a few linear measurements. The signals are assumed sparse, with unknown support, and are described by a dynamical model. In each iteration, the algorithm solves an ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> minimization problem and estimates the number of measurements that it has to take at the next iteration. These estimates are computed based on recent theoretical results for ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> minimization. We also provide sufficient conditions for perfect signal reconstruction at each time instant as a function of an algorithm parameter. The algorithm exhibits high performance in compressive tracking on a real video sequence, as shown in our experimental results.
BibTeX
@inproceedings{mota2015dynamic,
  author = {João F. C. Mota and Nikos Deligiannis and Aswin C. Sankaranarayanan and Volkan Cevher and Miguel R. D. Rodrigues},
  title = {{Dynamic sparse state estimation using ℓ1-ℓ1 minimization: Adaptive-rate measurement bounds, algorithms and applications}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2015},
  doi = {10.1109/icassp.2015.7178588},
}

Loading related content...

Figure