A Framework for Robust Lossy Compression of Heavy-Tailed Sources

1. Problem Statement

The paper addresses the rate-distortion problem for heavy-tailed sources, specifically $\alpha$-stable distributions (where $0 < \alpha < 2$).

• The Challenge: Standard rate-distortion theory relies heavily on the Mean Square Error (MSE) as a distortion measure. However, $\alpha$-stable distributions (for $\alpha < 2$) possess infinite second moments, rendering MSE undefined and inappropriate.
• Existing Limitations: Previous attempts to quantify distortion for these sources used alternative metrics like Mean Absolute Error (MAE) or Mean Square Root Absolute Error (MSRAE). These metrics suffer from:
  • Limited Validity: They are only valid for specific ranges of $\alpha$ (e.g., MAE requires $\alpha \ge 1$).
  • Discontinuity: Metrics can jump from finite to infinite values as $\alpha$ crosses critical thresholds (e.g., $\alpha=1$), despite the source statistics changing continuously.
  • Lack of Unification: There was no unified theoretical framework for the rate-distortion function of general heavy-tailed sources.

2. Methodology

The authors propose a novel framework based on the concept of "Strength" ($s_\alpha$) as the distortion measure.

• The Strength Measure:
  • Defined based on a reference $\alpha$-stable random vector $\tilde{Z}_\alpha$.
  • The strength $s_\alpha(X)$ of a random variable/vector $X$ is the infimum of $s > 0$ such that the expected negative log-likelihood of the normalized error $X/s$ with respect to the reference distribution is less than or equal to the differential entropy of the reference distribution:
    $$s_\alpha(X) \triangleq \inf \left\{ s > 0 : -E\left[ \log f_{\tilde{Z}_\alpha}\left(\frac{X}{s}\right) \right] \le h(\tilde{Z}_\alpha) \right\}$$
  • Properties: This measure generalizes the standard deviation (for $\alpha=2$, Gaussian) and the scale parameter for Cauchy ($\alpha=1$). Crucially, it is finite for all $0 < \alpha \le 2$.
• Rate-Distortion Derivation:
  • The authors leverage the property that $\alpha$-stable distributions maximize entropy among all distributions with a fixed strength constraint.
  • They derive the rate-distortion function $R(D)$ by establishing the trade-off between the compression rate and the strength of the quantization error.
• Quantization Design:
  • They develop a Lloyd-Max-like iterative algorithm to design optimal quantizers that minimize the strength of the error.
  • They analyze Uniform Quantizers in the high-rate regime (small quantization step size $\Delta$) to determine asymptotic optimality.

3. Key Contributions

1. Generalized Rate-Distortion Function:
   • Derived the rate-distortion function for scalar and vector symmetric $\alpha$-stable (S$\alpha$S) sources under a strength constraint.
   • The result is logarithmic in the strength-to-distortion ratio:
     $$R(D) = \max \left\{ \log \left[ \frac{s_\alpha(X)}{D} \right], 0 \right\}$$
   • This generalizes the classic Gaussian result ($\alpha=2$) and the specific Cauchy result ($\alpha=1$).
2. Unified Framework for Heavy-Tailed Sources:
   • Provided a theoretical basis that overcomes the discontinuity and range limitations of fractional lower-order moments (like MAE).
   • Extended the analysis to vector sources, including sub-Gaussian S$\alpha$S vectors and vectors with independent S$\alpha$S components.
3. Optimal Quantizer Design:
   • Proved that for strength-optimal quantizers, the quantization boundaries must be the midpoints between representation points (similar to MSE), though the representation points themselves are not conditional means.
   • Proposed an algorithm to compute optimal representation points for heavy-tailed sources (e.g., Cauchy).
4. High-Rate Asymptotic Analysis:
   • Proved that uniform quantizers are asymptotically optimal in the high-rate regime for heavy-tailed sources under the strength measure.
   • Showed that non-uniform quantizers offer little advantage over uniform ones at high rates, mirroring the Gaussian case.

4. Key Results

• Rate-Distortion Performance: The rate-distortion function scales logarithmically with the ratio of source strength to distortion.
• Uniform vs. Non-Uniform: In the high-rate limit, the optimal quantizer is uniform. The quantization error strength scales linearly with the step size $\Delta$: $s_\alpha(X - \hat{X}_\Delta) \approx s_\alpha(U) \cdot \Delta$, where $U$ is a uniform random variable on $[-1/2, 1/2]$.
• Cost of Heavy Tails:
  • Numerical analysis reveals that achieving the same quantization quality (distortion level) for a Cauchy source ($\alpha=1$) requires significantly more representation points (bits) than for a Gaussian source ($\alpha=2$).
  • Specifically, the convergence rate of the error strength to zero is approximately twice as slow for Cauchy sources compared to Gaussian sources ($s_2(U)/s_1(U) \approx 2.124$).
• Application to Communication:
  • In a communication channel with additive Cauchy noise, a strength-based quantizer outperforms quantizers optimized for $p$-th absolute moments and closely matches the Maximum Output Entropy (MOE) quantizer.
  • It provides higher mutual information for the quantized channel compared to Gaussian-optimized quantizers when the noise is heavy-tailed.

5. Significance

• Theoretical Unification: The paper bridges the gap between classical Gaussian rate-distortion theory and the complex world of heavy-tailed statistics, providing a mathematically rigorous and continuous framework.
• Practical Implications for AI and Signal Processing:
  • Machine Learning: Given that neural network weights and gradients often exhibit heavy-tailed behavior, this framework offers a principled way to compress these models (quantization) without relying on invalid MSE assumptions.
  • Sensor Networks & Robotics: Provides optimal strategies for compressing data from sensors that generate impulsive or heavy-tailed noise.
  • Hardware Efficiency: Demonstrates that standard uniform quantizers (used in ADCs) remain optimal even for heavy-tailed sources, provided the system accounts for the higher bit-rate required to achieve a specific distortion level.
• Benchmarking: Establishes $\alpha$-stable distributions as the fundamental benchmark for heavy-tailed compression, analogous to how Gaussian distributions serve as the benchmark for finite-variance sources.

In conclusion, the authors successfully extend the foundational pillars of lossy compression (rate-distortion theory and quantization) to the domain of infinite-variance sources, proving that while the mathematical tools must change (from MSE to Strength), the fundamental principles of uniform quantization and logarithmic rate scaling remain robust.