The symbol that builds the staircase

The staircase a separable kernel builds put two kernels with the same correlation along each axis side by side on a Toeplitz-block-Toeplitz system, and found a block-circulant preconditioner treating them completely differently. On the separable kernel $\rho^{|k_1|+|k_2|}$ its step count stayed between 18 and 22 while the correlation ran from 0.5 to 0.98 and the condition number from 62 to 818,561. On the isotropic kernel $\rho^{\sqrt{k_1^2+k_2^2}}$ it climbed from 17 to 36. The reason was the shape of the preconditioned spectrum: a product of two one-dimensional spectra makes a staircase of ten treads on a 10 × 10 grid, and conjugate gradients pays for treads; the isotropic kernel’s spectrum was a ramp of thirty-eight clusters.

The preconditioner was T. Chan’s: the block circulant nearest the matrix in the Frobenius norm, built by averaging along each axis separately, which is natural for a product kernel. The essay proposed one built for the other kind. “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.”

It gathers a staircase, and a better one than Chan’s — on the separable kernel. The isotropic ramp it shortens by a fifth.

Three circulants #

A circulant is fixed by its eigenvalues, and the three here differ only in where those come from.

Chan’s minimises $\lVert C - A\rVert_F$ over all block circulants with circulant blocks. For each offset it averages the two diagonals that compete for one circulant slot, weighted by how many entries each contributes, along each axis; four orders of conditioning and four steps built it and checked the minimisation against a fit.

The symbol circulant has as its eigenvalues the kernel’s two-dimensional symbol $f(\theta_1, \theta_2) = \sum_k \kappa(k)\,e^{i k\cdot\theta}$ sampled at the grid frequencies $\theta = 2\pi j/m$. That needs no closed form for the isotropic kernel’s symbol, because sampling a transform at those frequencies is the same as transforming the sequence periodised with period m: the circulant’s first column is the kernel summed over all its wraps, $c(j_1, j_2) = \sum_w \kappa(j_1 + w_1 m, j_2 + w_2 m)$, carried until the terms are below rounding. At ρ = 0.98 that is close to two hundred wraps in each direction.

Strang’s keeps only the nearest wrap: the circulant’s first column copies the matrix’s central diagonals. It is the cheapest and the one the circulant that cannot be indefinite found going indefinite in one dimension, which Chan’s average cannot.

The solves are the earlier essays’: conjugate gradients to a relative residual of $10^{-10}$ on the dense $m^2 \times m^2$ operator, a fixed right-hand side, and the preconditioned spectrum computed as that of $C^{-1/2} A C^{-1/2}$, with a cluster counted wherever consecutive sorted eigenvalues are more than one per cent apart.

The separable kernel gets the treads #

The figure at the top of the page is step counts against the grid side at correlation 0.9.

On the separable kernel Chan’s circulant takes 10, 18, 20, 21, 26, 26 and 28 steps at sides 4 to 16: the count grows slowly with the grid, as the earlier essays found. The symbol circulant takes 9 at side 4 and then 8, 8, 8, 8, 8, 8. From a side of 6 the count does not move at all.

The spectrum shows why. Under the symbol circulant sixty-four of the hundred eigenvalues are exactly one, and the other thirty-six fall on five more levels: six treads, against Chan’s ten. Turn the dial across correlations, or change the grid, and the count of treads does not change: six at every side from 4 to 10, six at every correlation from 0.5 to 0.98.

Sixty-four is $(m-2)^2$, and that is the whole explanation. The separable kernel’s matrix is a Kronecker product, $A = T \otimes T$, of the one-dimensional Kac–Murdock–Szegő matrix with itself, and periodising a product kernel periodises each factor, so the symbol circulant is $C = C_1 \otimes C_1$ with $C_1$ the one-dimensional symbol circulant. Then $C^{-1}A = (C_1^{-1}T) \otimes (C_1^{-1}T)$. For the one-dimensional kernel $\rho^{|k|}$, $T - C_1$ has rank two: the periodised sequence differs from the original only by the geometric tails that wrap around, and those are two rank-one terms. So $C_1^{-1}T$ is the identity plus rank two — $m - 2$ eigenvalues at one and two others, $a$ and $b$ — and the Kronecker square has eigenvalues $1$, $a$, $b$, $a^2$, $ab$, $b^2$, with one repeated $(m-2)^2$ times. Six numbers, whatever m is, whatever ρ is. Conjugate gradients in exact arithmetic would finish in six steps; in floating point, with the extreme levels spread by rounding, it takes eight. An orthogonalisation nobody calls one found the finite-termination property failing in floating point because the residuals lose their orthogonality; six levels are few enough that the loss costs two steps.

The rank-two fact is checked rather than assumed: the one-dimensional matrix minus its symbol circulant has exactly two singular values above $10^{-10}$ of the largest at sides 6, 10 and 16. It is the same structure the circulant the problem did not contain used to solve a matrix differing from a circulant in two corner entries — a transform and a two-by-two correction. Here the correction is not applied; it is left in the preconditioned operator, where it costs two eigenvalues per axis and nothing else.

Set beside the earlier picture, the symbol circulant’s staircase is the same idea carried one step further. Chan’s average, built to be nearest in the Frobenius norm, does not reproduce $C_1 \otimes C_1$ exactly for the one-dimensional optimum, and its one-dimensional preconditioned spectrum is a cluster of values near one rather than $m - 2$ copies of one exactly — so its products spread into ten levels instead of six. The symbol circulant gives up Frobenius optimality, which the proposal correctly expected, and gains an exact identity plus rank two in each factor, which it did not.

And pays for it in the condition number #

The symbol circulant does not win by making the condition number small. On the separable kernel at ρ = 0.98 its preconditioned condition number is 9,801 against Chan’s 92, because one of the six levels sits at 0.009: the two outlying one-dimensional eigenvalues include a small one, and squaring it puts a tread a hundred times below one. At ρ = 0.9 it is 361 against 61. The step count rises from 6 at ρ = 0.5 to 14 at 0.98, where the rounding has more to resolve across that range, but every one of those counts is below Chan’s.

This is the essay’s earlier finding in its sharpest form. Two dimensions and the cluster that thins found conjugate gradients’ cost in two dimensions set by how many distinct clusters the spectrum has, not by its extent, and here a spectrum a hundred times wider than Chan’s is cheaper to solve because it has six levels instead of ten.

The isotropic ramp, shortened #

On the isotropic kernel — the one the proposal was for — the symbol circulant leaves a ramp. At sides 4, 6, 8 and 10 its preconditioned spectrum has 11, 17, 23 and 30 clusters, against Chan’s 11, 25, 32 and 38. Shorter, and growing with the side at the same rate: about three clusters for every unit of side, where the separable kernel’s stays at six. The step count tells the same story. From a side of 6 to 16 it runs 19, 22, 26, 31, 33 and 35 against Chan’s 23, 25, 29, 37, 39 and 41 — about a sixth fewer steps on every grid, and the same growth.

Turn the spectrum’s dial to the isotropic kernel and the picture is the earlier essay’s ramp, under both circulants: no run of eigenvalues at one, no level that holds more than a handful, a smooth climb — from 0.23 to 9.0 under Chan’s circulant and from 0.085 to 21 under the symbol’s. The symbol circulant’s ramp is wider and has fewer steps on it; it is not a staircase.

So the prediction fails in the part it signed. Sampling the isotropic kernel’s own symbol does not gather the ramp into treads. It does what a better approximation of the symbol would be expected to do — the eigenvalues it assigns are closer to the operator’s, so the preconditioned spectrum is somewhat more compact — and it does it without changing the shape of the problem.

Neither difference is small #

The obvious explanation for the contrast would be that the separable kernel’s matrix differs from its symbol circulant by a small-rank correction and the isotropic kernel’s does not. Measured, that is half true. The isotropic difference is effectively full: 80 of its 100 singular values are above $10^{-10}$ of the largest, decaying smoothly. But the separable difference is not small either. Its rank is exactly $4m - 4$ — 36 on the 10 × 10 grid, a cliff from $10^{-4}$ to $10^{-15}$ after the 36th — because $T\otimes T - C_1\otimes C_1 = (T - C_1)\otimes T + C_1 \otimes (T - C_1)$, two terms of rank $2m$ sharing four dimensions.

A difference of rank 36 in a matrix of order 100 would, read by the usual argument, leave 36 eigenvalues free to wander and cost up to 36 extra steps. It costs two, because the eigenvalues it moves do not wander: they are products of the same two one-dimensional outliers, and products of two numbers take only six values. The treads come from the Kronecker structure of the preconditioned operator, not from a small difference. A kernel that is not a product has no such structure to inherit, whatever circulant is fitted to it, and that is the sense in which the earlier essay’s staircase belongs to the separable kernel rather than to any preconditioner.

Strang’s circulant #

The third construction, keeping only the nearest wrap, is the earlier field’s cautionary tale in two dimensions. On the separable kernel it is positive definite and costs 14 to 32 steps, worse than both alternatives and growing with the correlation; its largest preconditioned eigenvalue is 2,500 at ρ = 0.98. On the isotropic kernel it takes 18 steps at ρ = 0.5, 32 at 0.7, and from 0.85 it is indefinite — its smallest eigenvalue is negative, and conjugate gradients has no business with it. Copying the central diagonals throws away exactly the tail the symbol circulant sums, and an isotropic kernel’s tail along the diagonals of the grid is longer than along its axes, so truncating it at the nearest wrap cuts the most where the kernel is longest.

The symbol circulant is positive definite on both kernels at every correlation, because the symbol of a positive-definite kernel is positive and its samples are its eigenvalues. Chan’s average is positive definite by construction. The two safe circulants are the two that sum; the one that truncates is the one that fails.

Why the symbol is not enough on its own #

A limit the matrix never reaches opened this line of argument with the symbol as the object that describes a Toeplitz family: its extremes give the condition number of the infinite matrix, which finite sections approach from below. A circulant sampled from the symbol is the finite object that agrees with the symbol exactly at the grid frequencies, so it is natural to expect it to be the best possible circulant approximation whenever the symbol is the right description. On the separable kernel it is, and on the isotropic kernel it is still the better of the two by a sixth.

What the symbol cannot carry is the boundary. A finite Toeplitz matrix is the infinite operator truncated to a box, and the truncation is what every circulant has to approximate; the symbol describes the interior. In one dimension the box has two ends and the truncation error is rank two. In two dimensions a separable kernel’s box error factorises into two one-dimensional ones, each still rank two, and the product structure confines their effect to six levels. An isotropic kernel’s box has a perimeter of $4m$ sites, each coupled to the outside by the kernel’s full two-dimensional tail, with nothing that factorises — and that perimeter grows with the side, which is why the ramp grows with it too: about three clusters for every unit of side. The rate the condition number predicts gave conjugate gradients’ rate from the condition number as a bound; on these spectra the bound is irrelevant, because the separable spectrum is wider and cheaper, and what decides the count is how the boundary error is arranged rather than how large the spectrum is.

What this means for a nearly separable field #

The practical reading is narrower than the proposal hoped and more useful than the measurement first looks. A covariance that factorises along the axes — which correlation functions built as products do, and which many practitioners choose for exactly that convenience — should be preconditioned by the circulant sampled from its symbol, not by Chan’s: the step count is then independent of the grid and nearly independent of the correlation, eight steps from a side of 6 to 16. A covariance that does not factorise gets about a sixth fewer steps from the symbol circulant than from Chan’s, and keeps its growth with the grid.

Between the two, the earlier essay’s knife edge matters. It found the staircase dissolving a tenth of the way from the city-block norm to the Euclidean one — a kernel $\rho^{(|k_1|^p+|k_2|^p)^{1/p}}$ at $p = 1.1$ already had a ramp. Whatever the symbol circulant buys on the exactly separable kernel is therefore bought only there, and a field that is separable to modelling accuracy rather than exactly may see none of it. That is the measurement the last section names.

What these grids do not show #

Two kernels, sides up to 16 for step counts and up to 10 for spectra, correlations from 0.5 to 0.98, one right-hand side, dense matrices. Nested-dissection or multigrid preconditioners, which a practitioner would set against these on a two-dimensional field, are not compared; and the cost of building the symbol circulant — a periodised sum over hundreds of wraps at high correlation, or a closed-form symbol where one exists — is not counted, though it is paid once per kernel rather than once per solve. Nor is a kernel with a closed-form symbol and slow decay tested, where the periodised sum would need thousands of wraps and a closed form would be the only practical route; the Matérn family is the obvious case, and its symbol is known.

Still open: separable plus a correction, and the count from one dimension #

A kernel that is separable plus a small part. Add to the separable kernel a fraction ε of the isotropic one. The symbol circulant of the sum is the sum of the symbol circulants, and the preconditioned operator is a small perturbation of the Kronecker product with six levels. The prediction with a sign is that the six treads broaden into six clusters whose width grows with ε, that the step count stays near eight while those clusters stay under the one-per-cent threshold, and that it then climbs towards the isotropic count — so that the knife edge of the earlier essay, measured in ε rather than in p, has a width that can be read off before the solve.

The step count from one dimension. The separable count is now fully explained by two one-dimensional numbers, the outliers $a$ and $b$ of $C_1^{-1}T$. Their values follow from the rank-two correction in closed form, and the count of steps conjugate gradients needs to resolve six levels whose extremes are $a^2$ and $b^2$ is a one-line bound; whether that bound, computed from the one-dimensional kernel alone, predicts the eight steps on every grid and the rise to fourteen at ρ = 0.98 is the test that would turn this staircase into a formula.