Condition squaring — where it appears
Named by 17 essays across 7 fields — each of them below, with the objects they name alongside it.
The road that squares the problem
The normal equations are the first method every course teaches and the method no library uses. Forming AᵀA squares the condition number, and below ε = √u it does not degrade — it produces a matrix that is exactly singular, from data that was perfectly usable.
An iteration that walks out of the set
Every sweep of alternating least squares is the exact minimiser of its own subproblem, so the objective can only fall. What it cannot do is converge, when the target's nearest rank-r point is not in the rank-r set — and a plateau at a small residual looks identical to slow convergence unless the size of the terms is plotted beside it.
A matrix that is definite on one machine
Two hundred Gram matrices, two conforming builds, and twenty-six of them get different answers to "is this positive definite". The exact verdict, from determinants in BigInt rationals, says the fused build is right nine times and the other one seventeen.
The right-hand side as one more column
Modified Gram–Schmidt's Q is 4.3·10⁻⁹ from orthogonal at κ = 10⁸, and a least-squares solve that multiplies b by it is wrong by 0.13. Hand the same routine b as an extra column instead and the answer is right to 2.7·10⁻¹⁰ — closer than Householder's 4.0·10⁻⁹. Classical Gram–Schmidt gains nothing from the same trick, to the last bit.
The repair the drift did not need
A sliding window's carried Cholesky factor drifts 3.9·10⁻¹⁴ from its data, and multiplying by κ(AᵀA) predicts eight lost digits in the coefficients, a stream conditioned at 10¹² losing the answer, and a periodic refresh of the factor as the default repair. Measured against coefficients computed exactly in rationals, all three come out differently. On a stream made ill-conditioned by scaling, the conditioning never reaches the coefficients. On a collinear stream, a freshly recomputed factor is as wrong as the drifted one. And one correction from the window's own rows reaches Householder's accuracy for a fraction of a refresh's cost.
A tensor that cannot be decomposed
Every member of a certain sequence is exactly a sum of two rank-one terms, and both terms are written down in closed form. A three-hundred-sweep fit from a random start does not find them, and stalls at the same one per cent however far the sequence goes — while a fit started at the answer loses digits exactly as 2n² says it should.
A rank that depends on the thread count
One 60 × 14 matrix, one threshold, seven partitionings of the inner products that build its Gram matrix — and numerical ranks of 12, 12, 12, 10, 10, 11 and 11. Not a digit of an answer: the number of columns a model built from this matrix would have.
The repair that costs exactly itself
A ridge on every subproblem is the standard cure for a swamp and it works — the terms stop at 1.61 instead of climbing past 6.7, and a run that never finished finishes in 798 sweeps. On a tensor that does have an answer the error it costs is the ridge itself, to within a factor of two, at every setting from 10⁻¹⁰ to 10⁻¹. And the terms it returns are still the right terms.
The test that is a deadline
The quantity that separates a boundary from slow convergence fires on every run that has nothing to reach, at sweep 21 of four thousand, and on no ordinary fit. It also fires on every badly conditioned fit that does converge — at sweep 758. No threshold between 0.10 and 0.40 separates those two, and the sweep it fires at separates them by a factor of thirty-six.
The reference was a method
The optimality conditions of a constrained fit contain AᵀA, so solving them is the road that squares the problem wearing a block structure. At κ(A) = 10¹¹ the route that never forms a cross-product returns 1.89·10⁻⁹ and the route that does returns 4.64·10⁻⁴ — and forming AᵀA and then solving it in exact rationals returns 3.45·10⁻⁴, so nearly all of the loss happens before any elimination begins.
The answer the last window left
A sliding window that corrects its least-squares answer at every step could start each correction from the previous step's corrected answer instead of from a fresh solve: the two windows share all but one row. On a stream with any noise in it, that start is three orders worse. The window's exact answer moves by 0.79 of itself in one step at κ(A) = 3·10⁶, a fresh seminormal solve is wrong by only 1.8·10⁻⁴, and one correction contracts either start by the same factor — so the fresh start ends at 2.2·10⁻⁸ and the carried one at 3.7·10⁻⁵. Only on data that agree exactly does carrying win.
The residual the appended block cannot remove
Appending b as one more block made block modified Gram–Schmidt solve least squares as well as Householder, ten million times better than the same Q through Qᵀb at κ = 10⁸ — on problems with no residual. Give b a component outside the range and every stable route's error rises with it, while Qᵀb's, already at κ²u, does not move. The appended block's advantage then falls as one over the residual: 5,400 at a relative residual of 10⁻⁴, 54 at a per cent, none at one. It never falls behind Householder by more than a factor of four. What the residual decides is whether the extra block is worth its synchronisations, and the answer is yes up to a residual of about a per cent.
The step the two rows owe
A sliding least-squares window can start each step's correction from a fresh solve or from the answer it already has. The answer it has is three orders worse on noisy data, because the exact answer moves by most of itself in a step. The proposal was a start that moves too: the previous answer plus the change the entering and leaving rows imply, two triangular solves from the factor the window keeps. Its start lands exactly where one correction of the carried answer lands — the update is that correction, computed from two rows instead of twenty-four — and one correction after it ends 2.9 to 440 times below the fresh start at κ(A) = 3·10⁶, and level with the carried answer when the data agree exactly.
The worst residual belongs to the route
Every stable least-squares route's error rises with the residual at about a fiftieth of the bound κ²uρ, and the question left open was whether a residual aimed at the weak directions closes the gap. It can be aimed exactly: the map from residual to error is, on these problems, one direction and rounding. Aimed, Householder's constant rises from a median of 0.014 to 0.11 — √(m − n) = 6.9 times a typical direction, at 32, 64 and 128 rows to three figures — and stops a factor of nine short of the bound. The direction is each route's own: aimed at one, another route draws a fifth of its worst. And aimed at the appended block, the one-per-cent rule that made it worth its extra block falls to half a per cent, with the block twelve times behind Householder on the same data.
A tree leaks along its leaves
A stable least-squares route's error, for a fixed factorisation, is a linear map from the residual with one dominant direction, and each route leaks along its own. A tree of Householder factorisations — the shape a distributed code factorises in — was expected to have a direction of its own too, with b appended at every leaf inheriting Householder's accuracy there. Measured at κ = 10⁸ on two placements of the ill-conditioning, a tree's map has one direction like every route's, and its aimed constant is of Householder's order: within a fifth of it when the ill-conditioning is spread, two to three times it when it sits between column blocks. Its direction is its own — at a cosine of 0.40 to 0.58 from the sequential route's, 0.13 to 0.18 between blocks — and the split of the rows decides it. Appending b at the leaves changes nothing: the same constant to five figures, the same direction to ten.
Small compared to what
This site's own singular value routine has carried a sentence since the month it was written — that one-sided Jacobi computes the small singular values to high relative accuracy and the standard method does not. It has never been measured here, because measuring it needs a σ that is known rather than computed. A bidiagonal matrix and a Sturm count in exact rationals supply one.
A threshold the matrix does not set
Two numbers come out of a relative-accuracy comparison and they belong to different things. The size of the matrix moves the constant of the routes that never fail, by a factor of 2.7 between n = 4 and n = 10; it does not move the point where the route through BᵀB stops returning an answer, which sits between ten and eleven decades of grading at every size drawn.
Named alongside it
The objects these essays reach for when they reach for this one.
Exact ground truthBackward errorLeast-squaresNormal equationsAlternating least-squaresBorder-rankCholesky factorisationCP decompositionHouseholder reflectionIll-posed problemCondition numberExact arithmetic