Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Polar decomposition — where it appears

Writing a matrix as an orthogonal factor times a symmetric positive semidefinite one — a rotation after a stretch along orthogonal axes. Its orthogonal factor is the nearest orthogonal matrix in every unitarily invariant norm, which the Q of a QR factorisation is not.

Named by 6 essays across one field — 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 159131721252910⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹steprelative error in the orthogonal factorNewtonNewton, scaledNewton–Schulzone fixed point, three costsscaled Newton, steps7Newton–Schulz, steps28Newton at step 657scaled Newton at step 64.4·10⁻¹³a Newton step needs an inverseand a Schulz step needs two products

An iteration that only multiplies

Newton's iteration for the polar factor needs an inverse every step. Newton–Schulz needs only matrix products — nothing that reads an entry, nothing that pivots — and it converges if and only if every singular value is below √3. At 1.73205 it converges and at 1.73206 it returns an orthogonal matrix that is not the answer, with a residual of 5·10⁻¹⁶ and nothing to say so.

orthogonality · Polar decomposition 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 110¹10²01020304050noise ÷ thicknesstrials mirrored, %a coin: 50%t = 10⁻²t = 10⁻³t = 10⁻⁴per cent mirroredσ/t = 3, mean of three7.7σ/t = 10, mean of three34σ/t = 100, mean of three4720 points, 400 trials a stop, one seed per thicknessthe ratio decides, not the thinness

A rotation that comes back mirrored

Align twenty noisy points and the nearest orthogonal matrix to the answer is a reflection in 7.7 per cent of trials at noise three times the set's thickness and a third of them at ten — at thicknesses of 10⁻², 10⁻³ and 10⁻⁴ alike. The determinant fix is never a small correction. It moves the answer by exactly 2, it costs exactly 4σ₃ of residual, and it leaves the rotation's error at half the noise however thin the set becomes.

orthogonality · Polar decomposition 10⁻¹101020304050z, the effective noise over thicknesstrials mirrored, %5 points, equal20 points, equal80 points, equal● five precise, 1/σ²■ five weighted ×100per cent mirrored at z = 0.45, 1,000 trialstwenty points1.8eighty points1.3five points9.5five precise, weighted 1/σ²7.9equal noise, five weighted ×1006.8both weighted schemes have five effective pointstwenty and eighty points share one curve

Five precise points are five points

Weighting each sighting by its reliability is the standard form of an attitude or registration fit, and it changes how often the nearest orthogonal matrix comes back as a mirror. Measured, the rate is a function of two numbers: the weighted noise over thickness, and the effective count (Σw)²/Σw². Five points with a tenth of the noise, weighted by 1/σ², carry the information of 515 equal points and mirror like five — 7.9 per cent at a noise ratio where twenty points mirror 1.8 and five mirror 9.5. The √m the earlier measurement left unchecked is right, and it counts what carries the thin direction.

orthogonality · Polar decomposition 0123401020304050z, the effective noise ratiotrials mirrored, %1 thin: 1 × 1 model2 thin: 2 × 2 model3 thin: 3 × 3 modelper cent mirrored at z = 0.7, 600 trialsn = 3, 1 thin, 20 points9.7n = 5, 1 thin, 20 points13n = 10, 1 thin, 40 points12n = 5, 2 thin, 20 points23n = 10, 2 thin, 40 points24n = 8, 3 thin, 40 points32points: measured in n dimensionslines: a k × k determinant, no n in it

A mirror decided in the thin directions

In n dimensions the nearest orthogonal matrix to a noisy alignment is still sometimes a reflection, and the rate at which it is does not depend on n. Three, five and ten dimensions with one thin direction mirror alike; two thin directions mirror like each other in five dimensions and in ten. The rate is the chance that a k × k matrix built from the k thin directions has a negative determinant — 21.7 per cent at a noise ratio of 0.7 for k = 2, measured at 23.0 — and it is well above k independent coin flips. With two or more thin directions the determinant correction still fires, and it no longer rescues the rotation: the answer is eleven noise-widths off whether or not it was mirrored.

orthogonality · Polar decomposition

Named alongside it

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

OrthogonalityRotationSingular value decompositionCondition numberDeterminantFrobenius normGram–SchmidtHouseholderInvarianceQR factorisationReflectionSensitivity

All concepts