← All Cracked Math projects
PM-I03NOT STARTEDINTERMEDIATEMATHPYTHONIMPACT ★★☆☆☆

Gram-Schmidt vs Householder: watching orthogonality die

Same maths, four algorithms, and on NIST's nastiest regression problems they give anywhere from 0 to 8 correct digits.

EST.10 h
REWARD+300 XP
AFTERNIST Statistical Reference Datasets

ML-ARENA BENCHMARKS

PROOF: BENCH
METRICINDUSTRYMINE
||Q^T Q - I|| vs kappa (how far the computed Q is from orthogonal); log relative error (correct digits) against NIST certified values
GOAL · Householder within 1 digit of LAPACK on all 11 StRD problems. Measured orthogonality-loss slopes match eps*kappa (MGS) and eps*kappa^2 (CGS) within 10x, where eps is machine epsilon. Documented failure of the normal equations on Filip.
NIST StRD certified results; numpy.linalg.lstsq (LAPACK) · measured locally—
no results yet
YOUR RESULTS

Your recorded results appear here.

Brief

QR factorisation writes A = QR, with Q orthogonal (its columns are perpendicular unit vectors) and R upper triangular. It is the stable way to solve least squares. Implement classical and modified Gram-Schmidt (build Q one column at a time by subtracting projections; the modified version subtracts them one at a time, which loses less accuracy). Implement Householder QR with implicit Q (zero out each column below the diagonal with a reflection, and store the reflections instead of Q) and Givens QR (zero out one entry at a time with rotations). Also implement the normal equations (solve A^T A x = A^T b) via Cholesky. Run them on synthetic matrices with kappa from 1e2 to 1e14 (kappa is the condition number: how much the matrix can amplify errors) and on all 11 NIST StRD certified linear-regression problems (reference problems whose answers are certified to many digits), including Filip and Longley. Measure loss of orthogonality and digits of accuracy.

VICTORY CONDITIONS

  1. Householder within 1 digit of LAPACK on all 11 StRD problems. Measured orthogonality-loss slopes match eps*kappa (MGS) and eps*kappa^2 (CGS) within 10x, where eps is machine epsilon. Documented failure of the normal equations on Filip. (||Q^T Q - I|| vs kappa (how far the computed Q is from orthogonal); log relative error (correct digits) against NIST certified values).
  2. A public repository with a README that shows your result and how to reproduce it.

Terms in plain words

QR factorisation
Writing a matrix as an orthogonal matrix Q times an upper-triangular matrix R, which makes least squares easy and stable.
Gram-Schmidt (CGS / MGS)
Building orthogonal vectors by subtracting projections onto earlier ones; classical (CGS) and modified (MGS) differ in order of operations and in how fast orthogonality is lost.
Householder reflection
A mirror-like orthogonal transformation that zeros out all entries of a column below the diagonal in one step.
Normal equations
Solving least squares through A^T A x = A^T b; simple, but it squares the condition number and so loses twice as many digits.
NIST StRD
Statistical Reference Datasets from the US standards institute, with answers certified to high precision for testing software.

Why it rates ★★☆☆☆

Core numerical linear algebra, done rigorously against certified data. It is still a known experiment.