Abstract
This paper introduces the Online Reweighted Least Squares (ORLS) algorithm, a novel method for reconstructing sparse signals from linear measurements as they arrive sequentially. By integrating recursive updates with a Conjugate Gradient (CG) solver and a "warm-start" strategy, ORLS achieves reconstruction quality—measured by PSNR and SSIM—that is nearly identical to traditional batch processing. The approach offers significant advantages in computational efficiency and memory storage, making it particularly suitable for progressive decoding in Short-Wave Infrared (SWIR) imaging and other real-time compressive sensing applications.
Introduction
Compressive Sensing (CS) provides a framework for recovering high-resolution signals from a limited number of noisy linear measurements. Traditionally, this recovery is performed in "batch mode," requiring the collection and storage of all data before optimization begins. However, real-world scenarios such as remote sensing or medical imaging often demand a more flexible, "online" approach.
The authors address the need for a strategy that updates signal estimates with every new measurement. Such an online method allows for progressive reconstruction, enabling users to monitor image quality in real-time and adopt a "stop-when-satisfied" rule, thereby saving time and energy. Furthermore, online recovery minimizes the memory footprint by eliminating the need to store massive batches of sensing vectors and measurements.
Methodology
The ORLS algorithm is built upon the Iteratively Reweighted Least Squares (IRLS) framework. IRLS approximates $\ell_1$-minimization (sparsity promotion) by solving a sequence of weighted $\ell_2$ (least squares) problems. The weights are updated based on the current signal estimate, where smaller coefficients receive larger penalties to drive them toward zero.
The Online Implementation
- Recursive Updates: Instead of re-solving the entire system at each time step $t$, ORLS updates its internal state matrices recursively using only the newest measurement $y_t$ and its corresponding sensing vector $a_t$.
- Conjugate Gradient (CG) Solver with Warm-Starting: To avoid the $O(n^3)$ cost of direct matrix inversion, the authors employ a CG solver. The "secret sauce" of the algorithm's efficiency is warm-starting: the signal estimate from the previous time step ($x_t$) serves as the starting point for the next ($x_{t+1}$). Since the signal changes minimally between individual measurements, the solver converges in very few iterations.
- Regularization: A parameter $\lambda$ is included to balance data fidelity against the sparsity constraint, ensuring robust recovery even in the presence of noise.
Experimental Setup
The algorithm's performance was evaluated using several datasets and configurations:
- Natural Images: Used to establish a proof-of-concept and compare ORLS directly against standard batch IRLS.
- Simulated FPA-CS Setup: A simulation of a Focal Plane Array-based Compressive Sensing system, mimicking a SWIR camera where a Digital Micro-mirror Device (DMD) applies random binary patterns to the scene.
- DCT Dictionary: Images were processed in $8 \times 8$ patches, utilizing the Discrete Cosine Transform (DCT) as the sparsifying dictionary.
Results and Discussion
The experimental results demonstrate that ORLS is highly competitive with established batch methods.
Performance Parity and Superiority
In head-to-head tests on natural images, ORLS achieved PSNR and SSIM values nearly identical to batch IRLS. When applied to the SWIR imaging simulation, ORLS outperformed common Total Variation (TV) regularization-based batch recovery by approximately 1 dB in PSNR. At 100% measurements, the reconstruction reached ~38 dB PSNR, making it virtually indistinguishable from the ground truth.
Computational Efficiency
The "warm-start" strategy proved highly effective. The number of CG iterations required for convergence actually decreased as more measurements arrived, confirming that the previous estimate becomes an increasingly accurate starting point. This efficiency, combined with the fact that measurements and sensing vectors do not need to be stored long-term, highlights the algorithm's suitability for hardware with limited resources.
Conclusion
The Online Reweighted Least Squares (ORLS) algorithm provides a robust and efficient solution for sequential sparse recovery. By matching the quality of batch methods while offering progressive decoding and reduced memory requirements, it addresses key bottlenecks in real-time compressive imaging.
While the current model assumes a static scene and uses non-adaptive sensing, future research will explore extending ORLS to dynamic video scenes and integrating adaptive measurement strategies to further optimize information gain per measurement.
Summary updated