3 ms·
Example where it comes in handy: OLS (ordinary least squares). You want to solve Ax = b approximately. So, minimise the two-norm |Ax-b|, or equivalently, |Ax-b
by FabHK 4y ago
Example where it comes in handy: OLS (ordinary least squares).
You want to solve Ax = b approximately. So, minimise the two-norm |Ax-b|, or equivalently, |Ax-b|^2, or equivalently (Ax-b)ᵀ(Ax-b) = xᵀAᵀAx - 2xᵀAᵀb + bᵀb.
How to minimise it? Easy, take the derivative wrt the vector x and set to zero (the zero vector):
2AᵀAx - 2Aᵀb = 0, so x = (AᵀA)⁻¹ Aᵀb.
(Note: that's the mathematical formulation of the solution, not how you'd actually compute it.)
- enriquto 4y agoOr, equivalently, you can do the "engineer's trick": To solve an over-determined system Ax=b, where A is a rectangular matrix, you multiply both sides by Aᵀ. Thus you obtain a new system whose matrix AᵀA is square, and you can solve normally.
- mkl 4y agoThat doesn't explain why it's least squares though, which was FabHK's point. In isolation it actually seems like a pretty arbitrary thing to do.
- enriquto 4y agoSure, it's mostly a mnemonic. But you can do it easily in your head, even in infinite dimensions. For example, if you recall that (due to stokes theorem) the divergence is minus the transpose of the gradient, you can solve many variational problems that way. The canonical example is: find a function u whose gradient is a given vector field F. This is an over-determined system without a solution. Applying the above trick, you compute the divergence of both sides to obtain Poisson equation Δu=div(F), that you can solve. This is equivalent to finding the least-square minimizer of the energy E(u)=∫|∇u-F|²