04. Least-Square Problem

Least Squares Problem

Consider $Ax=b$
As $Ax=b$ doesn’t always have a solution then consider

Least Squares Problem

$$\underset{x}{\min }||Ax-b||\text{ for }A\in {\mathbb{R}}^{m\times n},b\in {\mathbb{R}}^m,m\ge n$$

where

$$||y||:=\sqrt{y_1^2+y_2^2+\cdots +y_m^2}=\sqrt{y^{T}y}$$

Link to original

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$

Link to original