Solving Ax = b: LU, QR, Cholesky and the Pseudoinverse
Why shouldn't you invert a matrix to solve Ax = b, and what is the pseudoinverse?
The situation
A teammate's regression code computes the inverse of XᵀX directly. It's slow, and with correlated features the weights come out badly wrong. Some of your problems also have more unknowns than equations. The interviewer asks:
Why shouldn't you invert a matrix to solve Ax = b, and what is the pseudoinverse?
The idea
Think of finding a word's page. You could copy out the whole dictionary into a lookup table, just to look up one word. Or you could sort things into easy steps and go straight to it. Inverting builds the table. Factoring does the easy steps.
Play
Try to break it. Slide ε down to 0.000001, and change b by a tiny amount.
Nudge a nearly singular system
Well behaved against unstableSolves A = [[1, 1], [1, 1 + ε]] with b = (2, 2 + ε), whose exact solution is (1, 1), then adds your change to b's second value. Exact arithmetic, using the formula directly. Digits lost is the rule of thumb log₁₀(κ).
Slide ε down to 0.000001. The two equations are nearly the same, so a tiny change in b sends the solution far away. The maths is correct: the problem itself is unstable. Better methods won't rescue an unstable problem, but regularisation changes the question to one that's stable.
Now say why: why can't a better algorithm fix a badly conditioned problem?
Maths
In one breath
Don't compute A⁻¹ to solve Ax = b: it's slower and less accurate than factoring A into easy pieces. Use LU for general square matrices, Cholesky for positive definite ones, QR for least squares and SVD when rank is in doubt. The condition number tells you how much errors get amplified. The pseudoinverse extends the idea to any matrix, giving the least-squares answer with the smallest weights.Factor, then solve
The idea: split A into matrices that are easy to solve, like triangular or orthogonal ones. Triangular systems take only about n² work, by substituting one line at a time.
| Method | Form | Use it for | Approximate cost |
|---|---|---|---|
| LU | A = LU, with row swaps | General square systems. Reuse the factors for many b. | ⅔n³ operations |
| Cholesky | A = LLᵀ | Positive definite: covariance, ridge, Gaussian processes. | ⅓n³, half of LU |
| QR | A = QR | Least squares, when it's well behaved. | About 2mn² |
| SVD | A = UΣVᵀ | Rank-deficient or nearly so. The most robust, and the slowest. | Several times QR |
Why not invert?
- Cost: computing A⁻¹ then multiplying takes about three times the work of an LU solve.
- Accuracy: it generally adds more rounding error.
- Memory: the inverse of a sparse matrix is usually dense, so you can lose all the savings.
Condition number
The condition number κ is the largest singular value divided by the smallest. It's how much a small change in the data can be amplified in the answer. As a rule of thumb, you lose about log₁₀(κ) digits of accuracy.
The normal equations square it: κ(XᵀX) = κ(X)². If κ(X) is 10⁸, XᵀX has about 10¹⁶, which is beyond double precision. That's why libraries use QR or SVD for regression.
The pseudoinverse
When there's no inverse, take the SVD, invert the non-zero singular values and leave the zeros at zero. That gives A⁺. It handles every case:
- Too many equations: A⁺b is the least-squares answer.
- Too few equations: of infinitely many exact answers, A⁺b has the smallest norm.
It also connects to ridge: as λ shrinks to zero, the ridge solution approaches A⁺b.
The maths
Example: if κ = 1,000 and your data has 0.1% noise, the answer could be wrong by up to 100%.
In practice
In practice
- Use a solver: call solve, not inv. For regression, call a least-squares function.
- Scale your features: features in very different units raise the condition number. Standardising is an easy fix.
- Reuse factors: if you solve for many b, factor once, then each solve is cheap.
- Choose a cutoff: pseudoinverse functions treat tiny singular values as zero. That threshold matters when you're near rank deficiency.
- Very large systems: direct methods grow with n³, so use iterative methods such as conjugate gradient, or gradient descent, for huge or sparse problems.
The answer that sounds right
"My matrix isn't singular, so inverting is safe"
It sounds right, since the inverse exists. But being invertible isn't the same as being safe. A nearly singular matrix has an inverse, and it amplifies every rounding error and bit of noise. Check the condition number, and solve by factoring. Regularisation helps where the problem itself is unstable.
Say it
Why shouldn't you invert a matrix to solve Ax = b, and what is the pseudoinverse?
Say your answer out loud
Aim for 30 seconds. It feels different from reading it, and that's the point.
Tick what you covered
The interviewer pushes further
Follow-up 1 of 3
Why do the normal equations lose accuracy?
Answer it out loud, then check.
Forming XᵀX squares the condition number. A condition number of 10⁸, which is manageable, becomes 10¹⁶, close to the limit of double precision. QR works on X directly, so it avoids this. Normal equations remain faster, and they're fine for well-conditioned problems.
Follow-up 2 of 3
What does the pseudoinverse give when there are more unknowns than equations?
Answer it out loud, then check.
Of the infinitely many exact solutions, it gives the one with the smallest norm. Interestingly, gradient descent started at zero converges to this same solution for linear regression, which is one way of explaining implicit regularisation.
Follow-up 3 of 3
When would you use gradient descent instead of a direct solve?
Answer it out loud, then check.
When n is so large that n³ or even storing the matrix is too expensive, or when the data is sparse or arrives in batches. Direct methods are exact and can be better for small dense problems. Conditioning still matters, since badly conditioned problems also slow gradient descent.
I wouldn't invert. Computing the inverse costs about three times an LU solve, and it's less accurate. I'd factor A into easy pieces: LU for general matrices, Cholesky for positive definite ones at half the cost, QR for least squares and SVD if the rank is in doubt. The condition number, largest over smallest singular value, says how much errors get amplified, and normal equations square it, which is why libraries use QR or SVD. The pseudoinverse inverts only the non-zero singular values, giving the least-squares answer with the smallest norm.
Key terms and sources
How computers actually solve linear systems: LU, QR, Cholesky and SVD, the condition number, and the Moore-Penrose pseudoinverse.
Sources
- Boyd and Vandenberghe, Introduction to Applied Linear Algebra
- Strang, Linear Algebra and Learning from Data
- Deisenroth, Faisal and Ong, Mathematics for Machine Learning
- Kolter and Do, CS229 Linear Algebra Review
Explanations are ours, built from these sources. Lab numbers are illustrative, and worked examples were checked by calculation.