Abstract
This paper presents highly efficient 1-bit and multi-bit coding schemes designed to estimate the scale parameter of heavy-tailed $\alpha$-stable distributions. By quantizing measurements into just a few bits, the proposed methods achieve estimation accuracy that closely approaches full-precision theoretical limits. These schemes significantly reduce storage and computational overhead, making them ideal for high-throughput data stream mining and compressed sensing applications.
Introduction
In modern data-intensive fields such as network traffic analysis and large-scale machine learning, data often follows heavy-tailed distributions where extreme outliers are frequent. The $\alpha$-stable distribution family is the standard mathematical framework for modeling such phenomena. However, traditional estimation techniques for these distributions typically require high-precision storage (e.g., 32 or 64 bits per measurement). In memory-constrained environments like data streams or compressed sensing, this requirement is often prohibitive. Standard rounding or truncation fails because it can discard the very outliers that characterize the distribution's scale. This research addresses the fundamental question: Can we accurately estimate the scale (spread) of these distributions using only bit-level information?
Quantization and Estimation Methods
The paper proposes moving away from storing raw measurement values in favor of a structured quantization approach:
- 1-Bit Coding: Each measurement $|y_j|^\alpha$ is compared against a fixed threshold $C$. A single bit is stored: "0" if below the threshold and "1" if above.
- Maximum Likelihood Estimation (MLE): A closed-form MLE is derived to reconstruct the scale parameter ($\Lambda_\alpha$) from the observed counts of zeros and ones.
- Bartlett Correction: To mitigate bias in small sample sizes ($n < 100$), the classical Bartlett correction is applied, significantly improving accuracy for small-batch processing.
- Multi-Bit Extension: The framework generalizes to $m$ partitions (e.g., 2-bit or 3-bit coding). Utilizing multiple thresholds not only improves accuracy but also reduces the estimator's sensitivity to the specific placement of those thresholds.
Key Insights and Theoretical Performance
A surprising finding of this work is the high efficiency of 1-bit coding. For the Cauchy distribution ($\alpha=1$), the variance of the 1-bit estimator is only approximately 20% higher than the theoretically optimal "infinite-bit" estimator. As shown in the performance analysis, the optimal variance and the corresponding optimal threshold parameter $\eta$ vary predictably with the characteristic exponent $\alpha$.
While 1-bit estimation is sensitive to the choice of threshold $C$ (or $\eta$), moving to 2-bit or 3-bit schemes (using 3 to 7 thresholds) provides remarkable stability. In the $\alpha \to 0+$ case, where the theoretical lower bound for variance is 1.0, the 1-bit scheme achieves 1.544. Stepping up to a 2-bit scheme reduces this to 1.122, capturing nearly all the information available in the original signal.
Practical Utility and Results
The effectiveness of these coding schemes was verified through extensive synthetic simulations involving $10^6$ samples across the full range of $\alpha \in (0, 2]$. Beyond variance benchmarks, the method was successfully integrated into a "one-scan" compressed sensing framework. The 1-bit scale estimator accurately identified signal sparsity ($K$), enabling the successful recovery of sparse vectors with minimal data overhead. Furthermore, the use of pre-computed look-up tables for MLE solutions ensures that the computational cost at runtime is negligible.
Limitations and Future Directions
While multi-bit schemes increase robustness, they still require a rough initial estimate of the scale to set effective thresholds. Future research will explore specialized coding for non-negative data vectors, such as those used in computer vision kernels, and extending these bit-level techniques to estimate correlations between vectors for large-scale similarity searches.
Summary updated