The condition number that does not know

A constraint removes a direction. That is the whole of what Bx = d does to a fit — the move two ways to remove a constraint makes explicitly: the answer is no longer free to move along the row space of B, so the least-squares problem that remains lives in the null space of B and is smaller by the number of constraints.

Which raises a question nothing on this ladder has asked. If the direction removed happens to be the one the fit was badly conditioned in, the constraint has removed the difficulty, and the problem that remains is easy.

At κ(A) = 10¹² the two answers are 4.73·10⁻¹⁶ and 3.03·10⁻⁴. Twelve orders of magnitude, from the same routine, on problems whose condition numbers agree to twelve figures.

What the two problems are #

The construction is worth stating precisely because the whole page rests on the two problems being genuinely comparable.

A is built with a cliff spectrum: its singular values are 1, 1, 1, 1 and then $1/\kappa$ for the last two, so the entire difficulty of the fit sits in two right singular directions and nowhere else. The constraint block B has two rows and is orthonormal in both problems. The only difference is which directions those rows are.

Constrained difficulty: B’s rows are the two weak right singular vectors of A. The null space of B is therefore spanned by the four strong ones, and $AQ_2$ has all its singular values equal to 1 — $\kappa(AQ_2)$ = 1.00, exactly, at every κ(A) drawn.

Free difficulty: B’s rows are two of the strong directions. The null space contains both weak ones, $AQ_2$ inherits the whole spectrum’s range, and $\kappa(AQ_2) = \kappa(A)$.

Everything a caller computes about these two problems agrees. Same shape, same rank, same κ(A), same κ(B) — which is 1 in both, since B is orthonormal either way. Same norm of A, same norm of b. The answers differ by twelve orders.

Which quantity does predict it #

κ(AQ₂), and the null-space route computes it on the way without reporting it.

The route factors $B^{\mathsf T}$, forms $AQ_2$, and runs a least-squares solve on it. The conditioning of that solve is κ(AQ₂), it is available from the same factorisation that produces the answer, and it costs a singular-value decomposition of a matrix that is smaller than A — or, more cheaply, an estimate from the R factor the QR already produced.

On the two problems at κ(A) = 10¹² it reads 1.00 and 10¹², and the errors it predicts are 10⁻¹⁶ and 10⁻⁴. That is the whole of the prediction, and it is right at every point of the sweep.

So the quantity is not missing, it is discarded. A routine that returned it alongside the answer would let a caller distinguish the two problems above without knowing anything about singular directions, and no interface returns it because the answer is what was asked for.

A constraint can only make it better #

The direction of the effect is worth stating as a general fact rather than as a measurement, since it is one of the few things in this collection that goes the reassuring way.

Adding an equality constraint restricts the answer to a subspace. The least-squares problem that remains is A restricted to that subspace, and the singular values of a restriction interlace those of the original: the largest cannot grow and the smallest cannot shrink. So

$$\kappa(AQ_2) \le \kappa(A)$$

always, for every constraint and every problem. A constraint cannot make a fit harder to solve accurately, and it can make it arbitrarily easier — the ratio is unbounded, as the figure’s twelve orders show.

That is the opposite of the usual situation with constraints, where imposing one makes an optimisation harder, and it is worth understanding why the two are not in conflict. A constraint makes the problem harder in the sense that the feasible set is smaller and the objective value is worse. It makes the conditioning better because there is less room for the answer to move. Those are different quantities and only the second is what an error bound is about.

The other routes see it too #

The figure draws the null-space route, because it is the accurate one and the contrast is cleanest there. The effect is not a property of that route.

At κ(A) = 10¹², with the difficulty inside the constraint, the saddle-point route returns 1.17·10⁻¹⁶ and the method of weighting at τ = 10⁸ returns 2.72·10⁻¹⁵. With it outside, the same two return 1.00 — no correct digit at all — and 6.22·10⁻⁴.

So every route benefits from the constraint being in the right place and none of them benefits equally. The saddle-point route, which forms a cross-product and loses the digits in the assembly, has nothing to lose when the cross-product it forms is of a well-conditioned matrix: with the difficulty removed, AᵀA is as well conditioned as A, the squaring costs nothing, and it returns the best number on the page. With the difficulty left in, it returns the worst.

That is worth having beside the previous rung’s table, because it qualifies it. The route that forms AᵀA loses κ(A)² and the one that does not loses κ(AQ₂) is the summary, and what the alignment measurement adds is that the first quantity is the one a caller can compute and the second is the one that is true — so a route chosen on κ(A) is being chosen on the wrong axis twice over.

Two figures with the same horizontal axis, the same four curves and the same κ(A) at every point, differing only in a choice a caller does not make and usually cannot see. That is the page in two pictures.

What the interlacing actually gives #

The inequality κ(AQ₂) ≤ κ(A) is worth one paragraph of derivation, because it is the only part of this page that is a theorem rather than a measurement and it says how far the effect can go.

$AQ_2$ is A restricted to an $(n - m)$-dimensional subspace. Its largest singular value is the largest value of $\|Av\|$ over unit $v$ in that subspace, which is at most the largest over all unit $v$ — so $\sigma_1(AQ_2) \le \sigma_1(A)$. Its smallest is the smallest over the subspace, which is at least the smallest over everything — so $\sigma_{\min}(AQ_2) \ge \sigma_{\min}(A)$. The ratio can only fall.

How far it falls is decided entirely by the subspace. Cauchy’s interlacing theorem gives the sharp statement: removing m dimensions can raise the smallest singular value at most to the (m + 1)-th largest one, so the best a constraint with m rows can do is take $\kappa(A)$ down to $\sigma_1/\sigma_{m+1}$. With the cliff spectrum used here and m equal to the number of weak directions, that is exactly 1 — the construction is the extreme case of the theorem rather than a lucky arrangement.

And the worst it can do is nothing, which is the second curve. So the whole range between the two figures is available, the endpoints are attained, and the position within the range is not a property of any quantity computed from A alone.

Where this leaves κ(A) #

A caller’s instinct is to compute κ(A), and the measurement says exactly how much that is worth.

As an upper bound it is correct. κ(AQ₂) ≤ κ(A), so an answer expected to κ(A)·u is never disappointed. On the first of the two problems above that bound predicts 10⁻⁴ and the answer is 10⁻¹⁶, which is a bound loose by twelve orders and is still a bound.

As a prediction it is worthless on a constrained problem — the same failure the units the matrix is measured in finds for a scaling, where a condition number reports the description rather than the problem —, and the two curves are how worthless. The usual defence — a bound is loose but at least it orders problems correctly — does not survive either: the two problems here have identical κ(A) and cannot be ordered by it at all.

And it is the quantity every caller has. κ(AQ₂) requires knowing B, forming the null-space basis and decomposing a product; κ(A) requires A. So the quantity that is easy is the one that does not answer, which is a shape this collection sees constantly and which a condition number scaling cannot move is the standing statement of: there, the part of the difficulty that survives every rescaling is the part that belongs to the problem, and κ(A) reports the description instead.

The same thing said about information #

There is a reading of all this that is not about arithmetic and it is worth having, because it explains why the effect is as large as it is.

A constraint is data. Bx = d is m exact equations about the answer, and exact data about a direction the fit could not resolve is worth a great deal more than more of the fit’s own rows would be. The weak singular directions of A are precisely the directions the data does not determine; a constraint lying along one of them supplies what the fit could not, and the residual problem has nothing ill-determined left in it.

That is the same accounting influence is decided before the data does for a fit’s rows, where a design has exactly p units of influence to distribute and where they go is settled before a measurement is taken. That is why the improvement is unbounded rather than a factor. It is not that the constraint reduces the error; it is that the constraint answers a different part of the question, and the part it answers is the part that was costing the digits.

The converse is the second curve, and it is the more common situation. A constraint that lies along a direction the fit already resolves well tells the computation something it already knew, leaves the difficulty untouched, and costs a dimension for nothing.

The refusals #

The claim worth breaking is the one a caller acts on before running anything: the accuracy attainable in a constrained fit is governed by κ(A). The assertion that two problems with the same κ(A) have the same attainable accuracy is fed the pair at κ(A) = 10¹² — agreeing to twelve figures, returning 4.73·10⁻¹⁶ and 3.03·10⁻⁴ — and required to fail.

The second refusal covers the over-correction, which is that κ(A) is useless. Fed the same pair, the claim that either answer is worse than κ(A)·u has to fail: the bound holds in both cases and is simply loose in one of them. A quantity that bounds correctly and orders incorrectly is a different thing from a quantity that is wrong, and the difference decides what a caller may do with it.

And the third is a control on the construction, since the whole page depends on the two problems being comparable. Each pair is fed the claim that its two κ(A)s differ, and has to refuse at every point of the sweep — a page whose finding is the same condition number, two answers has to establish the first half to more digits than the second half is being claimed to.

Where the field’s other condition numbers sit #

This collection has a running argument about what a condition number is for, and the constrained case adds a third position to it.

A condition number scaling cannot move is the first: κ(A) can be inflated arbitrarily by a bad choice of units, so part of it belongs to the description and part to the problem, and only the second part is worth acting on. The units the matrix is measured in is the same point from the other end.

A condition number that is not the model’s is the second, in the reduction field: κ(P)κ(Q) is quoted as a measure of how reducible a model is and is not — the quantity is real and it is answering a different question from the one it is being asked.

This page is the third and is unlike both. κ(A) here is not inflated by units, and it is not answering a different question: it is answering the right question about the wrong problem. The problem being solved is A restricted to a subspace, that restriction is what the constraint is, and a condition number computed before the restriction is a condition number of something the computation never touches.

The three failures want three different responses. The first is repaired by equilibration, the second by asking a different question, and this one by computing the quantity that is already in the routine’s hands and throwing it away.

What a caller should do #

Two things, and the first is nearly free.

Ask for κ(AQ₂) rather than κ(A), and take it from the routine that computed the answer rather than from a separate decomposition. A null-space route already has AQ₂ in hand and already factored it; an estimate from the diagonal of its R factor costs nothing and is within a small factor of the truth.

And read a large κ(A) with a small κ(AQ₂) as good news rather than as a contradiction. A fit whose matrix is badly conditioned and whose constrained answer is accurate is not a fluke and does not need explaining away — it is a constraint that happened to be placed where the difficulty was, and the measurement above says how common that is: entirely a matter of where the constraint came from.

A constraint that comes from a conservation law is placed by physics and has no reason to align with anything. One that comes from a calibration is placed by the measurement that was hardest to make, which is often precisely the direction the fit resolves worst — so the helpful case may be the more frequent one in practice, and nothing here measures that.

What is not measured here #

Not the intermediate case. Both problems are extreme: the constraint removes all of the difficulty or none of it. A constraint lying at forty-five degrees to a weak direction removes part of it, and where the error lands between the two curves is a question about the angle rather than about the alignment. It is one sweep and it is not run.

Not the multipliers. The Lagrange multipliers of the constrained problem are large when the constraint is doing a lot of work, which is exactly the case where the conditioning improves — so the multipliers may be a cheaper signal than κ(AQ₂) and they come out of the saddle-point route for free. Whether they order the two problems above correctly is unmeasured.

And not an inexact constraint. Everything here assumes Bx = d holds exactly. A constraint from a measurement does not, and the whole benefit above depends on the constraint being better determined than the fit’s own rows — which is the weighting method’s modelling case, where τ is finite and chosen from what the measurements are worth. At a finite τ the improvement must be partial, and how partial is the measurement this page’s construction is one step away from.

Still open: the quantity a routine should return #

The recommendation above asks a routine to return a number it already has, which raises the question of what else it has.

A null-space route holds three objects at the end: R from the constraint’s factorisation, whose diagonal gives κ(B); the R factor of AQ₂, whose diagonal gives κ(AQ₂); and the residual. A caller who received all three could distinguish every failure mode this ladder has measured — a nearly dependent constraint from κ(B), an ill-conditioned residual problem from κ(AQ₂), and a poor fit from the residual — and no interface returns more than the last.

The open question is what the right summary is. Three numbers is more than an interface usually offers and a single scalar cannot carry them, because they fail in different ways and a caller’s response to each is different. Whether there is a useful single quantity — an error estimate combining all three, computed from what is already in hand — or whether the honest answer is three, is a question about what a caller can act on rather than about arithmetic.

One line #

A constraint removes a direction, and whether it removes the one the fit was badly conditioned in decides the answer by twelve orders of magnitude — which κ(A) cannot see, because it is the same in both cases.