Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Householder — where it appears

A reflection that maps a vector onto a multiple of a coordinate axis, used to introduce zeros into a matrix a whole column at a time. It is orthogonal to the rounding level whatever the matrix, which is what makes a factorisation built from a sequence of them backward stable.

Named by 4 essays across 2 fields — each of them below, with the objects they name alongside it.

how far is it from A to an orthogonal matrix?smaller is nearer · the polar factor minimises this in every unitarily invariant normpolar factor U1.8554QR, signs fixed2.1265QR as returned3.8226200 drawn at randomκ = 10polar factor1.9QR, signs fixed2.1QR as returned3.8best of 200 random2.7‖A − QR‖ is the same either wayand ‖A − Q‖ is not

The nearest orthogonal matrix

Every field that has to clean up a drifted rotation reaches for QR, and QR does not answer the question. The nearest orthogonal matrix is the orthogonal factor of the polar decomposition — nearer by about a tenth, and, more to the point, the same matrix whatever order the columns were written in. QR's answer changes completely.

orthogonality · Polar decomposition 0246810121410⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹10⁴10⁷10¹⁰log₁₀ τ — the weight on the constraintrelative error against the exact answerτ = 1/√uGram–Schmidtnormal equationsHouseholder QRthe ceiling is the method'sHouseholder, τ = 10¹⁴4.8·10⁻¹⁵normal equations14Gram–Schmidt4.9·10¹⁰1/√u6.7·10⁷a constraint is a weight at infinityand the solver decides how far infinity is

A constraint is a weight at infinity

Stack an equality constraint on top of a least-squares problem with a large weight and the answer approaches the constrained one like 1/τ². The limit is takeable to any accuracy — and how far it can be taken is a property of the solver, not of the problem. One of them stops at the square root of the precision, and one of them does not stop.

leastsquares · Constrained least-squares polar: U₁P − U₂QR: Q₁P − Q₂-3.3·10⁻¹⁶-3.3·10⁻¹⁶2.2·10⁻¹⁶-1.9·10⁻¹⁶5.6·10⁻¹⁷-1.7·10⁻¹⁶6.7·10⁻¹⁶-8.9·10⁻¹⁶2.8·10⁻¹⁶-5.6·10⁻¹⁶-3.6·10⁻¹⁶6.1·10⁻¹⁶-8.3·10⁻¹⁶8.3·10⁻¹⁶-7.2·10⁻¹⁶-10·10⁻¹⁶2.2·10⁻¹⁶4.4·10⁻¹⁶1.7·10⁻¹⁶-4.4·10⁻¹⁶-5.6·10⁻¹⁷5.6·10⁻¹⁷0-7.2·10⁻¹⁶-4.4·10⁻¹⁶3.9·10⁻¹⁶5.6·10⁻¹⁷2.8·10⁻¹⁶-1.1·10⁻¹⁶-3.3·10⁻¹⁶2.2·10⁻¹⁶1.1·10⁻¹⁶-2.8·10⁻¹⁶5.6·10⁻¹⁶-2.8·10⁻¹⁶5.6·10⁻¹⁶0.67-0.35-0.23-0.620.19-0.72-0.770.170.20.290.190.93-0.180.55-0.0290.06-0.460.11-0.17-0.61-0.230.38-0.55-0.380.750.870.661.1-0.36-0.530.42-0.670.180.180.52-0.3Frobenius norms, columns reordered‖U₁P − U₂‖2.8·10⁻¹⁵‖Q₁P − Q₂‖3‖Q‖, for scale2.4κ of the matrix100Frobenius distance between the two answers, on one scale0 to 4polar2.8·10⁻¹⁵QR3.048‖Q‖ = 2.449the column space did not moveand one of the two answers did

A test with no answer in it

A caller with no reference answer can still ask whether a routine answered the right question: reverse the columns, run it again, compare. The polar factor's two answers agree to 10⁻¹⁵ at every conditioning drawn; a QR's differ by 2.353 on matrices whose own norm is 2.449. The test has a floor, and the floor is measurable too.

orthogonality · Polar decomposition median departureone reflector at a time, formed7.5·10⁻¹⁵one reflector at a time, applied3.4·10⁻¹⁵blocks of 64, applied3.7·10⁻¹⁵10⁻¹⁵10⁻¹⁴block sizedeparture from orthogonality12481632642·10⁻¹⁵4·10⁻¹⁵6·10⁻¹⁵8·10⁻¹⁵Q formedapplied through the blocksopen dots: each of the five seedsblocking helps the formed matrix and not the operator

The factor nobody forms

A blocked Householder factorisation's orthogonal factor, multiplied out, departs from orthogonality half as far in blocks of sixteen as one reflector at a time, and that was read as blocking buying a factor of two. Libraries do not multiply it out. Applied to vectors through its stored blocks — which is how every caller uses it — the same factor departs by 3.1 to 4.0·10⁻¹⁵ at every block size from one to sixty-four, and stops growing after about twenty reflectors instead of adding them up. The factor of two was the price of forming the product, and a factor that is never formed never pays it.

orthogonality · Householder

Named alongside it

The objects these essays reach for when they reach for this one.

OrthogonalityQR factorisationCondition numberGram–SchmidtInvariancePolar decompositionBlocked algorithmEquality-constrained least-squaresExact ground truthFrobenius normHouseholder reflectionLeast-squares

All concepts