Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Rank-revealing QR — where it appears

A QR factorisation whose diagonal is meant to expose a rank, which for the greedy pivot rule is a heuristic and not a guarantee. It is the cheap route to a rank verdict, it agrees with the singular values on almost every matrix, and where it errs it errs in the flattering direction.

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

1234567891010⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1indexsingular valuecutoff, σ₁ · 10⁻¹⁰numerical rank 10gap 8.2·10⁶an opiniontrue rank 410×10, built with 4 nonzero valuesrank is a decision

Rank is a decision

A floating-point matrix does not have a rank. It has a spectrum of singular values, and somewhere in that spectrum is a place where the values stop being signal and start being noise. Deciding where is a judgement, and the evidence for it is a gap.

spectra · rank 171319253137434910⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110²indexmagnitude|r_kk|σ_kone factorisation, two verdicts‖AP − QR‖/‖A‖1.1·10⁻¹⁶|r_nn|8.7·10⁻⁴σ_min3.7·10⁻¹²column interchanges0|r_nn| is never below σ_minso the cheap verdict errs one way only

The cheap rank and what it cannot see

Almost nobody computes singular values to decide a rank. The standard substitute is QR with column pivoting, read off the diagonal of R — and there is a triangular matrix on which the greedy rule makes no interchange at all, has no better column available at any step, and reports a matrix eight orders of magnitude further from singular than it is.

spectra · rank

Named alongside it

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

Column pivotingNumerical rankSingular valuesCondition estimationCondition numberCounterexampleHouseholder reflectionJacobi's eigenvalue methodKahan's matrixLower boundQR factorisationRank deficiency

All concepts