A rank that is a number of digits

The previous essay ended on a sentence that reads like a hedge and is not one: the numerical rank of a block is a property of a matrix and an accuracy together. This essay is what that costs, and the answer is a straight line.

The measurement #

One block. Two clusters of 128 points, on [0, 1] and on [2, 3], so the separation ratio q = (r_x + r_y)/d is exactly 1/2 — the geometry the previous essay’s null result is measured on. Count the singular values above ε·σ₁ for a sequence of ε:

The measured column is a straight line against the number of digits, at 0.554 columns a decade. Two digits cost one column. Fourteen digits cost nine.

That is a different kind of statement from this block is low rank. It says the exchange rate is constant: there is no accuracy at which the price per digit jumps, no cliff, and no regime where buying one more digit is suddenly unaffordable. Everything a code does with this format is a consequence of that flatness, because it means an accuracy can be chosen from what the answer needs rather than from what the storage will bear.

The other line #

The right-hand column of the table came from four numbers and no entry of the matrix.

The expansion in the previous essay converges at rate q and its truncation at order p has relative error at most q^(p+1)/(1 − q). Solved for the smallest p reaching ε, that is a predicted rank, computable from the two intervals’ endpoints before anything is evaluated. At q = 1/2 it comes to 3.32 columns a decade — because log₁₀ 2 is 0.301, and one over that is 3.32.

So both quantities are linear in the number of digits, which is the agreement, and the constants differ by a factor of six, which is the disagreement. The bound is an upper bound at every point measured, and it has to be: the decomposition is optimal and the expansion is one particular rank-p matrix.

Which of the two a code uses, and it is not the smaller one #

The obvious reading is that the bound is bad and the measurement is what matters. That is wrong in a way worth spelling out, because it is the reading that produces a program which cannot run.

A hierarchical format has to decide how much memory to allocate for a block before it compresses it, and on the problems this is for it has to decide without forming the block. The bound is the only one of the two numbers available at that moment. It comes from the geometry, it costs four subtractions, and it is an upper bound — a bound beside the quantity it bounds, which is this collection’s usual arrangement — which is the safe direction, because a rank allocated too generously wastes memory and a rank allocated too meanly loses accuracy silently.

So the six is not an error in the bound; it is the price of the bound being computable in advance. What the measurement buys is the knowledge that the price is a factor and not an order of magnitude, which is what makes the bound usable at all. A bound loose by a thousand would be a bound nobody allocates from.

The gap moves both lines, and not by the same amount #

The one geometric quantity in the whole story is q, and it is a knob.

Move the two intervals apart and q falls. At a gap of a quarter of an interval width q is 0.8 and the block needs 7 columns at eight digits, against a bound of 90. At a gap of eight it is 0.111, the block needs 3, and the bound says 9.

The bound is nearly thirteen times too pessimistic at the tightest separation and three times at the widest — and the tightest separation is exactly where a partition puts most of its blocks, because a partition that only compressed well-separated pairs would compress almost nothing. The bound is worst where the decision is made.

At a gap of zero the bound does not exist at all. q is 1, the expansion does not converge, and the entry in the table is a dash. That case is the subject of the fifth essay in this field, and it is the reason a partition has a test in it rather than a rule.

The slope is the sharper way to say the same thing, and it moves too.

The predicted slope is 1/log₁₀(1/q) and nothing else — 3.32 at q = 0.5, 2.11 at q = 1/3 — so it falls steeply as the gap widens. The measured slope does not fall with it.

Both slopes fall as the gap opens, and the predicted one falls faster. Across gaps of 1, 2, 3, 4 and 6 the measured slope runs 0.55, 0.50, 0.45, 0.39 and 0.34 columns a decade while the bound’s runs 3.32, 2.11, 1.68, 1.45 and 1.18. The ratio between them is 6.0, 4.2, 3.7, 3.7 and 3.5 — so the factor is six only at the tightest separation in this sweep and settles near three and a half.

The ratio between prediction and measurement is what is actually moving, and it moves early: 3.7 at gap 3 and 3.7 at gap 4, against 6.0 at gap 1. Most of the closing happened in the first two steps and the rest of the slider barely narrows it further.

So the bound is wrong about the constant and wrong about how the constant varies. It is not uniformly six times pessimistic and then correct in shape; its own slope shrinks 2.8-fold across this range while the measured slope shrinks 1.6-fold, which means the two curves are converging rather than staying parallel. A reader who calibrated a correction factor at one separation — divide the bound by six, say — would be over-correcting by nearly a factor of two at the wide end. The honest summary is that the bound has the right variable and neither the right constant nor the right sensitivity to it, and that is a different defect from being pessimistic by a fixed amount.

The factor of six is not a factor #

The two comparisons above are made at different fixed points — the first holds q at 1/2 and varies the accuracy, the second holds the accuracy at 10⁻⁸ and varies q — and neither asks the question that decides how the bound can be used: does the slope against digits depend on q the way the bound says it does?

Fitting the columns-per-decade at each separation gives

q = 0.800: 0.839 measured against 10.319 predicted. q = 0.667: 0.696 against 5.679. q = 0.500: 0.554 against 3.322. q = 0.333: 0.500 against 2.096. q = 0.200: 0.393 against 1.431. q = 0.111: 0.321 against 1.048.

The ratios are 12.29, 8.15, 6.00, 4.19, 3.64, 3.26. The six in the section above is the value at one separation, and it is nowhere near constant: it varies by a factor of nearly four across the range, and it varies monotonically, so it is a trend rather than scatter.

The reason is that the two lines have different shapes in q. The bound’s rate is 1/log₁₀(1/q) by construction — that is what solving q^(p+1) = ε for p gives. The measured rate falls like (log₁₀(1/q))⁻⁰·⁴², near the square root and less than half as steep. So the bound does not merely sit above the truth; it climbs away from it as the clusters approach.

There is a second reading of the same fitted exponent, and it points somewhere this collection has been twice already. A rate that falls like the square root of a quantity the bound treats linearly is the shape the Krylov degree has against ‖A‖t, and the consequence is the same in both places: the pessimistic version of the law is not merely a constant too large, it has the wrong curvature, so extrapolating it beyond where it was calibrated goes wrong in a direction the calibration cannot warn about. Here the extrapolation is from a comfortable separation to a tight one, and the tight one is where the blocks are.

Which makes one repair unavailable #

That closes off the obvious way to make the bound useful, and it is worth closing off explicitly because it is what a reader will reach for.

Having measured a factor of six, the tempting move is to allocate from the bound divided by six — a calibrated estimate, still cheap, still computable from four subtractions, and six times tighter. It does not work. At q = 0.8 the true factor is 12.3, so bound-over-six under-allocates, and under-allocating is the direction that loses accuracy silently. At q = 0.111 the true factor is 3.3, so it over-allocates by nearly a factor of two and gives back most of what the calibration was for.

And the failure is worst exactly where it matters. A partition puts most of its admissible blocks at the tightest separation its test allows, because a partition that only compressed well-separated pairs would compress almost nothing — so the blocks whose allocation is under-estimated by a calibrated bound are the majority of them.

So the section above is right that the bound is worth having and right about why, and the reason is narrower than it looks. The bound is usable because it is an upper bound, not because it is a fixed multiple of the answer. Its safety is a property of the inequality; its looseness is a property of q and is not a number. Any use that treats the gap as calibratable turns a guarantee into an estimate, and does so in the unsafe direction on most of the partition.

What the measurement does buy is the sizing decision one level up: the looseness runs from three to twelve, not from three to a thousand, so a code that allocates from the bound is over-allocating by one order of magnitude at worst and can budget for that. A bound whose looseness is bounded is a usable bound, and that is the statement the six was standing in for.

What a straight line here means for a program #

Three consequences, and the third is the one this field turns on.

A storage budget is a linear function of the digits. Doubling the digits does not double the memory; it adds a fixed number of columns per block. Storage against accuracy is therefore a gentle trade, not a cliff, and a code that runs out of memory can give back digits one at a time.

There is no natural stopping point. Nothing in the curve says stop here. A sparsity pattern says what to keep; a numerical rank does not, so the choice has to come from outside the matrix. This collection has a whole field about problems whose answer is not determined by the data, and this is the same shape of question about a representation rather than about a solution.

And what to set it from is not the matrix. Since the price per digit is constant, the sensible question is how many digits the answer needs — which is a question about the condition number of the problem and about what the result is for. The essay on the compression as a backward error is where that closes, and the sentence it arrives at is: decide the digits the answer needs, divide by κ, and compress to that.

What sets the slope, which is not the kernel #

The 0.554 is worth taking apart, because a constant that appears in a table without a mechanism is a number a reader has to take on trust.

The exchange rate is one over the logarithm of the ratio between consecutive singular values. This block’s ratio is about 1/52 — the values run 1, 2.40·10⁻², 4.59·10⁻⁴, 8.47·10⁻⁶ — so log₁₀ 52 is 1.72, and one over it is 0.58. The fitted 0.554 differs from that by the small non-geometric part of the head of the spectrum, which is what a fit over seven points ought to differ by.

So the slope is set by the decay ratio, and the decay ratio is set by the geometry. What it is not set by is which smooth kernel was chosen. Replace 1/r by log r on the identical points and the spectrum is 1, 2.09·10⁻², 4.24·10⁻⁴, and the count at eight digits is the same 5. That is not a coincidence and it is not a general law either: the two kernels are related by a derivative, which preserves the expansion’s structure, and a kernel unrelated to either — one that oscillates, say — behaves completely differently. The fourth essay in this field is about that case and it is the one where all of this stops working.

The reading to carry is narrower than smooth kernels are compressible. It is that the decay rate belongs to the pair of clusters, and the kernel decides only whether an expansion of that kind exists at all. Everything in the table above would be reproduced by any kernel with a convergent separable expansion on those two intervals, and none of it survives a kernel without one.

The one place the line bends #

Everything above is measured on an admissible pair — two clusters that do not touch. There is one setting of the gap where the whole account changes character and it is the leftmost row of the second table.

At a gap of zero the two intervals share an endpoint. q is exactly 1, the expansion does not converge, the bound is undefined, and the entry is a dash. The block is still compressible — 12 columns at eight digits out of 128 — but nothing above predicts that number, and the third essay in this field measures what makes it different: the 12 becomes 13 when the block is sampled twice as finely, and the 5 of an admissible pair does not become anything.

That is the distinction a partition is built around. It is not that a touching pair is incompressible; it is that its cost is a function of the discretisation as well as of the geometry, so a code cannot budget for it from the geometry alone. Given the choice between a block whose price is known before the problem is discretised and a block whose price has to be measured afterwards, a format takes the first and refuses the second — which is what the admissibility test in the fifth essay does, in one comparison of four numbers.

Two decades below the roundoff, and the tail #

The last row of the first table is worth reading carefully, because it is the only one that is not on the line.

At 10⁻¹⁴ the count is 9, where the line predicts about 8. The reason is not that the decay changed: it is that the block’s tenth singular value is 2.8·10⁻¹⁶, which is the unit roundoff, and the ones below it are numerical noise rather than singular values of the matrix. A ratio of 10⁻¹⁴ sits close enough to that floor for the count to pick up a column that is not carrying information.

That is a small effect here and it is a large one in a code, because a formatted arithmetic asked for a tolerance below the working precision will happily allocate rank for it. The essay on the site about the zeros nobody meets and everybody writes is about exactly this class of parameter, and the rule it arrives at applies unchanged: a tolerance below the unit roundoff is not a tolerance, it is a request for every column there is.

What the straight line is not #

Two readings this figure invites and neither of them survives contact with the next essay.

It is not a claim that the block is cheap in absolute terms. Five columns out of 128 is cheap; five columns out of 8 would not be. Everything here is a statement about a ratio, and the ratio only becomes a saving when the block is large — which is a statement about what a partition does with the matrix rather than about any single block, and the essay on storage against size is where it is settled.

And it is not a claim about the whole matrix. The line above is one block. A hierarchical representation is a hundred blocks of a dozen different shapes, each with its own q and therefore its own line, and the accuracy asked of it is applied to each block against that block’s own largest singular value. What that does to the accuracy of the assembled matrix is a separate question with a surprising answer — measured, the whole matrix comes out about thirty times more accurate than the per-block tolerance asked for, and the factor belongs to the kernel rather than to the number of blocks.

The general shape of that mistake is one this collection keeps meeting. A quantity controlled locally and reported globally is two quantities, and the ratio between them is nobody’s parameter. the-part-of-a-solver-that-may-be-rounded is the same shape about precision, and a-small-residual-is-not-a-small-error is the same shape about a residual. Here it is about a tolerance, and the honest thing is to measure the ratio rather than assume it is one.

The refusal #

The claim under test is the one every course states in its second week: that the rank of a matrix is a property of the matrix.

It is true in the algebra and this essay does not dispute it. What is refused is its use — the reading that a matrix has a rank which a program can go and find. The assertion that the same 128 × 128 block needs the same number of columns at 10⁻² and at 10⁻¹⁴ is fed those two counts, 2 and 9, and it fails.

The refusal is deliberately not fed a hard case. It is fed the easiest possible one: one matrix, two readings, twelve decades apart, nothing changed in between. If the count were a property of the matrix the two numbers would be equal, and they are not equal by a factor of four and a half. That is the whole of it, and it is the sentence the rest of this field is written on top of.