The kernel with nothing to compress

Three essays in, this field has a thesis and no case against it. That is a bad sign, and the fix is not a caveat but an experiment.

The experiment #

The measurement in the previous essay held the geometry fixed and refined the sampling. This one does something different and more pointed: it holds the geometry fixed in the sense that matters — the separation ratio q — and grows everything else.

Two parallel line segments, each of length L, a distance 2L apart. The half-widths are L/2 each and the centres are 2L apart, so

q = (L/2 + L/2) / 2L = 1/2

at every scale. Sixteen-fold changes in L leave q at exactly one half; the assertion behind the figure checks that equality to twelve digits rather than assuming it, because an experiment whose independent variable secretly moves is not an experiment.

Both segments are sampled at 256 points, and two kernels are evaluated on the same points:

1/r and cos(κ r)/r , κ = 40 .

Count the singular values above 10⁻⁸ of the largest.

The left column is the previous essay’s result, restated: a smooth kernel does not know how big the picture is. The right column is what happens when the kernel does.

Why the segments are parallel #

This is the detail that took the longest to get right and it is worth the paragraph, because the obvious arrangement produces a confirmation of the thesis and it is an artefact.

Put the two clusters collinear — on [0, 1] and [2, 3], as in every earlier essay — and the distance between a point of one and a point of the other is |x − y|. Then

cos(κ|x − y|) = cos κx cos κy + sin κx sin κy

by the addition formula, which is a sum of two products of a function of x with a function of y. The numerator is exactly rank two. Multiplied entrywise by 1/|x − y|, which the earlier essays measure at rank five, the whole block has rank at most ten — and measured, at κ = 160 and 256 points, it is ten.

So the collinear arrangement says the oscillatory kernel is as compressible as the smooth one, and it says so for a reason that has nothing to do with kernels: one-dimensional geometry admits an addition formula that two-dimensional geometry does not. Move the segments off each other’s line and the distance is √((x − y)² + h²), which is not linear in x and y separately and has no addition formula, and the rank behaves as the table above shows.

That is the shape of mistake this collection keeps a whole habit for. A measurement taken in the cheapest available geometry confirmed the thesis; the confirmation was a property of the geometry; and every gate the site has would have passed it, because the number was correct and the assertion that read it was correct too.

The growth, and what sets it #

The right-hand column grows like a power. Fitted against the scale on a log–log axis the exponent is about 0.53, so the rank goes roughly like √L — or, in the quantity that has a meaning, like the square root of the number of wavelengths across the pair.

The mechanism is standard and worth stating in one sentence, and it is the same mechanism a block nobody can call sparse runs into from the other side, where the entries are small everywhere and the rank is nevertheless full. The block is a sampling of cos(κ r)/r as a function on a rectangle, and how many separable terms a function needs is set by how much it oscillates across that rectangle. A smooth kernel varies by a fixed amount across the rectangle however large the rectangle is, because r and the rectangle scale together and 1/r is homogeneous. cos(κ r) does not scale: κ is a fixed number with units, so a rectangle twice as large contains twice as many oscillations.

Sweeping the wavenumber itself makes both halves of that visible at once.

The smooth column is the same five integers at every wavenumber tested. At κ = 5, 10, 15, 20, 25, 40, 60 and 80 the smooth kernel’s ranks are 6, 6, 6, 6, 6 — not approximately, the same integer at every scale and every κ — while the oscillatory kernel’s largest rank runs 28, 33, 38, 72 and 92 across κ = 15, 20, 25, 60 and 80. One kernel does not know the wavenumber exists and the other is governed by nothing else.

That is a sharper statement than the exponent, and it is the one the admissibility rule needs. A rank of 6 whatever κ does means the smooth kernel’s compressibility is a property of the geometry alone, which is exactly what a ratio of lengths can express — and it is why the rule works there. The oscillatory rank tracks the wavelength count closely enough to be read off it: 92 against 101.9 wavelengths at κ = 80, 28 against 19.1 at κ = 15, within about a third across a factor of five in the wavenumber.

The number that decides an oscillatory rank is therefore κL²/d — the count of wavelengths across the geometry, which for these segments is κL/4π — and no ratio of lengths can see it. q is dimensionless. The wavelength is not. A test written in q alone is blind to the one quantity that matters here, which is why an admissibility rule that works for the Laplace kernel does not transfer to the Helmholtz one and why high-frequency scattering is a different subject rather than a harder instance of this one.

The collapse, which is the test the claim was owed #

That paragraph asserts something stronger than the table shows, and the difference is worth separating. The table varies one thing — the scale L, at κ = 40 — and finds a rank that grows like √L. From that alone the honest statement is the rank grows with the scale. The claim that the deciding quantity is κL, that the block does not know the wavenumber and the size apart, is a claim about a second parameter the table never moved.

It is a testable claim and it has a clean test: hold κL fixed and vary its two factors against each other. If the block is a function of the product, blocks with the same product must have the same rank however that product was assembled.

Parallel segments of length L a distance 2L apart, 128 points a side, rank at ε = 10⁻⁸, with W the number of wavelengths across the separation:

Every group with the same W has the same rank, and two of the three groups reach it three independent ways — across a factor of sixteen in the wavenumber and eight in the size. Not close: the same integer. The block genuinely is a function of the product and of nothing else, which is the result the mechanism predicts and the table could not have distinguished from a coincidence of the particular κ it was measured at.

The smooth column is 6 at every one of those rows too, and that is not a throwaway. A reader could reasonably suspect the whole effect of being an artefact of the growing geometry — more points, a longer segment, a worse-conditioned block — in which case both kernels would drift. One of them does not move at all across the same sweep, so whatever is moving the other one is the kernel. That is the size the rank does not notice measured a second way, on a geometry built to make it fail.

Extending the sweep to κ = 80 at L = 4 gives W = 101.9 and a rank of 53, and fitting the six ranks 9, 12, 16, 22, 33, 53 against W from 3.2 to 101.9 gives an exponent of 0.512 over a factor of thirty-two — which is a better-supported square root than the 0.53 fitted over the factor of sixteen above, and lands on the same number. assertTheOscillatoryRankIsAFunctionOfTheProduct in the kernel library runs the three collapse groups and this fit, and fails if any group disagrees with itself.

The reason to insist on the collapse rather than the exponent is that the two carry different consequences for a code. An exponent says how expensive the largest block will be. The collapse says that a rank estimate measured on one wavenumber transfers to another, provided the geometry is scaled to match — so a solver may cache admissibility decisions across a frequency sweep instead of re-measuring at each one, which is exactly the sort of decision rank is a decision is about and exactly the sort of thing an unverified proportionality would have made unsafe.

What breaks, exactly #

It is worth being precise about which parts of the field survive this and which do not, because “the format fails” is too coarse and would be wrong.

The partition survives. The tree, the admissibility test, the block structure and the recursion are all still well defined and still produce a correct representation of the matrix. Nothing in them consults the kernel.

The storage claim does not. The whole argument for n log n storage rests on the rank of an off-diagonal block being a constant, and here it is a growing function of the block’s physical size. At a fixed wavelength and a refining mesh the rank is bounded — the geometry is not growing, only the sampling — so the format is usable on a fixed scattering problem. What fails is the sentence about solving a larger problem at the same cost per unknown, which is the sentence the format was built for.

And the accuracy claim survives untouched. Every representation built at ε is still within ε; the compression is still a backward error; the residual of a solve with it is still the representation’s error. What has changed is only how many numbers that costs. This is the good kind of failure — an expense rather than a wrong answer — and it is worth saying so, because the alternative failure mode is the one this collection spends most of its time on. It is also the distinction the cheap rank and what it cannot see draws about a rank estimate: being expensive and being wrong are different verdicts and want different responses.

The number the geometry cannot see, stated carefully #

There is a temptation to summarise this as the format needs smooth kernels, and that summary is close enough to be repeated and loose enough to mislead, so it is worth replacing with the actual condition.

What the expansion in the first essay of this field needs is that the kernel be asymptotically smooth: that its derivatives of order p, taken away from the diagonal, grow no faster than p! times a constant to the p over r to the p. That condition is what makes the Taylor coefficients fall off geometrically, and it is satisfied by 1/r, by log r, by 1/r² and by every derivative of any of them — which is to say by the Green’s functions of the Laplace, Stokes and elasticity operators and by the covariance kernels of most of statistics — the family a hierarchy with no grid behind it builds its partition for, where no mesh is needed because the kernel supplies the geometry.

cos(κr)/r satisfies it too, with a constant that contains κ. That is the whole subtlety: the kernel is not disqualified, its constant is bad, and a constant that contains a dimensional parameter interacts with a geometry that has a size. The bound reads

rank ≈ (something in q) + (something in κ · diam) ,

and a partition that only controls the first term controls half of it.

So the condition is not smooth and it is not not oscillatory. It is that the kernel must have no length scale of its own, or that whatever length scale it has must be large compared with every cluster the partition produces. A code can check the second version cheaply — it knows κ and it knows its clusters — and the checking is exactly the modified admissibility test the last section describes.

That reframing also explains the two ends of the drag on the hero figure. At κ = 5 a wavelength is longer than the whole picture at every scale drawn, the second term is small, and the two curves sit almost on top of each other. At κ = 80 the second term dominates by the third scale. Nothing about the kernel changed between those two figures except a number with units.

The company it keeps #

This site has three other places where a method meets a problem it cannot exploit, and the family resemblance is worth naming.

Randomisation does not create structure is the closest: a randomised low-rank approximation of a matrix with a flat spectrum returns nothing useful, and nothing else would either, because there is no low-rank structure to find. The failure is honest in the sense that no method could do better.

The spectrum that predicts nothing is different in kind. There the method works and the predictor fails: GMRES on a non-normal matrix converges at a rate the eigenvalues do not describe, so the quantity everybody reaches for is the wrong quantity. This essay is of that second kind. The format works; q is the wrong quantity; and the right one is not in the geometry at all.

A limit the matrix never reaches is the third: Toeplitz structure buys an exact spectrum and does not buy a well-conditioned problem, and the half that gets summarised away is the half that decides whether anything can be solved.

Three ways for a structural claim to be less than it looks: the structure is absent, the predictor is the wrong one, or the structure is real and buys something other than what was wanted. This field’s counterweight is the middle one.

What a code should do about it #

The measurement suggests three responses and only the third is satisfactory.

Detect it. The rank a block turns out to need is available after the block is compressed, so a format can notice that its ranks are growing and report it. That is worth doing and it is a diagnosis rather than a remedy: by the time the ranks are large the memory has been spent.

Refuse it. An admissibility test written in κ·diam as well as in q — a pair is admissible when it is well separated and small compared with a wavelength — produces a partition whose blocks are all genuinely low rank. That works and it produces a great many more blocks, because the second condition puts an absolute cap on cluster size where the first is scale-free. The storage stops being n log n and starts being something worse.

Or change the representation. The methods that actually solve high-frequency scattering keep a low-rank structure that is directional: a block is factored separately for each range of incoming directions, and each of those factors is small. That is a different format with a different partition and it is not this one.

The honest summary is that this field’s format is a Laplace-kernel format, that it applies to everything whose Green’s function is asymptotically smooth — which is a great deal — and that the cases it does not cover are not covered by patching it.

What the counterweight is for #

A field with a thesis and no case against it is not a field with a strong thesis; it is a field whose experiments were chosen by whoever holds the thesis. This site has run into that twice before and written it down both times, so the pattern is worth naming rather than performed.

The first was in the randomised field, where the essay on what randomisation does not create exists because every other essay in that field is about a method working. The second was in the sequence field, where three essays found a rule that reads a free measurement and beats every constant, and the fourth found the boundary — a decision half of which is invisible in any solve, where the same shape of rule loses by ninety-three per cent.

The shape is the same in all three. The positive essays establish a mechanism; the counterweight establishes the mechanism’s domain, which is the part a reader needs in order to know whether their own problem is inside it. Without it the collection has taught a technique and not taught when it applies, which is the failure mode of every method paper ever written.

Here the domain is stated as sharply as the measurements allow. Inside it: kernels with no length scale of their own, clusters separated by their own diameter, ranks that are constants. Outside it: one number with units, and a rank that grows like the square root of the picture with no size at which it stops.

The refusal #

The claim under test is the one the first three essays of this field would leave a reader holding: that a matrix built from a kernel and two clusters of points has low-rank off-diagonal blocks.

It is fed the case at the far end of this sweep — two parallel segments of length 8 at a distance of 16, so q is exactly the ½ of every compressible measurement in this field, with cos(40 r)/r in place of 1/r. The assertion that the block needs at most twelve columns at 10⁻⁸ is handed 53, and it fails.

What makes the refusal worth the code is that it is fed the same geometry the thesis was measured on. A counterexample with a different q would be a demonstration that admissibility matters, which is a different essay and already written. This one holds every quantity the earlier essays vary, and changes only the one they never mention.