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.

Named by 2 essays across 2 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²020406080100120140160size niterationsno preconditionerwrapped (Strang)averaged (T. Chan)both are circulant approximations‖C − T‖/‖T‖, averaged0.13‖C − T‖/‖T‖, wrapped0.25smallest eigenvalue, wrapped, n = 16-0.65one of them is positive definiteand it is the one that is nearer

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

Named alongside it

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

Circulant matrixCirculant preconditionerClustered spectrumConjugate gradientsDiscrete fourier transformEckart–YoungGram matrixJacobi's eigenvalue methodLow-rank approximationOrthogonalityPositive definitePreconditioning

All concepts