The condition number of the model

A condition number answers a question of the form: if the data moves by this much, how much can the answer move? The answer depends on what “the data” is allowed to be, and κ(A) makes one particular choice — the data is all n² entries and they may move independently.

For a Toeplitz matrix that is the wrong choice — as a nearby problem of the wrong kind shows from the backward-error side — and this essay measures how wrong.

The ladder #

Take the same 40×40 Kac–Murdock–Szegő matrix as the previous essay, at ρ = 0.999, where κ = 7.88·10⁴. It can be described at four levels of tightness, each a subset of the one above.

As 1,600 entries. Every entry independent. This is what κ assumes.

As 79 constant diagonals. A general Toeplitz matrix, 2n − 1 numbers.

As 40 numbers. A symmetric Toeplitz matrix, which is what this one is.

As one number. ρ, which is the whole content of ρ^|i−j|.

Both quantities are monotone along that ladder by construction — a smaller set of perturbations can do less damage and can explain less — so the interesting question is not the direction but where along the ladder each of them moves.

The condition numbers #

1,600 entries 78,800 79 diagonals 33,000 40 numbers 31,800 one number 61.9

Two facts, and the second is the one worth having.

Constant diagonals buy a factor of 2.5. Going from “any perturbation” to “a Toeplitz perturbation” — which is the structural restriction the whole subject is named after — takes the condition number from 78,800 to 33,000. Imposing the symmetry as well takes it to 31,800, which is nothing.

The last rung buys three decades. From 31,800 to 61.9, a factor of 513, for the step from “forty numbers” to “one number”.

The last rung is a limit rather than a measurement, though, and how well a finite matrix realises it is a separate question the ladder cannot answer.

The asymptotic is excellent where it is not needed and degrades where it is. Across ρ = 0.5, 0.7, 0.8, 0.9 and 0.95 the measured κ at n = 128 reaches 99.9%, 99.6%, 98.9% and then 87.9% of the limit, while the limit itself climbs from 9 to 1,521. So the shortfall grows monotonically as the family approaches the singular limit — the one direction in which the number is being relied on.

Which is a caution about the last rung rather than a correction to it. Twelve per cent is small beside the factor of 513 that rung buys, so nothing in the ladder’s shape changes. What it means is that the one-number description is the rung whose value must be measured at the size in hand rather than read off a limit: the gap between symbol and matrix is a function of ρ and n together, and at n = 128 it is already 12% at a ρ the family reaches easily. A reader taking Szegő’s number as the condition number of their matrix is taking a lower bound whose slack they have not checked.

Two of those three ratios do not move across the family and the third does, and the difference is the finding rather than the shape.

    ρ        κ          Toeplitz ⁄ dense   symmetric ⁄ dense   dense ⁄ parameter
   0.5     8.9·10⁰          0.413              0.397                 18
   0.9     2.8·10²          0.420              0.404                211
   0.99    7.0·10³          0.419              0.403              1,031
   0.9999  8.0·10⁵          0.419              0.403              1,301

The structural rungs are constant to three digits across five orders of magnitude in κ — 0.419 and 0.403, not “about a factor of two”. That is a stronger result than the essay set out to claim and it says what those rungs are: a property of the description, unchanged by how hard the particular matrix is.

The parameter rung is not. It is worth a factor of eighteen at ρ = 0.5 and thirteen hundred at ρ = 0.9999 — and it saturates there: 18, 79, 211, 454, 1031, 1273, 1301. So three decades is the ceiling rather than the value, reached only once ρ passes 0.99, and at the easy end of the family the one-parameter description buys less than an order and a half.

The reason is in the fourth column of the ladder read on its own. The parameter condition number is 1.36, 1.50, 1.65 and 2.09 at ρ = 0.5 through 0.95 — essentially flat, because the solution barely depends on ρ there — and then climbs to 6.8, 61.9 and 613 as the family approaches its singular limit. Both ends of the ratio eventually grow, and the advantage stops widening.

Which is worth having, because it sharpens the essay’s claim rather than weakening it. The parametrisation’s advantage is largest exactly where the problem is hardest, and it is largest by a bounded amount. A reader carrying “the last rung is worth a thousand” to a well-conditioned member of the family would be carrying a number that is two orders too large, and a reader carrying “the structural rungs are worth a factor of two” is carrying one that holds everywhere.

Why the saturation is the interesting half #

A ratio that grows and then stops is a different object from one that grows, and it is worth saying what stopped it.

The parameter rung’s condition number measures how far the answer moves when ρ moves. Near ρ = 1 the matrix approaches singularity as a function of ρ, so a small change in ρ is a large change in the answer, and that number climbs. Meanwhile κ climbs too, for the same reason. Past ρ ≈ 0.99 they climb together and the ratio between them is fixed.

So the ladder’s bottom rung is not immune to the family’s difficulty; it is delayed. Below ρ = 0.95 the one-parameter description is almost perfectly conditioned — 1.36 to 2.09 — because the answer hardly depends on ρ at all. Above it the description starts to inherit the problem, and by ρ = 0.9999 it has inherited 613 of the 798,000.

That is the honest general form of the essay’s claim. A tighter description does not remove the conditioning; it postpones it. How far it postpones it is a factor with a ceiling, and the ceiling here is about 1,300 — which is large, is worth having, and is not the “the model has one number in it so nothing can go wrong” that a reader might take from the bottom rung read alone.

Which is the wrong place for the drop to be #

The natural expectation is that the structural restriction — the constant diagonals — is where the benefit lives. It is the restriction a numerical analyst would name, it is the one that defines the class of matrix, and it is the one that buys the fast algorithm.

It buys a factor of two and a half in the conditioning.

The restriction that buys three decades is the one a modeller would name: the matrix is not “a Toeplitz matrix”, it is “ρ to the power of the separation”, and the thing that could be wrong about it is ρ. That is not a linear-algebra structure at all. It is a statement about where the numbers came from.

There is a version of this that everybody already knows and does not connect: the condition number of a matrix depends on the units its rows and columns are measured in, and equilibrating changes it by decades. That is the same observation — a change of units is a restriction of the perturbations to those that respect the units — and this collection has an essay on it, and a second on the componentwise condition number that scaling cannot move.

What this ladder adds is that the sequence continues past scaling. Units are one restriction; the structure is another; the parametrisation is a third; and the last one is worth more than the two before it put together.

How the structured number is computed #

It is worth writing out, because the definition is the whole of why the answer means what it means.

The solution of Ax = b is a function of A. Restrict A to move only within a set of admissible perturbations — a linear space, spanned by matrices E₁ … E_p — and the derivative of x in the direction Eₖ is −A⁻¹E_k x. Assemble those p vectors as the columns of a matrix, weight each so that a unit coefficient corresponds to a unit change in ‖ΔA‖, and the largest amplification any admissible perturbation can produce is the 2-norm of what results.

Multiply by ‖A‖ and divide by ‖x‖ and it is a relative-to-relative number, comparable with κ.

Three consequences fall straight out.

With no restriction it is κ, which is the amplifier in its usual form. If the admissible set is everything, the assembled matrix is A⁻¹ times an isometry and its norm is ‖A⁻¹‖, so the whole expression is ‖A‖‖A⁻¹‖. That is the top rung and it is a check on the machinery rather than a result.

It depends on b. Unlike κ, the structured condition number is a property of the system and not of the matrix alone, because the derivative involves x. That is not a defect: a restricted perturbation does its damage in specific directions, and whether those directions matter depends on where the answer is.

And it is a supremum that is attained, unlike an estimate that can be fooled. The direction achieving it is the leading singular vector of the assembled matrix, which means the number is a worst case that can be exhibited rather than a bound. Every claim above about what κ over-states is a claim about a perturbation somebody could construct.

And the backward error runs the other way #

The same ladder, with the previous essay’s quantity on it:

1,600 entries 2.0·10⁻¹⁷ 79 diagonals 1.15·10⁻¹⁴ 40 numbers 5.6·10⁻¹² one number none

Restricting the perturbations makes the problem better conditioned and makes the backward error worse, and at the bottom rung the backward error is not merely worse — there is no perturbation of the model that explains the computed answer at all.

That is a trade with no free end, and it is worth stating in the form a reader can use.

Describing a problem more tightly is a claim about what can vary. The reward is that less can go wrong: the answer is less sensitive because fewer things are allowed to move. The price is that fewer things being allowed to move makes it harder for anything to explain a computed answer, and past some point nothing does.

Both halves are the same statement about the same set, read from two directions. The set of admissible perturbations is small; a small set contains no large damage, and it also contains no explanation.

What the last rung means in practice #

The one-parameter rung is not an abstraction. A great many matrices in computation are one or two numbers wide.

A Kac–Murdock–Szegő matrix is a correlation length. A discretised Laplacian is a grid spacing. A convection–diffusion stencil is a Péclet number. A Tikhonov-regularised system is a regularisation parameter and the original data. A finite-element mass matrix is a density and a mesh. In all of these the entries are computed from a handful of numbers by a formula, and the entries cannot move independently because nothing that produced them can move them independently.

So the useful question for such a matrix is not what κ says. It is: how sensitive is the answer to the numbers the model actually contains? That is a derivative with respect to a parameter, it costs one solve per parameter, and for a one-parameter family it costs one solve.

At ρ = 0.999 it comes out at 61.9. The answer to a system whose condition number is 78,800 is sensitive to the number the matrix is made of at the level of two significant figures lost, not five.

The ladder is not always this shape #

One measurement is worth adding because it bounds the finding rather than extending it.

Along the whole family — ρ from 0.5 to 0.999, κ from 8.9 to 78,800 — the ratio between the structured condition number at the symmetric-Toeplitz rung and κ is 0.40, and it does not move. Four decades of conditioning, and the benefit of the constant diagonals is the same 40 per cent throughout.

That is a negative result about a hope this essay could have been written to support: the idea that structure is worth more as the problem gets harder. On this family it is worth exactly as much at κ = 9 as at κ = 78,800, which means the structural restriction is not fighting the ill-conditioning at all. It is removing a fixed fraction of a fixed kind of damage.

The last rung is different: the factor of 513 there does grow with ρ, because what it removes is precisely the near-singular direction the family is heading towards. That is the difference between a restriction that happens to exclude some perturbations and one that excludes the perturbations that matter, and it is only visible by sweeping.

The caution, which is large #

Everything above says κ over-states the danger. It over-states it only for the perturbations the restriction excludes, and there is one source of perturbation that respects no restriction at all.

Rounding error is not structured. When a solver forms a quantity from the entries of a Toeplitz matrix, the errors it makes are independent per operation, and the perturbation they correspond to is a general matrix. That is precisely the previous essay’s finding read from this side: the explaining perturbation is not Toeplitz because the arithmetic that produced it does not know the matrix is.

So the two halves of this pair say something more precise together than either says alone.

If the uncertainty in the data is structured — a mis-measured ρ, a mesh spacing known to three digits, a correlation length estimated from data — then the structured condition number is the right number and κ is over-stating by three decades.

If the uncertainty is the arithmetic — rounding, an approximate solve, a truncated iteration — then it is unstructured, κ is the right number, and the structured one is a statement about a kind of error that is not occurring.

Most real problems have both, in unknown proportion, which is the honest end of this. What can be said is that computing only κ answers the second question and is routinely quoted as though it answered the first.

One number a modeller could ask for #

If only one thing came out of this pair it would be a quantity worth naming, because it has no name and it is one solve.

For a matrix generated from parameters θ by a formula, the parameter sensitivity of the answer is

‖A‖ · ‖A⁻¹ (∂A/∂θ) x‖ ⁄ (‖∂A/∂θ‖ ‖x‖)

which is one derivative, one solve, and two norms. For a one-parameter family it is a scalar. For a handful of parameters it is a small matrix whose largest singular value is the worst case and whose singular vectors say which combination of the parameters the answer is sensitive to — which is information κ cannot carry at all, because κ has no parameters in it.

That last part is the reason to bother. A modeller told “κ is 10⁵” learns that the problem is hard. A modeller told “the answer moves by 62 units per unit of relative change in ρ, and by nothing in the other three parameters” learns which measurement to go back and improve.

It is the same distinction this collection drew between a normwise and a componentwise condition number, one level further out: the normwise number describes the matrix, the componentwise one describes the entries, and this one describes the model.

Two routes to the ladder #

The condition numbers here are computed as norms of a Jacobian: the derivative of the solution with respect to each admissible perturbation direction, assembled into a matrix and measured. The backward errors are computed as constrained minimisations over the same directions. The two use the same basis and nothing else in common, and they are dual — one is the largest damage a unit perturbation can do, the other is the smallest perturbation that does a given damage.

They can be checked against each other at the ends. At the dense rung the condition number must equal ‖A‖‖A⁻¹‖ and the backward error must equal Rigal and Gaches’s ‖r‖/(‖A‖‖x̂‖), both of which have closed forms, and both agree to the last digits. At the one-parameter rung the backward error must be infeasible whenever the residual has a component outside a one-dimensional subspace, which is what the feasibility check reports.

A ladder whose ends are pinned by closed forms is a ladder whose middle is worth reading.

The refusal #

The assertion is fed the one-parameter basis asked for without its parameter.

The basis at that rung is the single matrix dA/dρ, whose entries are |i − j|·ρ^(|i−j|−1), and it is not defined without ρ. The tempting behaviour is to return a zero matrix and carry on, which produces a perturbation set containing nothing — and a perturbation set containing nothing has a condition number of zero and a backward error of infinity, both of which look like this essay’s findings taken to their limit and neither of which is a fact about any matrix.

That is the failure worth guarding here rather than anywhere else, because the finding at that rung is already that the condition number is small and the backward error is absent. A bug that produced the same shape would be indistinguishable from the result.

What is next #

Every zero in this collection’s current run so far has arrived on its own: a divisor going to zero, a curvature changing sign, an eigenvalue leaving for infinity, a determinant that was identically zero before anybody looked. The last two essays are about the other half, and it is the half a program actually contains — the zeros that are never met and are always written down, by somebody, in a comparison against a constant.