Part I · Representing a signal · Chapter 4

Giving each Gaussian a feature: least squares

About 20 minutes. Bring a little patience for one small matrix; every number is worked out for you.

4.1 Placement is half the model

Chapter 3 ended with the matrix A: how much each Gaussian owns each token. That is everything placement decides. The other half is what each Gaussian carries. Your model does not let a network guess these vectors; it computes the best possible ones, in closed form, for the placement it is given. That choice cut the error by about a fifth, and it shapes how the whole model is trained.

By the end you can write the field as AZ, derive the least-squares features and their ridge version, explain why a Cholesky factorisation solves them, and say in one sentence why the geometry can still be trained through the solve.

First, a guess: if a Gaussian half-owns a token, should its feature simply be the average of the tokens it owns? Write yes or no, and why.

4.2 The field as a matrix product

Give Gaussian k a feature vector zk of D numbers (in your work D = 384). By Chapter 3, the field at token p is Σk Apk zk. Stack the vectors as the rows of a matrix Z and every token at once is one product:

F̂ = A Z (P × K) times (K × D) gives (P × D)

The target is the teacher's grid, a matrix T of the same shape, P × D. Before fitting, your code scales each token's row of T to length one (row_l2_normalize). Each of the 384 columns is fitted with the same A, so it is enough to think about one column; the examples below use D = 1.

Weighted mean. The obvious choice of feature: the average of the targets, weighted by ownership, zk = Σp Apk tp / Σp Apk

A worked example: three tokens, two Gaussians. Gaussian 1 owns token 1, Gaussian 2 owns token 3, and they split token 2. The targets are 1, 1, 0.

TokenA (G1, G2)Target tField, weighted meanError
11, 011.0000
20.5, 0.510.667−0.333
30, 100.333+0.333

Here z₁ = (1 + 0.5)/1.5 = 1 and z₂ = 0.5/1.5 = 0.333. The mean squared error is (0 + 0.111 + 0.111)/3 = 0.0741. The problem is visible: token 2's value leaks into Gaussian 2's average and spoils token 3. Each average is computed as if no other Gaussian existed.

4.3 Least squares: choose all features together

Instead, ask directly for the features that make the field closest to the target:

Least squares. Choose Z to minimise the squared error ‖AZ − T‖², the sum of squared differences over all tokens and channels.

At the minimum, nudging any zk cannot help. That happens exactly when the remaining error T − AZ has no component along any column of A, which gives

Normal equations. AᵀA Z = AᵀT AᵀA is a small K × K matrix: entry (j, k) measures how much Gaussians j and k overlap. AᵀT is K × D: what each Gaussian sees of the target.

For the example, AᵀA has diagonal 1.25 and off-diagonal 0.25, and AᵀT = (1.5, 0.5). Solving the 2×2 system gives z₁ = 1.167, z₂ = 0.167:

TokenTargetWeighted meanLeast squares
111.0001.167
210.6670.667
300.3330.167
Mean squared error0.07410.0556

The error drops by a quarter. Notice z₁ = 1.167 is larger than every target: the features are no longer averages. They are coefficients that work together, with Gaussian 1 over-shooting slightly on its own token so that the shared token and token 3 come out better. Overlapping Gaussians become a smooth basis, not a set of separate averages.

4.4 Ridge: a safety pull towards the averages

Least squares has one weakness. Suppose two Gaussians sit almost on top of each other, so every token is split nearly 50/50: rows (0.51, 0.49), (0.50, 0.50), (0.49, 0.51), targets 1, 0.5, 0. The exact solution is z = (25.5, −24.5): enormous, opposite features that nearly cancel, fitted to 1% differences. Change one target by 0.02 and both features move by about 0.5. Such features mean nothing, and they make training unstable.

The fix adds a penalty for straying from a sensible default Z₀:

Ridge regression towards a prior. Minimise ‖AZ − T‖² + λ‖Z − Z₀‖², where λ (lambda) > 0 sets the strength of the pull. The solution satisfies (AᵀA + λI) Z = AᵀT + λZ₀ with I the identity matrix. As λ grows, Z moves to Z₀; as it shrinks, to plain least squares.

Your model uses λ = 0.01 and takes Z₀ to be the weighted means of 4.2 (lstsq_coefficients.py). Textbook ridge pulls towards zero; pulling towards the weighted means instead means a poorly determined feature falls back to a sensible average rather than to nothing. In the near-collision case, ridge gives z = (1.47, −0.47), and the same 0.02 change in a target moves the features by only about 0.03.

Is 0.01 strong? Each row of A sums to one, so the diagonal of AᵀA averages at most P/K: 4 on a 16×16 grid with 64 Gaussians. Against that, 0.01 is tiny. In the three-token example ridge changes the features only in the third decimal (1.165, 0.168). The pull matters only when the system is nearly singular, which is exactly when it is needed.

What it bought

On the 16×16 target with 64 Gaussians (the model of that time, called Gridless64), training with least-squares features instead of weighted means lowered holdout dense error from 0.0001343 to 0.0001041, 22.5% lower (seed 20261112, 800 holdout images). Two further seeds gave a three-seed mean of 0.00010442, 22.2% lower. Linear-probe accuracy, a check of what the features still encode (Chapter 7), did not change. Swapping least squares into an already-trained weighted-mean model, with its placement frozen, gained only 6.7% (seed 20261108): most of the gain comes from training placement against the better features, so that overlapping Gaussians are used as a basis. Caveat: these 800 holdout images were reused throughout development, so they are not a sealed test.

4.5 Solving it: the Cholesky factor again

The matrix M = AᵀA + λI is symmetric, and for any non-zero v, vᵀMv = ‖Av‖² + λ‖v‖² > 0. So it is positive definite, which is Chapter 2's condition, and it therefore has a Cholesky factor: M = LLᵀ with L lower-triangular, now K × K. Solving with it takes two easy passes:

  1. Factor M = LLᵀ, once per image.
  2. Forward substitution: solve LY = R from the top row down, where R = AᵀT + λZ₀.
  3. Back substitution: solve LᵀZ = Y from the bottom row up.

A triangular system is easy because each row introduces one new unknown. In the example with λ = 0.01: M has diagonal 1.26 and off-diagonal 0.25, so a = √1.26 = 1.1225, b = 0.25/a = 0.2227, d = √(1.26 − b²) = 1.1002, exactly the 2D recipe of Chapter 2. With R = (1.51, 0.5033), forward substitution gives Y = (1.3452, 0.1852), and back substitution Z = (1.1650, 0.1683).

In your code, RidgeCoefficients.forward in lstsq_coefficients.py forms M and R with GPU matrix products, factors M in the _cholesky kernel (pivots floored at λ, which changes nothing in exact arithmetic because every pivot of M is at least λ), and runs both substitutions in _cholesky_solve. One 64×64 factor serves all 384 channels. The single-tile kernel stops at 128 Gaussians; 256 use a blocked version (lstsq_blocked.py), which Chapter 18 covers.

4.6 Geometry outside, features inside

Step back and look at the structure. The error depends on two kinds of unknowns: geometry (centres, Cholesky factors, masses), which enters non-linearly through A; and features, which enter linearly. For any geometry the best features are a closed-form solve, so the error becomes a function of geometry alone:

E(geometry) = minZ ‖A(geometry) Z − T‖²

Variable projection. For problems whose unknowns split into linear and non-linear parts, eliminate the linear part by least squares and optimise only the non-linear part. The method and its derivatives were set out by Golub and Pereyra[Golub and Pereyra, 1973].

For your model this means the network never has to output 64 × 384 feature numbers. It only places Gaussians, and whatever it places is scored with the best features for that placement.

Training through the solve

Training moves the geometry downhill on E, so it needs the gradient of the error with respect to A, knowing that Z itself depends on A. One could back-propagate through every step of the Cholesky loops, but there is a shortcut. The solution always satisfies MZ = R. Differentiate that equation rather than the algorithm that solved it, and the gradient needs just one more solve with the same stored factor.

Implicit differentiation. Getting the derivative of a solution from the equation it satisfies, without differentiating the steps used to find it.

In RidgeCoefficients.backward: given the incoming gradient dZ, solve G = M⁻¹dZ with the saved factor, then

dA = (T − AZ)Gᵀ − (AG)Zᵀ, dZ₀ = λG

From dA the gradient flows back through the responsibilities (Chapter 3) to the centres, Cholesky factors and masses.

Go deeper: where the formula comes from

Write Z = M⁻¹R with M = AᵀA + λI and R = AᵀT + λZ₀. A small change gives dZ = M⁻¹(dR − dM·Z). For a loss with gradient ∂ℓ/∂Z, set G = M⁻¹ ∂ℓ/∂Z (M is symmetric). Then the change in loss is ⟨G, dR − dM·Z⟩. With dR = dAᵀT and dM = dAᵀA + AᵀdA, collecting the terms that multiply dA gives TGᵀ − AZGᵀ − AGZᵀ, which is the formula above. The Z₀ term gives λG, and because Z₀ is itself a weighted mean of A, that gradient also flows back into A. The 2003 review by the same authors covers the general theory[Golub and Pereyra, 2003].

4.7 Check yourself

Answer from memory; each question gives its reason once you choose.

1. Why can least-squares features beat weighted means on the same placement?

Weighted means treat each Gaussian as if it were alone. Least squares minimises the error of the combined field, so overlapping Gaussians act together as a basis, even if a feature leaves the range of the data.

2. What does the ridge term λ‖Z − Z₀‖² protect against?

When two columns of A are almost equal, AᵀA is nearly singular and the exact solution blows up. The pull towards the weighted means keeps such features sensible; it barely affects well-separated Gaussians.

3. Why may the solver use a Cholesky factorisation?

vᵀ(AᵀA + λI)v = ‖Av‖² + λ‖v‖² > 0 for any non-zero v. That is the condition for a Cholesky factor to exist. A itself is P × K, not square.

4. Least squares with placement frozen gained 6.7%; trained end to end it gained about 22%. What does that show?

Training against the solve changes where Gaussians go, so overlap is used as a basis. Three seeds agree to within about 1%, far less than the effect.

5. A reviewer asks how gradients reach the geometry if the features come from a linear solve. Best answer?

The solution satisfies MZ = R; differentiating that equation gives the gradient with one more solve using the saved factor. It then flows through A to the centres, factors and masses.

4.8 Close the loop

Without scrolling up, explain how your model chooses the feature vector of each Gaussian, why it is not just the average of the tokens it owns, and how training still reaches the geometry. Then compare with your first answer.

A model answer

“The field is AZ: responsibilities times one feature per Gaussian. Given the placement, the features are the ridge least-squares solution (AᵀA + λI)Z = AᵀT + λZ₀, with λ = 0.01 and Z₀ the weighted means. Unlike plain averages it accounts for overlap, so Gaussians act as a basis; the ridge keeps nearly coincident Gaussians from getting huge cancelling features. The matrix is symmetric positive definite, so it is solved with a Cholesky factor. This is variable projection: the network only places Gaussians, and the error is a function of placement alone. Gradients pass through the solve by implicit differentiation, one extra solve with the stored factor. On the 16×16 target it lowered dense error from 0.0001343 to 0.0001041, about 22%, with the probe unchanged.”

Read next Hastie, Tibshirani and Friedman, “The Elements of Statistical Learning”, 2nd edition, section 3.4.1 on ridge regression. It covers the penalty, its closed-form solution and why it stabilises nearly singular problems.

Something unclear, or want to rehearse how you would say this to a reviewer? Ask your teacher in the chat.

One-page summary of this chapter ·