Skip to content

Rank-Revealing QR Factorization

Factorization method — instantiates Independent Generating Set Design

Orthogonalizes a matrix with column pivoting so the most independent, best-conditioned columns are chosen first as the basis and the numerical rank shows up as a break in the diagonal.

Rank-Revealing QR Factorization factors a matrix into an orthogonal part and a triangular part while reordering its columns so the strongest independent columns come first. Its defining move is column pivoting: at each step it grabs the column that is least explained by those already chosen — the one with the largest orthogonal residual — so the leading columns are not merely independent but the most independent available. Two payoffs follow. The chosen columns form a well-conditioned basis of the actual original columns (not abstract combinations of them), and the magnitudes on the triangular diagonal decay, so a sharp drop marks the numerical rank. Where an exact row reduction extracts some independent subset, this one deliberately selects a stable subset and ranks the columns by how much genuinely new information each contributes.

Example

A data scientist has a regression model with roughly forty candidate predictors, several of them near-duplicates: height in centimetres and in inches, a couple of composites that are almost linear blends of others. Ordinary least squares behaves erratically because the design matrix is ill-conditioned — tiny data changes swing the coefficients wildly. Rank-Revealing QR with column pivoting reorders the predictors by how much independent information each adds. The diagonal of the triangular factor drops sharply after about thirty columns, flagging the numerical rank, and the first thirty pivoted predictors form a well-conditioned subset worth keeping.

The near-duplicate features land at the tail, where the diagonal has collapsed toward zero — visibly redundant. Dropping them leaves a stable model built from real, named predictors the analyst can still interpret, not from opaque linear combinations. The factorization both revealed how many independent predictors there really were and chose a good set of them.

How it works

  • Pivot on the largest residual. At each step, select the remaining column whose component orthogonal to the already-chosen columns is largest, and move it to the front.
  • Orthogonalize and record. Apply an orthogonal transformation (typically Householder) to peel that column off, accumulating the orthogonal and triangular factors.
  • Read rank from the diagonal. The pivot order ranks columns by independent contribution; a sharp fall in the triangular diagonal magnitudes locates the numerical rank.

What distinguishes it is selection for conditioning: the pivot rule optimizes the kept subset's stability, not just its independence.

Tuning parameters

  • Pivoting rule — classic largest-residual (Businger–Golub) column pivoting versus "strong" rank-revealing variants that guard against rare failure cases; robustness against cost.
  • Rank cutoff on the diagonal — where you declare the drop; sets how many columns to keep, trading completeness against conditioning.
  • Column scaling — how columns are normalized before pivoting; unequal scales bias which columns look "largest" and can distort the selection.
  • Underlying orthogonalizer — Householder, Givens, or modified Gram–Schmidt; stability versus structure-exploitation.
  • Update vs. recompute — incrementally adding or removing a column versus a full refactorization when the matrix changes.

When it helps, and when it misleads

Its strength is a concrete, well-conditioned subset of the original columns — interpretable in a way the singular value decomposition's abstract directions are not — ranked by importance and delivered together with the numerical rank. For subset selection and stable least squares it is often the tool of choice.

It misleads because column pivoting is a greedy heuristic. It reveals the rank in nearly every practical case, but contrived matrices exist on which no single pivot exposes the deficiency, which is why "strong" variants were developed.[1] And when the diagonal decays smoothly instead of gapping, the rank cutoff is a judgment call, not a fact. The classic misuse is reading a gentle diagonal decay as a clean rank and truncating anyway. The discipline is to treat an ambiguous gap as ambiguous and confirm with the definitive singular-value spectrum — Singular-Value Rank Diagnosis — before committing to a rank.

How it implements the components

Rank-Revealing QR fills the select-a-stable-subset side of the archetype:

  • minimality_and_pruning_rule — column pivoting keeps a minimal independent set of the strongest columns and prunes the rest as redundant.
  • basis_selection_decision_rule — the pivot order is a selection rule: it decides which original columns become the basis, ranked by independent contribution.
  • conditioning_and_stability_envelope — pivoting for the largest residual keeps the selected basis well-conditioned, bounding how much it amplifies coefficient error.

It does not return the exact dependency relations among columns — Pivoted Row Reduction does — nor give the definitive singular-value spectrum and rank tolerance (Singular-Value Rank Diagnosis), nor orthonormalize a pre-chosen independent set (Gram–Schmidt Orthonormalization).

Notes

Rank-Revealing QR sits between its two neighbours. Pivoted Row Reduction extracts an exact basis but says nothing about conditioning; the singular value decomposition gives the definitive rank but in abstract directions that are not any of your original columns. RRQR keeps original, interpretable columns while being far more numerically stable than row reduction — the middle path when you need real columns and a stable basis.

References

[1] Column-pivoted QR (the Businger–Golub algorithm) reveals numerical rank in almost all practical cases but is a greedy heuristic. Contrived matrices — the Kahan matrix is the textbook example — exist on which it fails to expose rank deficiency, which is why "strong" rank-revealing QR variants were developed. ↩