Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

Rank — the series

4 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    part 2 · spectra
  2. 81930415263110²10⁴10⁶10⁸10¹⁰10¹²size of the matrix|rₙₙ| ÷ σₘᵢₙthe two agreec = 0.2c = 0.35c = 0.5no ceilingratio at n = 1021ratio at n = 646.8·10¹⁰interchanges, anywhere0the greedy rule never had a choiceand the gap grows with every row

    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.

    part 3 · spectra
  3. 13579111310⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹index ksingular valueσ₁ · 10⁻¹⁴, the thresholdone matrix, three rankspartitionings7lowest rank10highest rank12threshold7.3·10⁻¹⁴σ₁7.3the curves separate in the noiseand the threshold is drawn through it

    A rank that depends on the thread count

    One 60 × 14 matrix, one threshold, seven partitionings of the inner products that build its Gram matrix — and numerical ranks of 12, 12, 12, 10, 10, 11 and 11. Not a digit of an answer: the number of columns a model built from this matrix would have.

    part 4 · machine
  4. 1611162126313610⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹10¹indexmagnitude|rₖₖ|σₖone factorisation, two verdicts‖AP − QR‖/‖A‖10⁻¹⁵|rₙₙ|1.1·10⁻¹²σₘᵢₙ10·10⁻¹³column interchanges33|rₙₙ| is never below σₘᵢₙso the cheap verdict errs one way only

    A good curve and a bad verdict

    The diagonal of a column-pivoted R is famous for the one matrix it is wrong about. On that matrix it is right about thirty-nine of its forty entries — every |rₖₖ| within a factor of six of the σₖ it stands for — and wrong by 4·10⁶ at the fortieth, which is the only one a rank verdict ever reads.

    part 5 · spectra

All series