09 - Solution to Least Squares Problem

Solution to Least Squares Problem

Let $A$ be a $m\times n$ matrix with $m\ge n$ with QR decomposition

$$A=\left[\begin{array}{cc}Q& Q_{\perp }\end{array}\right]\left[\begin{array}{c}R\\ 0\end{array}\right]=Q_F\left[\begin{array}{c}R\\ 0\end{array}\right]$$

be the full QR decomposition via Householder QR Factorisation

Assuming $R$ is non-singular so $A$ has full column rank then

Least Squares Problem

$$\underset{x}{\min }||Ax-b||\text{ for }b\in {\mathbb{R}}^m$$

has solution

$$x=R^{-1}{Q}^{T}b$$

Proof

As

$$||Q_F^{T}y||=\sqrt{y^T{Q}_F{Q}_F^{T}y}=\sqrt{y^{T}y}=||y||$$

for any $y$ then

$$||Ax-b||=||Q_F^T(Ax-b)||=\left|\left|\left[\begin{array}{c}R\\ 0\end{array}\right]x-\left[\begin{array}{c}{Q}^{T}b\\ Q_{\perp }^{T}b\end{array}\right]\right|\right|$$

where bottom part is always $-Q_{\perp }b$ regardless of $x$
with top part being $0$ if $x=R^{-1}{Q}^{T}b$