Linear algebra in practice: factorisations and conditioning

Solving a linear system is the inner loop of regression, portfolio optimisation and risk. The mathematics says the answer is $A^{-1}b$ ; the numerics says never to compute that, and the difference between the two is where precision is lost on real, nearly-collinear financial data.

Matrix	Use	Cost
General square	LU with partial pivoting	$\tfrac{2}{3}n^3$
Symmetric positive definite	Cholesky	$\tfrac{1}{3}n^3$ — half of LU
Rectangular, least squares	QR	$2mn^2$
Rank-deficient or ill-conditioned	SVD	$O(mn^2)$ , most expensive and most robust
Large and sparse	Iterative (CG, GMRES)	Per iteration, times the iterations

Table 4.1 · Which factorisation. Cholesky is the one to reach for on a covariance matrix: it is twice as fast as LU, needs no pivoting, and its failure is a *feature* — if it breaks down, the matrix was not positive definite and you have learned something.

Equation 4.2

The condition number

How much a relative error in the input can be amplified in the output. A condition number of $10^k$ means losing about $k$ digits of precision.

\kappa(A) = \|A\|\,\|A^{-1}\| = \frac{\sigma_{\max}}{\sigma_{\min}}

$\sigma$: Singular values. The ratio of the largest to the smallest is the condition number.
$\kappa = 10^{16}$: All sixteen digits of a double are gone; the answer is noise.

Figure 4.3 · Why nobody forms $A^{\top}A$ . Forming the normal equations squares the condition number, which costs you half your digits before any arithmetic happens. In double precision that takes a well-behaved problem to the edge of nonsense — and it is why every serious least-squares routine goes through QR instead.

Why the normal equations lose twice as much. The condition number of $X^\top X$ is the *square* of that of $X$ . So a design matrix with $\kappa = 10^6$ — awkward but workable, losing six digits — becomes $10^{12}$ once you form the product, which leaves four digits of a double. QR works on $X$ directly and never forms the product, so it loses six digits rather than twelve. On well-conditioned data both approaches agree; on collinear data, which is when you most need the answer, the normal equations can return coefficients that are simply wrong, and nothing in the output says so.

Example 4.4

A design matrix has condition number $10^{7}$ . How many digits survive solving by QR, and by the normal equations?

Show the worked solutionHide the worked solution

Worked solution

Formula $\text{digits lost} \approx \log_{10}\kappa$
Substitute $\text{double precision} \approx 16 \text{ digits}$
Solve $\text{QR: } \kappa = 10^{7} \Rightarrow 16 - 7 = 9 \text{ digits}$
$\text{normal equations: } \kappa^2 = 10^{14} \Rightarrow 16 - 14 = 2 \text{ digits}$
Answer $9 \text{ against } 2$

Sanity check. Two significant digits on a regression coefficient is not a rounding issue, it is the difference between a usable estimate and a meaningless one. And a condition number of $10^7$ is entirely ordinary for a factor library with correlated features.

Linear algebra in practice: factorisations and conditioning

After this lesson you should be able to

The condition number

The rest of this lesson is in Premium