Notes - Numerical Analysis HT24, Least-squares
Flashcards
Quickly derive a solution to
\[\min_x ||Ax - b||\]
where $A \in \mathbb R^{m \times n}$, $b \in \mathbb R^m$ and $m \ge n$, using $QR$ factorisation.
Let
\[A = (Q \quad Q_\perp) {R \choose \pmb 0} = Q_F {R \choose \pmb 0}\]be a full QR factorisation of $A$. (Explicitly, the dimensions are: $Q \in \mathbb R^{m \times n}$, $Q _ \perp \in \mathbb R^{m \times (m-n)}$, $R \in \mathbb R^{n \times n}$, $\pmb 0 \in \mathbb R^{(m - n) \times n}$). Then since $Q _ F$ is orthogonal, it doesn’t affect the norm, so
\[\begin{aligned} ||Ax - b|| &= ||Q_F^\top (Ax - b)|| \\\\ &= ||Q_F^\top Ax - Q^\top _F b|| \\\\ &= \left|\left| {R \choose 0} x - { {Q^\top b \choose Q^\top_\perp b}\\,} \right|\right| \\\\ &= ||Rx - Q^\top b|| + ||{-Q^\top_\perp b}|| \\\\ \end{aligned}\]Since $-Q^\top _ \perp b$ is independent of $x$, the minimum occurs when $Rx = Q^\top b$, which can be solved via normal methods (since both sides are the correct dimension: $R$ is $n \times n$, $x$ is $n \times 1$ and $Q^\top b$ is $n \times 1$).
Quickly derive a solution to
\[\min_x ||Ax - b||\]
where $A \in \mathbb R^{m \times n}$, $b \in \mathbb R^m$ and $m \ge n$, using the SVD of $A$.
Sketch: Use the same trick as in the QR case, by using the full QR and taking $U _ F = [U; U _ \perp]$ and then using the fact that $ \vert \vert U _ F(Ax - b) \vert \vert = \vert \vert Ax - b \vert \vert $.
(Another proof, not using the SVD, can be done by applying the results about best approximations in inner product spaces: this problem is equivalent to finding the best approximation of $b$ in the subspace of $\mathbb R^m$ given by the columns of $A$).