Universal compression of Gaussian sources with unknown parameters

Alon Orlitsky, Narayana P. SanthanamarXiv 2014 · arXiv

This paper, authored by Alon Orlitsky and Narayana Santhanam, provides a rigorous mathematical framework for compressing data coming from continuous sources (like sensors or audio) when the underlying statistical parameters are unknown.

TL;DR

The authors extend the concept of "worst-case universal compression" from discrete alphabets to uncountable ones, specifically focusing on Gaussian sources. They define a metric called attenuation—the continuous analog to redundancy—and derive exact, non-asymptotic formulas for how well a universal distribution can represent a Gaussian source with an unknown mean, unknown variance, or both.

What Problem Does This Paper Address?

In classical information theory, if you know the exact distribution of a data source, you can compress it perfectly using Shannon's entropy. However, in the real world, we rarely know the exact distribution; we might only know that the source is "Gaussian" but not its specific mean ($\mu$) or variance ($\sigma^2$).

For discrete data (like text), Shtarkov’s "worst-case redundancy" framework helps find a universal distribution that performs well regardless of which specific model in a collection is actually generating the data. But when the data is continuous (uncountable support), standard redundancy measures often become infinite or ill-defined. The authors tackle this gap by asking: Can we find a universal probability density function (pdf) that doesn't significantly underestimate any specific Gaussian model within a given range?

Methods

The authors introduce Attenuation ($\hat{A}$), defined as the integral over the support of the supremum of all possible pdfs in a class $\mathcal{P}$. Essentially, if you have a collection of Gaussian models, the "best" universal pdf is proportional to the upper envelope of all those models.

To calculate this for sequences of length $n$, the authors:

  1. Partition the Space: They divide the $n$-dimensional space of possible outcomes into regions based on where the Maximum Likelihood (ML) estimates for mean and variance fall (e.g., inside or outside the allowed parameter ranges).
  2. Coordinate Transformation: They use sophisticated Jacobian transformations to move from raw data sequences to sufficient statistics (like the sample mean and sample variance).
  3. Exact Integration: Unlike many papers that rely solely on asymptotic approximations (what happens as $n \to \infty$), this paper uses tools like the Sylvester determinant theorem to provide exact formulas for attenuation.

Datasets

Not discussed in the paper. As a theoretical work in information theory, the paper relies on mathematical proofs and derivations rather than empirical testing on specific datasets.

Key Insights and Ideas

  • The "Envelope" Approach: The optimal universal pdf is found by taking the maximum possible value any model in your class could assign to a data point and then normalizing it. The normalization constant is the "attenuation."
  • Parameter Scaling: The authors show a clear relationship between the number of unknown parameters and the growth of attenuation.
  • If only one parameter (mean or variance) is unknown, attenuation grows at a rate of $O(\sqrt{n})$.
  • If both mean and variance are unknown, attenuation grows at a rate of $O(n)$.
  • Exactness Matters: While prior literature (like Rissanen’s work) provided the "order of magnitude" for these values, this paper provides the exact constants and formulas, which is crucial for small-sample regimes where asymptotic behavior hasn't kicked in yet.

Key Results

The paper provides several landmark formulas for a sequence of $n$ i.i.d. Gaussian samples:

  • Unknown Mean (Fixed Variance): The attenuation is exactly $1 + \alpha \sqrt{\frac{n}{2\pi}}$, where $\alpha$ is the range of the mean.
  • Unknown Variance (Fixed Mean): The attenuation grows asymptotically as $\sqrt{\frac{n}{\pi}} \ln \frac{\sigma_M}{\sigma_m}$, where $\sigma_m$ and $\sigma_M$ are the minimum and maximum possible standard deviations.
  • Both Unknown: The dominant term in the attenuation is $\frac{\alpha \sqrt{n(n-1)}}{\pi \sqrt{2}} (\frac{1}{\sigma_m} - \frac{1}{\sigma_M})$. This shows that the interaction between unknown mean and unknown variance significantly increases the "cost" of universality.

Limitations and Future Work

  • Parameter Bounds: The results depend on knowing the range ($\alpha$ for mean, $[\sigma_m, \sigma_M]$ for variance). If these ranges are infinite, the attenuation becomes infinite, meaning a "truly" universal distribution doesn't exist without some prior constraints.
  • Gaussian Specificity: While the authors motivate the work using "infinitely divisible distributions" (a broad class including Cauchy, Gamma, and Poisson), the specific derivations in this paper are tailored to the Gaussian case.
  • Future Directions: A natural extension would be applying this framework to multivariate Gaussians or other exponential family distributions where parameters might be coupled in more complex ways.

Summary updated

BibTeX
@misc{orlitsky2014universal,
  author = {Alon Orlitsky and Narayana P. Santhanam},
  title = {{Universal compression of Gaussian sources with unknown parameters}},
  year = {2014},
  eprint = {1410.4550},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1410.4550},
}
Figure