9d25feaKeep the Python evidence for the entropy-rate gapJeremy Magland 1# Why LPC+ANS gets 14x when the entropy rate says 23x
3Setting: `--sigma 5 --filter bandpass --low 300 --high 2000 --taps 31 --rate 30000`.
4All numbers are bits/sample on the quantized signal z (ratio = 16 / bits).
6## Verdict
8**The entropy estimate is right, and the gap is real.** LPC+ANS is not
9suboptimal by accident — integer-residual prediction followed by a memoryless
10entropy coder structurally cannot reach the conditional entropy of this
11process. A codec that codes each sample against a discretized Gaussian
12centred at the *real-valued* prediction reaches 22.3x with a verified
13lossless round-trip; a Monte-Carlo model-based codec reaches ~23.7x.
15## The mechanism
17After optimal linear prediction from the quantized past, the prediction error
18of y_next has std s ~= 0.28 quantization steps. The conditional distribution
19of z_next = round(y_next) is therefore a Gaussian bump covering ~1-3 integer
20bins, and its shape depends strongly on the *fractional part* of the
21prediction mu: mu near a bin centre gives ~0.4 bits, mu near a bin edge gives
22~1.1 bits.
24- An ideal conditional coder uses mu per sample: mean entropy ~= **0.72 bits**.
25- LPC+ANS codes the integer residual z - floor-prediction with one pooled
26 histogram: that histogram is the *mixture* over all fractional parts,
27 entropy ~= **1.07 bits** (semi-analytic; 1.10 measured with the app's
28 15-bit integer coefficients).
30The ~0.35-0.38 bit gap **is** the 14x-vs-22x discrepancy. Raising the LPC
31order does nothing (14.6x plateau by order 64): the loss is in the residual
32coding, not the prediction.
34## Measurements (4M-sample realizations; codecs charged for all side info)
36| method | bits/sample | ratio |
37|---|---|---|
38| raw int16 | 16 | 1x |
39| order-0 entropy of z | 1.954 | 8.2x |
40| LPC(32) + ANS (app's method, reproduced) | 1.101 (+~1.5% ANS) | 14.3x |
41| LPC(128) + ANS ceiling | 1.098 | 14.6x |
42| **conditional-Gaussian arithmetic codec (real bytes, exact round-trip)** | **0.7184** | **22.27x** |
43| Gibbs posterior-predictive codec (achievable rate, 60 sweeps) | 0.674 +/- 0.065 | 23.7x |
44| timeseries-entropy estimator, M=512 (default settings) | 0.615 +/- 0.065 | 26x |
45| timeseries-entropy estimator, M=1024, thin=2 | 0.658 +/- 0.046 | 24.3x |
46| semi-analytic conditional entropy (rounding-as-noise model) | 0.723 | 22.1x |
48The true entropy rate is bracketed: <= 0.718 is *proven* by real compressed
49bytes that round-trip; ~0.674 is achievable by the model-based codec; the
50Monte-Carlo estimator's 0.62-0.68 is consistent with both. The estimator's
51Rhee-Glynn pilot (`--pilot 6`) shows RMS Delta_m <= 0.016 decaying at
52exponent ~2, so its r=1.5 truncation is sound at these settings.
54## The codec that proves it (`codec_gaussian.py`)
561. Fit an order-64 real-coefficient predictor on the block (Levinson);
57 send coefficients as float32 in the header (270 B total).
582. Fit a single residual scale s (grid search on the block); send it too.
593. For each sample: mu_t = dot(coeffs, previous 64 decoded samples);
60 code z_t with an arithmetic coder under P(k) proportional to
61 Phi((k+1/2-mu_t)/s) - Phi((k-1/2-mu_t)/s), tails folded into edge bins,
62 16-bit frequencies. Decoder computes the identical mu_t from decoded
63 samples, so tables agree bit for bit.
644. First 64 samples are coded under the marginal N(0, std_z) table.
661,048,576 samples -> 94,157 bytes = 0.7184 bits/sample = **22.27x**,
67`np.array_equal(z, decoded) == True`. Encode/decode ~7 s each in pure
68Python+numpy.
70`gibbs_predictive_rate.py` pushes further: both sides could run the
71timeseries-entropy Gibbs sampler on the decoded past (shared seed) and code
72against the Rao-Blackwellized posterior predictive of the generative model —
73the nonlinear optimum. Its measured cross-entropy is 0.674 +/- 0.065
74bits/sample (23.7x). The -log2-of-a-mean is Jensen-biased upward, so more
75sweeps would only lower it toward the true conditional entropy.
77## Files
79- `analysis_spectral.py` — semi-analytic model: Kolmogorov innovation
80 variance of S_z = sigma^2|H|^2 + 1/12; conditional vs mixture entropy;
81 empirical Wiener-predictor rates by order.
82- `lpc_ans_repro.py` — exact port of the app's integer LPC (15-bit coeffs,
83 shared shift, floor prediction, int16 wrap); reproduces 14.3x.
84- `codec_gaussian.py` — the round-tripping conditional-Gaussian codec.
85- `gibbs_predictive_rate.py` — achievable rate of the Monte-Carlo
86 model-based codec, reusing timeseries_entropy.ConditionalChain.
87- `entropy_cli_run.log`, `entropy_pilot.log`, `codec_gaussian_1M.log`,
88 `gibbs_predictive.log` — raw outputs.
90## Notes for the app / estimator
92- The app's hollow "order-0 entropy of the residual" bar is the LPC+ANS
93 *ceiling*, and the measured 14x sits right on it — the coder is fine; the
94 prefilter family is the limit.
95- The tenth method now exists in the app: `src/compress/conditionalGaussian.ts`,
96 computed with the other nine in the compression worker and drawn as its own
97 "conditional" chart group. In-browser at these settings, 100k block:
98 LPC(32)+ANS 1.119 bits (14.30x) vs cond. Gaussian AC 0.738 bits (21.68x).
99- With prediction-error std s, the fractional-phase loss of integer-residual
100 coding is ~E[H(mix)] - E[H(cond)]; it vanishes for s >> 1 (white/large
101 sigma) and grows as s drops below ~0.5 — worst exactly in the
102 narrowband, moderate-sigma regime this parameter set sits in.