Low-complexity compressive sensing with downsampling

Dongeun Lee, Jaesik Choi, Heonshik Shin

Introduction

In the burgeoning field of the Internet of Things (IoT) and wearable biosensors, power efficiency is the primary constraint. Traditional data compression techniques, such as transform coding, often impose a computational burden that exceeds the capabilities of resource-constrained sensors. Compressive Sensing (CS) emerged as a promising alternative by shifting the computational load from the sensor (encoder) to a more powerful base station (decoder). However, standard CS implementations utilizing dense random matrices still require significant multiplication and addition operations at the sensor level. This paper proposes a novel framework that combines sparse random matrices with a simple downsampling scheme to achieve a "double-win" in both computational complexity and bit-rate efficiency.

Methodology

The proposed framework integrates three core components to minimize the encoder's workload:

  1. Sparse Random Matrices: Instead of dense Gaussian matrices, the authors employ matrices containing mostly zeros and a minimal number ($d$) of ones. This substitution converts complex matrix multiplications into a small number of simple additions.
  2. Encoder-Side Downsampling: The encoder performs downsampling by a factor of $L$, selecting every $L$-th sample from the input signal. This directly reduces the size of the input vector, thereby slashing the total number of operations required for the CS process.
  3. Decoder-Side Linear Interpolation: At the base station, the downsampled signal is first recovered using standard linear programming. Subsequently, the signal is upsampled and smoothed using linear interpolation to reconstruct the original data.

A notable deviation from standard signal processing is the omission of low-pass filtering prior to downsampling. The researchers observed that for typical sensor signals, the distortion introduced by practical filters was more detrimental than the aliasing caused by skipping the filtering step.

Experimental Setup and Datasets

The framework was evaluated using real-world environmental data from the Sensorscope project. Two distinct signal types were tested to assess robustness:

  • Static Signals: Air temperature data, characterized by relatively smooth transitions.
  • Dynamic Signals: Solar radiation data, which exhibits higher volatility and frequent fluctuations.

Key Insights

The "Smoothing" Effect

A counterintuitive finding was that downsampling at low factors ($L=2$ or $4$) actually improved signal quality. While standard CS recovery can introduce artificial noise, recovering fewer points and applying linear interpolation resulted in a smoother signal that more closely matched the ground truth.

Complexity Scaling

The proposed scheme significantly improves the scaling of computational complexity. While general CS scales at $O(MN)$ and sparse CS at $O(dN)$, the integrated approach scales at $O(dN/L)$. This represents an exponential reduction in sensor-side work as the downsampling factor increases.

Results

The experimental results demonstrate substantial gains in efficiency:

  • Computational Complexity: The scheme achieved a 99.95% reduction in complexity compared to standard dense Gaussian CS frameworks.
  • Bit-rate Savings: Significant data compression was observed, with bit-rate savings of 46.29% for air temperature data and 32.62% for solar radiation data, without exceeding the error thresholds of baseline systems.
  • Optimal Performance: The lowest error rates were generally achieved at downsampling factors of $L=2$ or $L=4$. Beyond $L=4$, the information loss from downsampling began to outweigh the benefits of interpolation-based smoothing.

Conclusion and Future Work

This research presents a highly efficient CS framework suitable for the most resource-constrained IoT devices. By combining sparse matrices with temporal downsampling, the authors achieved dramatic reductions in power and bandwidth requirements. Future work will explore more sophisticated interpolation methods for dynamic signals and the extension of this temporal downsampling approach into the spatial domain for distributed sensor networks.

Summary updated

BibTeX
@article{lee2014low,
  author = {Dongeun Lee and Jaesik Choi and Heonshik Shin},
  title = {{Low-complexity compressive sensing with downsampling}},
  journal = {IEICE Electron. Express},
  year = {2014},
  doi = {10.1587/elex.11.20130947},
}
Figure