Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Frobenius norm — where it appears

The square root of the sum of squares of a matrix's entries, in which the nearest circulant to a given matrix is an average of its diagonals. It is cheap, it is the norm several approximation theorems are stated in, and it cannot see where in the spectrum a perturbation landed — which is a defect the sequence field measures.

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

12345678910⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1rank k of the approximation‖A − Aₖ‖measured, 2-normσₖ₊₁, from theorymeasured, Frobeniusthe first two agreeto 4.3·10⁻⁹worst |‖A−Aₖ‖₂ − σₖ₊₁| / σₖ₊₁4.3·10⁻⁹worst Frobenius discrepancy4.3·10⁻⁹κ = 10⁹; 30 random rank-3 matrices, none closerthe error is σₖ₊₁

The best approximation there is

The error of the best rank-k approximation is not bounded by the next singular value. It is equal to it. That is an unusually sharp theorem, and it makes the theorem itself usable as an independent check on the computation.

spectra · SVD 10²110¹10²size niterations to 10⁻¹⁰λₘᵢₙ(C) changes signno preconditionerStrang's circulantthe preconditioner's own spectrumλₘᵢₙ(C) at n = 16-0.4λₘᵢₙ(C) at n = 32-0.14λₘᵢₙ(C) at n = 640.016λₘᵢₙ(C) at n = 1280.051λₘᵢₙ(C) at n = 2560.053left of the line the repair costs stepsright of it, the count stops counting n

The circulant that cannot be indefinite

The previous essay found a preconditioner taking 117 steps against an unpreconditioned 59, because its smallest eigenvalue was −0.173. Average the two diagonals instead of choosing between them and the count is 7, 8, 9, 10, 10 across a factor of sixteen in size.

structure · Toeplitz 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²02040size niterationsno preconditionerwrapped (Strang)averaged (T. Chan)both are circulant approximations‖C − T‖/‖T‖, averaged0.22‖C − T‖/‖T‖, wrapped0.23smallest eigenvalue, wrapped, n = 160.23one of them is positive definiteand it is the one that is nearer

A speedup with a ceiling of its own

At ρ = 0.5 the averaged circulant takes 5 conjugate gradient steps at n = 512 against an unpreconditioned 30 — and that 30 is where the unpreconditioned count stops. It reads 29, 28, 30, 30 at n = 64 to 512 and then 29, 28, 26, 27, 25 at every doubling out to 16,384, because κ has reached 99.9% of Szegő's limit and the count has nothing left to grow with.

structure · Preconditioning 10¹10²10⁻⁴10⁻³10⁻²10⁻¹1products with Arelative errorHutchinsonHutch++measured at equal costfitted rate, Hutchinson-0.5fitted rate, Hutch++-1.7error at 96, Hutchinson0.017error at 96, Hutch++0.0022both axes count products with Aso the sketch is paid for in the picture

A rate that belongs to the matrix

Hutchinson's fitted exponent sits near a half on every spectrum measured. Hutch++'s runs from −7.15 to −0.67 across the same four budgets, decided entirely by how fast the singular values fall — so one of the two methods has a convergence rate and the other has a rate per matrix. The ±1 probe's advantage moves the same way, from 1.56× at n = 10 to 1.09× at n = 120.

randomised · Trace estimation 051015202530354010⁻⁴10⁻³10⁻²10⁻¹110¹rank of the basiserror, and what the rule readsprobe × 7.98largest probetrue error, Frobeniustrue error, spectralσₖ₊₁, the floorgeometric 0.8, one run, ten probesoptimal rank for ε = 0.111basis reaches ε at rank15probe below ε at rank20published estimate below ε at rank34ε = 0.1the dotted line across is ε = 0.1each rule stops where its curve crosses it

The rank a certificate charges

A randomised range finder can choose its own rank: grow the basis a column at a time and stop when ten fresh probes all come back short. With the published safety factor it never stopped early in any draw measured, and on a matrix whose singular values fall by 0.8 a step it stopped at rank 30 for a tolerance the best rank-11 approximation already meets. The nineteen extra columns are three separate prices — four for building the basis from random vectors, five because a probe reads more than the spectral norm, and ten for the constant — and the spectrum decides which of them dominates.

randomised · Randomised 11.31.610⁻¹110¹10²10³log₁₀ ntropical root ÷ actual modulusexactsmallest moduluslargest modulusthree norms, two endslarge root, n = 40.96large root, n = 320.94small root, n = 45.4small root, n = 32230a maximum predicts a maximumand says nothing about a minimum

An estimate that does not move

The tropical roots are said to miss the bottom of a spectrum by a factor growing like n². The estimate does not get worse. It changes by four per cent between four masses and sixty-four while the modulus it names falls by a factor of a hundred and sixty, and an estimate that is constant in the variable the answer depends on is a different defect from an inaccurate one.

polynomial · Polynomial scaling

Named alongside it

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

Condition numberOrthogonalitySingular value decompositionSingular valuesAsymptotic analysisCirculant preconditionerClustered spectrumConjugate gradientsExact ground truthLow-rank approximationPolar decompositionPreconditioning

All concepts