Serial Quantization for Sparse Time Sequences

Alejandro Cohen, Nir Shlezinger, Salman Salamatian, Yonina C. Eldar, Muriel MédardIEEE TSP 2021 · DOI

TL;DR

This paper introduces SQuaTS (Serial Quantization for Sparse Time Sequences), a novel method for efficiently quantizing and reconstructing sparse time-varying signals using standard, low-cost analog-to-digital converters (ADCs). SQuaTS achieves significantly improved accuracy compared to existing methods by leveraging group testing principles, enabling more efficient data acquisition in resource-constrained scenarios.

What Problem Does This Paper Address?

Digital hardware requires analog signals to be sampled and quantized. While vector quantization offers the highest accuracy, it's computationally complex and requires storing multiple samples in analog form before processing. Standard ADCs operate serially and independently on each sample, which is hardware-friendly but can lead to significant accuracy loss, especially when dealing with sparse signals (signals with many zero or near-zero values). Existing methods that combine compressed sensing (CS) with quantization often require the entire analog signal to be available before compression and quantization, making them unsuitable for real-time sequential acquisition. This paper addresses the need for a method that can quantize sparse time sequences sequentially, accurately, and with low hardware complexity, avoiding the need to store analog samples.

Methods

The core of SQuaTS is inspired by group testing theory, a field focused on identifying defective items in a large set using a minimal number of tests. SQuaTS adapts this by:

  • Scalar Quantization: Each incoming analog sample is first quantized by a standard scalar ADC.
  • Binary Codeword Update: Instead of storing the quantized value directly, its index is used to select a pre-defined binary codeword from a specific "bin." This selected codeword is then combined with a running binary register using a logical OR operation. This process is repeated for each incoming sample.
  • Sequential Encoding: The key innovation is that the system updates a single, fixed-size binary register (b bits) sequentially. This avoids the need to store multiple analog samples.
  • Group Testing Inspired Codebook: A codebook is generated based on principles from group testing, where codewords are organized into bins. This structure facilitates the decoding process.
  • Maximum Likelihood (ML) Decoding: After all samples are processed, the final binary register is decoded using an ML approach to reconstruct the original sparse signal.
  • Reduced Complexity Decoder (CoMa): To address the computational burden of ML decoding, a sub-optimal but much faster decoder based on the "Column Matching" (CoMa) method is proposed.
  • Distributed Quantization: The SQuaTS framework is extended to handle scenarios where multiple sparse signals are acquired simultaneously at different locations and need to be jointly recovered.

Datasets

Not discussed in the paper. The paper focuses on synthetic data generated for simulations.

Key Insights and Ideas

  • Leveraging Sparsity for Quantization: The paper demonstrates that by treating quantization as a group testing problem, the inherent sparsity of the signal can be exploited to achieve much higher accuracy for a given bit rate compared to direct scalar quantization or CS-based methods.
  • Sequential Acquisition without Analog Storage: SQuaTS's ability to update a single binary register sequentially is a significant advantage for hardware implementation, especially in scenarios where analog memory is limited or costly.
  • Trade-off Between Accuracy and Complexity: The introduction of the CoMa decoder highlights a practical trade-off: SQuaTS can achieve high accuracy with ML decoding, but a faster, less complex decoder (CoMa) can be used at the cost of slightly reduced accuracy.
  • Robustness to Noise: The paper shows that SQuaTS can be adapted to handle noisy digital representations by slightly increasing codeword length, demonstrating its practical applicability.
  • Distributed Systems Compatibility: The framework naturally extends to distributed sensor networks, allowing for joint recovery of multiple sparse signals.

Key Results

  • Superior Accuracy: SQuaTS consistently outperforms direct scalar quantization and CS-based methods (like QIHT and FISTA) in terms of Mean Squared Error (MSE) for a given quantization rate, especially for highly sparse signals. For example, in one scenario, SQuaTS achieved a 7 dB gap in MSE over CS-based methods at a rate of 0.5 bits/sample.
  • Reduced Bit Rate: For a desired MSE, SQuaTS requires significantly fewer bits than direct scalar quantization, particularly when the signal is sparse (k << T). The required bit rate scales logarithmically with the signal length T and linearly with the sparsity k.
  • Computational Efficiency: While ML decoding can be complex, the proposed CoMa decoder offers a substantial reduction in computational complexity, making SQuaTS practical for real-time applications.
  • Distributed Performance: In distributed settings with multiple sparse signals, SQuaTS also shows significant accuracy improvements over distributed CS methods.

Limitations and Future Work

  • A-priori Knowledge of Sparsity: The current SQuaTS design assumes knowledge of the sparsity level k (or an upper bound). While the paper notes that performance degrades gracefully if the true sparsity differs from the assumed k, optimal performance requires accurate knowledge. Future work could explore adaptive methods for estimating k in real-time.
  • Codebook Design: The paper uses randomly generated codebooks. While effective, exploring structured or optimized codebook designs could potentially further improve performance or reduce complexity.
  • Decoding Algorithms: The paper proposes CoMa as an efficient decoder but acknowledges that other advanced decoding algorithms (e.g., for noisy group testing) could be integrated to further enhance robustness or performance.
  • Quantization Mapping: While the codebook design is independent of the input distribution, the overall MSE is affected by the choice of the scalar quantizer. Optimizing this mapping for specific signal distributions could be a direction for future research.
  • Multi-hop Network Complexity: While the framework is extended to multi-hop networks, the analysis assumes simplified network policies. More complex network scenarios and their impact on performance could be investigated.

Summary updated

BibTeX
@article{cohen2021serial,
  author = {Alejandro Cohen and Nir Shlezinger and Salman Salamatian and Yonina C. Eldar and Muriel Médard},
  title = {{Serial Quantization for Sparse Time Sequences}},
  journal = {IEEE TSP},
  year = {2021},
  doi = {10.1109/tsp.2021.3083985},
}
Figure