The staircase a separable kernel builds

Four orders of conditioning, and four steps found the most striking number these kernels have produced. On a 10 × 10 grid the two-dimensional Kac–Murdock–Szegő kernel’s condition number runs from 62 at a correlation of 0.5 to 818,561 at 0.98, and the conjugate gradient step count with the optimal block-circulant preconditioner runs 18, 21, 21, 22, 21, 19, 18 over the same range. The parameter that makes the problem hard is the one the preconditioned solver does not notice, which the essay called the strongest available statement that the preconditioner works.

It also named the warning in its own last section. Everything held because the kernel factorises: $\rho^{|k_1|+|k_2|}$ is a product of two one-dimensional kernels, so the two-dimensional operator is the one-dimensional one squared — a Kronecker product — and its spectrum, its symbol and its preconditioned spectrum are all products of one-dimensional ones. A kernel that does not factorise, it said, has no such spectrum, and every closed form becomes a measurement.

The obvious such kernel is the isotropic one. $\rho^{\sqrt{k_1^2+k_2^2}}$ has exactly the same correlation along each axis — at a displacement of one cell horizontally or vertically it is ρ in both — and differs only along the diagonals, where it decays with Euclidean rather than city-block distance. It is positive definite, since an exponential of distance is in any dimension, and a covariance of this shape is what a two-dimensional field with no preferred directions would have. It is the kernel a user of this preconditioner is more likely to meet.

Steps against the correlation #

The system is the same Toeplitz-block-Toeplitz matrix built from each kernel, the preconditioner the same optimal block-circulant approximation — the Chan average taken along both axes — solved by transform, and the right-hand side the one the earlier essays used. Conjugate gradients runs to a relative residual of $10^{-10}$.

On the separable kernel the figure is the earlier essay’s: the unpreconditioned count climbs 43, 63, 93, 115, 143, 178 as ρ goes from 0.5 to 0.98, and the preconditioned one stays at 18, 21, 22, 21, 19, 18. On the isotropic kernel the unpreconditioned count climbs much less — 30, 39, 45, 47, 50, 51, because the isotropic operator is much less ill-conditioned at the same correlation, to judge by that count — and the preconditioned count climbs with it: 17, 22, 27, 29, 33, 36. It rises at every step of ρ, and at 0.98 it is twice the separable kernel’s.

Divided out, the difference is stark. On the separable kernel the preconditioner divides the step count by 2.4 at ρ = 0.5 and by 9.9 at 0.98: the harder the problem, the more it helps, which is what a good preconditioner for an ill-conditioned family should do. On the isotropic kernel it divides by 1.8 at 0.5 and by 1.4 at 0.98, less as the correlation rises. The same construction, applied to a kernel with the same axial correlation, goes from the best preconditioner among these Toeplitz problems to one that is barely worth its transforms.

A staircase against a ramp #

The spectra say why, and they say it in a shape rather than a number. At ρ = 0.9 the separable kernel’s preconditioned eigenvalues run from 0.27 to 16.4 and the isotropic kernel’s from 0.23 to 9.0 — by range, by the condition number the preconditioner leaves, the isotropic kernel is the better-preconditioned one, 39 against 61. But the separable spectrum is a staircase: a long flat tread near 0.39, another near 0.67, a short one near 2.5 and a few isolated values, ten clusters in all when values within one per cent of each other are counted as one. The isotropic spectrum is a ramp from 0.23 to 1.4 with a tail above it, thirty-eight clusters at the same spacing. Turn the dial and the contrast grows with ρ: the separable staircase goes from 29 clusters at 0.5 to 18 at 0.7, 14 at 0.85 and 10 from 0.9 on, while the isotropic ramp goes from 29 to 31 and then 38.

The staircase is the Kronecker product. With $A = T \otimes T$ and the preconditioner $C = C_1 \otimes C_1$, the preconditioned matrix is $(C_1^{-1}T) \otimes (C_1^{-1}T)$, whose eigenvalues are the products $\mu_i\mu_j$ of the one-dimensional preconditioned eigenvalues. The earlier essays measured that one-dimensional spectrum: m − 2 low values bunched together, one just above one, and one large one. Products of a few distinct values are a few distinct values: low times low, low times one, one times one, low times large, and so on — a handful of treads, each holding many eigenvalues, whatever the correlation does to where the treads sit. The isotropic kernel’s two-dimensional operator is not a product of one-dimensional ones, its preconditioned spectrum is not a product either, and nothing gathers its eigenvalues into treads.

The treads, predicted from one dimension #

The account can be checked number by number, because the one-dimensional spectrum is cheap. On ten points at ρ = 0.9, the one-dimensional KMS matrix preconditioned by its own Chan circulant has eigenvalues 0.519, then seven between 0.618 and 0.628, then 1.085 and 4.050. Their products are the separable two-dimensional spectrum exactly: the seven bunched values squared give the long tread near 0.39, a bunched value times 1.085 gives the tread near 0.67, a bunched value times 4.05 the tread near 2.5, and 4.05 squared is 16.40 — the largest two-dimensional eigenvalue, to eight digits. Counted at the same one-per-cent spacing, the hundred products fall into ten clusters, and the two-dimensional spectrum computed directly has ten.

That agreement holds everywhere it was checked. On every grid from 4 to 10 a side at every correlation from 0.85 up, the clusters predicted from the one-dimensional products equal the clusters measured in two dimensions — 9, 10 or 14 of them, and 5 on the 4 × 4 grid at 0.98 — and the largest product is the largest eigenvalue. At ρ = 0.98 the bunch has tightened further, seven one-dimensional values all at 0.525, which is why the staircase stops changing: once the bunch is a single value to a per cent, its products are single values too, and the number of treads is set by how many distinct one-dimensional values there are — four or five — rather than by m.

So the separable kernel’s step count can be predicted on a grid too large to compute its two-dimensional spectrum, from a one-dimensional eigenvalue problem of the side’s size. The isotropic kernel’s cannot, and that is the whole of the difference between them.

Conjugate gradients pays per tread #

That the count follows the treads rather than the range is the standard account of conjugate gradients — its residual polynomial has to be small on every cluster, and each cluster costs about a step or two however wide the spread of clusters is — and the measurements line up with it. Over every grid and every correlation, the separable kernel’s spectra hold 5 to 29 clusters and take 10 to 22 steps; the isotropic kernel’s hold 10 to 38 and take 12 to 36. At every correlation from 0.85 up on the 10 × 10 grid, the kernel with more clusters takes more steps, although it is the one with the smaller preconditioned condition number. The rate the condition number predicts is a statement about the range, and here the range points the wrong way.

The earlier essay’s own measurement fits the same account from the other side. It counted how many eigenvalues the preconditioner brings within half a unit of one — 9, 11, 13 and 17 on the four grids, at every correlation — and found the count flat. That count is flat because the staircase’s treads do not move relative to one another as ρ rises; they move together. It was a count of treads in disguise.

The count grows with the grid #

Two dimensions, and the cluster that thins found the separable count size-dependent in two dimensions where it was flat in one — 10, 18, 20, 21 on square grids against 7, 10, 10, 10 in one dimension with the same unknowns — and the essay after it found it logarithmic in the side. At ρ = 0.98 the separable kernel’s count is 11, 16, 16 and 18 on grids of 4, 6, 8 and 10; the isotropic kernel’s is 12, 24, 28 and 36, more than tripling. So the isotropic kernel loses both of the separable kernel’s properties at once: its count depends on the correlation, and it depends on the size faster. Both come from the same place. A ramp of distinct eigenvalues gets longer as the grid grows, one tread per new distinct value, where a staircase built from m one-dimensional values keeps roughly the same number of treads.

A knife edge, not a region #

The last question the difference raises is how close to separable a kernel has to be to keep the flat count. The family $\rho^{\|k\|_p}$ — the correlation raised to the p-norm of the displacement — runs from the separable kernel at p = 1 to the isotropic one at p = 2, and every member is positive definite and has the same correlation along the axes.

The flat count does not survive a tenth of the way. At ρ = 0.98 the preconditioned count is 18 at p = 1 and 25 at p = 1.1, and then 25, 28, 33 and 36 at p = 1.25, 1.5, 1.75 and 2. At ρ = 0.9 it is 21 at p = 1 and 26 at p = 1.1, and from there it drifts to 29. The cluster count says the same thing more sharply: at ρ = 0.98 the separable spectrum’s ten treads become 31 clusters at p = 1.1, and never fall below 31 again. At ρ = 0.5, where the separable kernel had no staircase to lose — 29 clusters at p = 1 — the count sits at 17 or 18 throughout.

So the correlation-independence is not a property of kernels near the separable one. It is a property of the separable one, and of the exact algebraic identity that makes its preconditioned spectrum a product; move the norm by a tenth and the identity is gone, and with it the treads. What remains past p = 1.1 is a smooth dependence on p, most of the change happening near p = 1 and the rest spread evenly to p = 2.

This is the measurement that turns the earlier essays’ warning into a size. A two-dimensional field whose correlation is exactly separable is a modelling choice — made, when it is made, for computational convenience — and the preconditioner’s indifference to the correlation is a return on that choice that does not extend to any field that is not exactly separable.

What the separable measurements were entitled to #

None of the earlier essays’ numbers is wrong. The flat count, the flat number of eigenvalues brought near one, the logarithm in the side — each is a correct measurement of the separable kernel, and each is correct because of the separability, which the essays said. What this measurement adds is the size of the gap between the family they were measured on and the family a user is likely to have. The isotropic kernel is not an exotic alternative; it is the same correlation with the directional artefact removed, and on it the preconditioner is modest.

The general lesson is one numerical linear algebra keeps teaching. A test family chosen so that its answers are closed forms — the heat equation’s sine modes, the KMS symbol, the Kronecker product — is chosen for exactly the property that makes the answers special. An index that is a pair and a solve that is d decompositions exploited the Kronecker structure on purpose, as a method. Here it had been exploited by accident, as the source of a preconditioner’s apparent indifference to the correlation. The kernel with nothing to compress made the same discovery about low-rank blocks, where a smooth kernel compressed and an oscillatory one did not, and the coarse problem is a different problem about a one-dimensional identity meeting a second axis.

What a user of the preconditioner can check #

The difference between the two kernels is invisible in the quantities a solver usually reports. The preconditioned condition number points the wrong way — the isotropic kernel’s is the smaller — and the unpreconditioned count points the wrong way too, since the isotropic system is the easier one without help. What separates them is how many distinct values the preconditioned spectrum has, and a solver does not compute that.

Two cheap checks do the work instead. The first is structural: whether the kernel factorises along the axes. If it does, the one-dimensional preconditioned spectrum, a problem the size of one side, predicts the treads, and the treads predict the count, as the section above measured. If it does not — and the p-norm family says that nearly separable is not separable enough — the one-dimensional prediction is simply unavailable. The second is empirical: run a few steps both ways and compare. On the separable kernel at ρ = 0.98 the preconditioner divides the count by ten; on the isotropic one by 1.4. A ratio under two is a signal that the preconditioner is doing little, and it can be read long before convergence from how fast the two residuals fall. A rate that does not notice the size is what a preconditioner that genuinely removes the difficulty looks like; a ratio that falls as the problem gets harder is what one that does not looks like.

Ten points a side, one isotropic kernel, one circulant #

Grids up to 10 × 10, because the preconditioned spectrum is computed densely; the step counts alone would run further. One isotropic kernel, the exponential of distance; a Gaussian or Matérn kernel of higher smoothness decays differently along the diagonals and would have its own spectrum. The preconditioner is the optimal block-circulant one; a preconditioner built for the isotropic kernel — a circulant from the two-dimensional symbol’s own values, or the Strang choice along both axes — might gather the isotropic spectrum better, and the circulant that cannot be indefinite found that the choice of circulant mattered a great deal in one dimension.

The cluster count at one per cent is a convenient measure, not the quantity conjugate gradients minimises over; at five per cent the counts are 6 to 10 for the separable kernel and 16 to 19 for the isotropic one from ρ = 0.85 up, the same ordering at a coarser grain. That the step count follows the clusters is the standard account and fits every run here; it is not derived.

Still open: a preconditioner for the ramp, and where the treads come from #

A preconditioner that knows the kernel is isotropic. The block-circulant preconditioner’s construction averages along each axis separately, which is natural for a product kernel. An isotropic kernel’s symbol is a function of the radial frequency; a circulant whose eigenvalues were sampled from that symbol directly might gather the ramp into treads of its own. The prediction with a sign is that it would, at the cost of losing the optimality property in the Frobenius norm that the Chan average has.

The step count from the treads. The treads are now predicted from one dimension; the step count is not. A rule that charged conjugate gradients a fixed number of steps per tread, calibrated on the grids here, and was then asked for the separable kernel’s count on a 100 × 100 grid from the 100-point one-dimensional spectrum alone, would turn the account into a prediction a solver could use before it ran.

A kernel that is separable plus a small correction. The p-norm family leaves separability everywhere at once. A kernel that is exactly separable plus a perturbation of controlled rank — a separable covariance with a few isotropic terms added — would keep the staircase and add a few isolated eigenvalues to it, and conjugate gradients pays a step or two per isolated value. Whether the count then grows with the perturbation’s rank rather than its size is the prediction, and it would say how to use this preconditioner on a field that is nearly separable in that sense.