NLA MT25, Least-squares
Flashcards
Via QR factorisation
See in particular ∆least-squares-with-qr.
@State a result that characterises the backward stability of finding the least squares solution to an overdetermined linear system $Ax \approx b$ via the QR decomposition.
This process is backward stable, so the computed $\hat x$ satisfies… @todo.
Via normal equations
@Prove that
\[\hat x = \text{argmin} _ x \vert \vert Ax - b\| _ 2 \iff (A^\top A) \hat x = A^\top b\]
so that in particular we may solve the least-squares problem by solving the normal equations.
We minimise the squared objective:
\[\begin{aligned} \vert \vert Ax-b \vert \vert _ 2^2 &= (Ax - b)^\top (Ax -b) \\ &= (x^\top A^\top - b^\top)(Ax - b) \\ &= x^\top A^\top A x - x^\top A^\top b - b^\top Ax + b^\top b \\ \end{aligned}\]Differentiating with respect to $x$ and setting to $0$, we find the minimum occurs when
\[\begin{aligned} &2A^\top A \hat x - A^\top b = 0 \\ \iff& A^\top A\hat x = A^\top b \end{aligned}\]What are the pros and cons of solving least squares problems $\min _ x \vert \vert Ax - b \vert \vert _ 2$ using the normal equations $A^\top A x = A^\top b$ and the Cholesky decomposition of $A^\top A$ (which exists, since $A^\top A \succ 0$ when $\text{rank}(A) = n$).
- Pros: Fast compared to e.g. using the QR decomposition.
- Cons: Not backward stable, since $\kappa _ 2(A^\top A) = (\kappa _ 2 (A))^2$.