The transform zoo · Close Enough

1What correlation costs

Code two correlated coordinates separately and you pay for the same information twice.

Fig 6.4.1Rotating the coding axes

Rotate the coding axes Each axis is coded with its own bell curve, costing about $\log_2 \sigma$ bits. The panel shows the total relative to the original axes. Snap to the principal axes: that is the lowest a rotation can go. Then read the last line.

For Gaussian data the saving from perfect decorrelation has a closed form, the coding gain:

\kbits{G} \;=\; \frac12 \sum_{i=1}^{d} \log_2 \frac{\sigma_i^2}{\lambda_i} \;=\; \frac{d}{2}\,\log_2 \frac{\text{arithmetic mean of the variances}}{\text{geometric mean of the eigenvalues}}

where $\sigma_i^2$ are the variances of the coordinates as given and $\lambda_i$ the spectrum. A flat spectrum gives no gain. A lopsided one gives a lot.

2The zoo

Transform	Decorrelates	Exactly invertible on integers?	Cost per vector	Used in
PCA / KLT rotation	fully (linearly)	no	$d^2$	lossy transform coding
DCT, Hadamard, random rotation	partly, no training	no (Hadamard: nearly)	$d \log d$	JPEG, OPQ-style preprocessing
byte shuffle, bit planes	nothing; regroups	yes	$d$	Blosc, generic float pipelines
Delta / XOR with a neighbour	along one axis	yes	$d$	time series, 6.5 The prediction zoo
Lifting (integer rotations)	approximately	yes	$d^2$	JPEG 2000, lossless audio
Triangular prediction	fully (linearly)	yes	$d^2/2$	this page

3Why you cannot just rotate

A rotation is exactly what the lossy world uses (3.4 From spectrum to bit budget). For lossless coding it has a fatal flaw.

Fig 6.4.2Rotations break the integer grid

The grid does not survive Left: the int8 values sit on a square grid. Right: after a rotation the same points sit on a tilted grid. Rounding the rotated coordinates to integers moves each point, and nothing guarantees it can be moved back.

The obvious workaround is to quantize the rotated coefficients, reconstruct, and code the exact leftover separately. That works, and it has a knob: the step $s$ used for the coefficients.

It helps (2,477 → 2,367), but it leaves most of the prize on the table.

4The lossless twin of a rotation

Go back to the playground and read its last line: predicting y from x reaches exactly the same number as the best rotation.

That is not a coincidence. A rotation diagonalises the covariance with an orthogonal matrix. A triangular matrix does it too:

\Sigma \;=\; \kbook{L}\,\kbook{L}^{\!\top} \qquad\text{(Cholesky)} \qquad\Longrightarrow\qquad \sum_i \log_2 \kres{L_{ii}} \;=\; \tfrac12 \log_2 \det \Sigma \;=\; \tfrac12\sum_i \log_2 \lambda_i

Read row $j$ of $L$ as a recipe: predict coordinate $j$ from coordinates $1 \dots j-1$ ; what is left has spread $L_{jj}$ . The product of those leftover spreads equals the product of the eigenvalues’ square roots. Same volume, same bits.

And unlike a rotation, it never leaves the grid:

Coordinate 1 is coded as it is.
Coordinate 2: the decoder already has coordinate 1 exactly, computes the same prediction, rounds it the same way, and adds the coded difference. Exact.
Coordinate 3: predicted from the exact 1 and 2. And so on.

Triangular prediction: the lossless decorrelatornumpy + scipy

from scipy.linalg import solve_triangular

m = X_train.mean(0)
L = np.linalg.cholesky(np.cov((X_train - m).T) + np.eye(d) / 12)   # fit once

def innovations(x):                    # encoder side; x is a vector of integers
    z = solve_triangular(L, x - m, lower=True)
    return z * np.diag(L)              # x_j minus its prediction from x_1..x_{j-1}
# coordinate j is then coded with a bell curve of spread L[j, j] around its prediction

Fig 6.4.3Spread explained by earlier coordinates

What the earlier coordinates explain Blue: each coordinate’s spread on its own. Orange: its spread once the coordinates before it are known. The gap, on a log scale, is the saving.