Online Reweighted Least Squares Algorithm for Sparse Recovery and Application to Short-Wave Infrared Imaging

Subhadip Mukherjee, Deepak R., Huaijin G. Chen, Ashok Veeraraghavan, Chandra Sekhar SeelamantulaarXiv 2017 · arXiv

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

  1. 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$.
  2. 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.
  3. 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.
Sample natural scene used for evaluating reconstruction performance.

Results and Discussion

The experimental results demonstrate that ORLS is highly competitive with established batch methods.

Comparison of Batch IRLS and ORLS performance. (a) and (b) show visual parity, (c) shows minimal difference, and (d) illustrates the progressive improvement in PSNR/SSIM as measurements increase.

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

Abstract

We address the problem of sparse recovery in an online setting, where random linear measurements of a sparse signal are revealed sequentially and the objective is to recover the underlying signal. We propose a reweighted least squares (RLS) algorithm to solve the problem of online sparse reconstruction, wherein a system of linear equations is solved using conjugate gradient with the arrival of every new measurement. The proposed online algorithm is useful in a setting where one seeks to design a progressive decoding strategy to reconstruct a sparse signal from linear measurements so that one does not have to wait until all measurements are acquired. Moreover, the proposed algorithm is also useful in applications where it is infeasible to process all the measurements using a batch algorithm, owing to computational and storage constraints. It is not needed a priori to collect a fixed number of measurements; rather one can keep collecting measurements until the quality of reconstruction is satisfactory and stop taking further measurements once the reconstruction is sufficiently accurate. We provide a proof-of-concept by comparing the performance of our algorithm with the RLS-based batch reconstruction strategy, known as iteratively reweighted least squares (IRLS), on natural images. Experiments on a recently proposed focal plane array-based imaging setup show up to 1 dB improvement in output peak signal-to-noise ratio as compared with the total variation-based reconstruction.
BibTeX
@misc{mukherjee2017online,
  author = {Subhadip Mukherjee and Deepak R. and Huaijin G. Chen and Ashok Veeraraghavan and Chandra Sekhar Seelamantula},
  title = {{Online Reweighted Least Squares Algorithm for Sparse Recovery and Application to Short-Wave Infrared Imaging}},
  year = {2017},
  eprint = {1706.09585},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1706.09585},
}
Figure