Chapter 3.3 Solution of the LS Problem

$A \in {I\!\!R}^{ n \times m } ~~~n \geq m$

( Ax = b is called the over-determinate system ) Find $\hat x$ s.t. ${\Vert A \hat x - b \Vert}_2$ is minimal .

( min is the sense that ${\Vert A \hat x - b \Vert}_2$ $\leq$ ${\Vert Ay - b \Vert}_2$ for all y )

[Thm] If $A \in {I\!\!R}^{ n \times m }$ , $n \geq m$    $Q \in {I\!\!R}^{ n \times m }$     $R \in {I\!\!R}^{ n \times m }$

s.t. A=QR and $R=\left [ \matrix{ \hat R \cr 0 \cr } \right ]$

<Proof> $A \in {I\!\!R}^{ n \times m }$   Let   $\hat A = [ A , \~ A ] \in {I\!\!R}^{ n \times n }$

$\~ A {I\!\!R}^{ n \times ( n - m ) }$  is  choosen arbitrary .

$\Rightarrow \exists ! Q , \bar R ~s.t.~A=Q \bar R , \bar R = [ R , \~ R ]$

$\~ R \in {I\!\!R}^{ n \times ( n - m ) }$   ( upper triangle )

$\Rightarrow$ A=QR

R  has the form  $\left [ \matrix{ \hat R \cr 0 \cr } \right ]$

Example :
$A = \left [ \matrix{ 1 & 2 \cr 3 & 4 \cr 5 & 6 \cr 7 & 8 \cr } \right ]$
$\Rightarrow$ $\left [ \matrix{ 1 & 2 & 3 & -2 \cr 3 & 4 & 2 & -5 \cr 5 & 6 & -3 & 1 \cr 7 & 8 & 1 & 4 \cr } \right ]$ = $Q \left [ \matrix{ * & * & * & * \cr & * & * & * \cr && * & * \cr 0 &&& * \cr } \right ]$ $A = Q \~ R$ $\Vert b - A \hat x \Vert$  ( Q  is  orthonogal  ) 

${\Vert Q^T b - Q^T A \hat x \Vert}_2$= ${\Vert Q^T b - R \hat x \Vert}_2$ = ${\Vert d - c \Vert}_2$ = ${[{( d_1 - c_1 )}^2 + \cdots + {( d_m - c_m )}^2 + d^2_{m+1} + \cdots + d^2_n ]}^{1 \over 2}$

where   $\left \{ \matrix{ d = Q^T b = \left [ \matrix{ d_1 \cr d_2 \cr \vdots \cr d_n... ...t x = \left [ \matrix{ c_1 \cr c_3 \cr \vdots \cr c_n \cr } \right ] } \right$

The min. of  ${\Vert b - A \hat x \Vert}_2$  is in   $c_i = d_i , i = 1 , \cdots , m$

and the min. is   $\sqrt { d^2_{m+1} + \cdots + d^2_n }$

( Note : d_i is fixed , c_i is changing .)

Full-Rank Case :

S = $\left [ \matrix{ \hat C \cr d \cr } \right ] - \left [ \matrix{ \hat R \cr 0 \cr } \right ] x$ = $\left [ \matrix{ \hat C - \hat R x \cr d \cr } \right ]$

$~~~~~\Vert ~~~~~~\Vert$ $~~~~Q^T b ~~~~R \hat x$

Thus ${\Vert S \Vert}^2_2$ = $\sum {\vert S_i \vert}^2$ = ${\Vert \hat C - \hat R x \Vert}^2_2 + {\Vert d \Vert}^2_2$

( When the min. product in $\hat C - \hat R x = 0$ , then x is the solve of $\hat R x = \hat C$

P160 3.36

$\left [ \matrix{ 3 & -2 \cr 0 & 3 \cr 4 & 4 \cr } \right ] \left [ \matrix{ x_1 \cr x_2 \cr } \right ]$ = $\left [ \matrix{ 1 \cr 2 \cr 4 \cr } \right ]$

C = Q^T b = $\left [ \matrix{ {{-19} \over 5} \cr {{-62} \over {25}} \cr {{-16} \over {25}} \cr } \right ]$R = $\left [ \matrix{ -5 & -2 \cr 0 & -5 \cr 0 & 0 \cr } \right ]$ $\Vert \hat R x - \hat C \Vert = 0$

$\underbrace {Q_2 Q_1}_{Q^T} A = \left [ \matrix{ -5 & -2 \cr 0 & -5 \cr 0 & 0 \cr } \right ]$

Ax = b $\Rightarrow$ Q^T A x = Q^T b

$\left [ \matrix{ -5 & -2 \cr 0 & -5 \cr 0 & 0 \cr } \right ] \left [ \matrix{ x_1 \cr x_2 \cr } \right ]$ = $\left [ \matrix{ {{-19} \over 5} \cr {{-62} \over {25}} \cr {{-16} \over {25}} \cr } \right ]$ solution $\left [ \matrix{ x_1 \cr x_2 \cr } \right ] = \left [ \matrix{ {{351} \over {625}} \cr {{62} \over {125}} \cr } \right ]$

Least Square Error :

${\left \Vert \matrix{ \left [ \matrix{ -5 & 2 \cr 0 & -5 \cr 0 & 0 \cr } ... ...16} \over {25}} \cr } \right ] \cr } \right \Vert}_2 = {{16} \over {25}}$

Rank-Deficient Case

If $A \in {I\!\!R}_{ n \times m }$ , n > m ,rank(A) = r < m , then $~\exists Q , R$

 s.t.  A = QR ,  where  R = $\left [ \matrix{ R_{11} & R_{12} \cr 0 & 0 \cr } \right ]$ $\left \{ \matrix{ R_{11} \in {I\!\!R}^{ r \times r } ~~(~upper~triangle~)~ \cr R_{12} \in {I\!\!R}^{ r \times ( m - r ) } } \right$

$\left [ \matrix{ * & * & * \cr 0 & * & * \cr 0 & 0 & * \cr 0 & 0 & 0 \cr 0 & 0 & 0 \cr } \right ]$      rank(3)

$\left [ \matrix{ * & * & * \cr 0 & * & * \cr 0 & 0 & 0 \cr 0 & 0 & 0 \cr 0 & 0 & 0 \cr } \right ]$      rank(A) = 2

Q^T A x = Q^T b $\Rightarrow$ Rx = Q^T b

$\left [ \matrix{ R_{11} & R_{12} \cr 0 & 0 \cr } \right ] \left [ \matr... ...r } \right ] = Q^T b = \left [ \matrix{ \hat c \cr \hat d \cr } \right ]$

Least Square Error :

${\left \Vert \matrix{ \left [ \matrix{ \hat c \cr \hat d \cr } \right ] & - ... ... {x_2} \cr \hat d \cr } \right ] } \right \Vert}_2 = {\Vert \hat d \Vert}_2$

( If we choose $x = \left [ \matrix{ x_1 \cr x_2 \cr } \right ]$ s.t. $R_{11} \hat {x_1} + R_{12} \hat {x_2} = ?$

$\Rightarrow R_{11} \hat {x_1} = \hat c - R_{12} \hat {x_2}$ )

Rank is small , Least Square is large .