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.
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
- 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