Notebook 12: matrix factorizations, and what each one costs

[project-delphi]

Blocked on #53. A notebook that is not a section cannot be committed until
extras: exists — check_links.py rejects it and gen_notebooks.py cannot
build its header.

The workshop teaches factorizations in passing — LU and QR in section 01, the
pseudoinverse in 07, convolution-as-a-matrix-product in 09 — but never answers
the two questions a practitioner actually has:

Which factorization do I reach for on this data, and what does it cost me?

Notebook 11's take-home A is a single PCA exercise. That is a gesture at the
first question and silence on the second. This is the notebook that answers both
properly, as take-home material outside the 195-minute clock.

The source is the blog's August 2026 linear-algebra arc, which already has the
derived complexities and the quantified results:

• Matrix Factorizations as Optimization Problems: QR, SVD, Eigendecomposition, NMF, and Cholesky
• The Matrix That Rotates, Stretches, and Rotates Again
• The Directions a Matrix Refuses to Turn

notebooks/12-matrix-factorizations.ipynb

House shape throughout: generated header/Setup/footer from #53, hand-written
teaching body, a # TODO cell followed by a folded solution-tagged cell per
exercise, and a 🇪🇸 line under each heading.

1. Five factorizations, five questions. LU and Cholesky → repeated solves;
   QR → least squares; eigendecomposition → repeated application and spectra;
   SVD → optimal rank-k; NMF → parts you can name. Framed as constrained
   optimization, following the first blog post.
2. The cost table, derived. Cholesky at O(n³/3) then O(n²) per solve, so
   O(n³ + mn²) for m right-hand sides. QR least squares against the normal
   equations, where κ(XᵀX) = κ(X)² turns κ(X)ε error into κ(X)²ε. Full SVD
   at O(mn·min(m,n)) against Lanczos at O(k·nnz(A)) and randomized at
   O(mnk).
3. The cost table, measured. Time each factorization across a size sweep,
   fit log t against log n, and plot the fitted exponent beside the
   predicted one. Big-O as a slope the reader produced, not a claim they are
   asked to accept.
4. Widget — method chooser. Toggle data properties (tall or square,
   symmetric, positive-definite, sparse, nonnegative, interpretability needed,
   many right-hand sides) and read back the factorization that fits, why, and
   what it costs. The decision procedure, made interactive.
5. Conditioning, on real data. Normal equations against QR, side by side.
   The blog uses NIST StRD Filip (κ ≈ 1.8e15); substitute a degree-10
   Vandermonde built from a column the workshop already fetches — the airline
   passengers series from section 08, or California housing from 07. A
   high-degree polynomial fit on real x reaches the same brutal condition
   number with no new download.
6. Widget — rank slider on an image. camera() / astronaut(), already
   workshop datasets: rank against relative error, stored numbers k(m+n+1)
   against mn, and dB. Reference points from the blog to land near: rank 16 →
   21.2 dB at 12.5% of raw bytes, rank 50 → 27.5 dB at 39%.
7. Widget — downstream task. Rank moving a real metric, not reconstruction
   error. Primary, and fully offline: truncate load_digits (1797×64) to
   rank k, train a cheap classifier on the rank-k features, and plot accuracy
   against k — the elbow where accuracy saturates far below full rank is the
   whole point. Pair it with NMF on the same digits for the parts-based reading,
   where components come out as stroke fragments you can look at.
   One sanctioned alternative if the recommender framing is wanted instead:
   MovieLens 100k held-out RMSE against rank (943×1682, 5.7% observed — the
   blog's own experiment), SHA-256 pinned like fetch_verified_video. Pick one;
   do not do both.
8. Budget widget. Set m, n, k; read back predicted flops, bytes
   stored, compression ratio and a rough wall-clock estimate for each method —
   big-O turned into a sizing tool for the reader's own data.

Exercises (3–4, each a # TODO cell plus a folded solution): rebuild least
squares two ways and compare residuals against np.linalg.lstsq; find the rank
at which an image crosses a chosen dB threshold; verify the fitted exponent for
one method against its predicted one.

Data

Reuse what the workshop already loads — camera()/astronaut(),
load_digits, breast cancer, California housing, the airline series. Any new
remote dataset needs a reason nothing on hand can serve, and is SHA-256 pinned
the way fetch_verified_video and fetch_verified_wav already are. MovieLens
is the only candidate, and only if it replaces the digits widget rather than
adding to it.

Handbook

Add Appendix E — Matrix Factorizations: Which One, and What It Costs, in the
established appendix voice: a short framing paragraph, the cost table, and
numbered # TODO blocks mirroring the notebook's exercises, with a Colab link.

Two knock-on edits:

• Appendix D (Cholesky) is a one-exercise version of material this appendix
  covers properly — shrink it to a pointer.
• Appendix E is currently Facilitator Notes and should stay last, so it is
  relabelled Appendix G. (Issue for notebook 13 takes F.)

This also satisfies check_links.py check 3 for the new notebook — every
notebook must be linked from at least one rendered page, and the handbook is in
_quarto.yml's render: list — so no special case is needed.

Gaps

The blog does not cover LU as its own topic, CUR at all, or randomized SVD
beyond a single complexity line. Write those from scratch or cut them; do not
imply a source that is not there.

Housekeeping

• Body cells are edited directly in the .ipynb; only Setup code goes in
  scripts/content.py.
• Rerun gen_tables.py and gen_notebooks.py, then check_links.py.
• quarto render (1.6.40) and commit docs/.
• Run the notebook top to bottom on a cold Colab runtime — the widgets and the
  timing sweeps are exactly what a static check cannot see.