Chapter 3 Orthoginal Matrices and the Least-Squares Problem

[Def] Q is orthogonal matrix if QQ^T = I ( $\Rightarrow$ Q^T = Q^-1)

Note : If Q orthogonal

$\Rightarrow$ < g_i , g_j > = $\left \{\matrix{1 , i=j \cr 0 , i \ne j \cr } \right \{ g_i \}$ are row ( column ) vectors of Q .
$< \cdot , \cdot > : {I\!\!R}^n \times {I\!\!R}^n \rightarrow I\!\!R$ is a inner product if

1. < x , y > = < y , x >
2. < $\delta$ x + $\beta$ y , z > = $\delta$ < x , z > + $\beta$ < y , z >
3. $< x , \delta y + \beta z >$ = $\delta$ < x . y > + $\beta$ < x , z >
4. < x , x > $\geq$ 0 ( < x , x > = 0 $\Leftrightarrow$ < x = 0 >

Example : < x , y > = x^T y = y^T x

${\Vert x \Vert}^2_2$ = < x , x > = x^T x ( because If  x = < x₁ , x₂ , ... , x_n >

$\Rightarrow$ ${\Vert x \Vert}^2_2$ = x²₁ + x²₂ + ... , x²_n )

Cauchy Schwartz Inequality :

$\vert < x , y > \vert$ $\leq$ ${\Vert x \Vert}_2 {\Vert y \Vert}_2$
( $\vert \sum^n_{i=1} x_i y_i \vert$ $\leq$ ${(\sum {\vert x_i \vert}^2)}^{1 \over 2}$ ${(\sum {\vert y_i \vert}^2)}^{1 \over 2}$ )

The angle of two vector x,y satisfy $\cos \theta$ = ${{< x , y >} \over {{\Vert x \Vert}_2 {\Vert y \Vert}_2}}$

i.e. $\theta$ = ${\cos}^{-1} ( {{< x , y >} \over {{\Vert x \Vert}_2 {\Vert y \Vret}_2}})$

Least-Square Problems :

Example : $\left \{ \matrix{ 2 x_1 + x_2 = 3 \cr 3 x_1 - x_2 = 5 \cr x_1 - 2 x_2 = 4 \cr } \right$
over-determinate
Least Square Problem :

Find the best answer x^T , satisfy $\Vert$ b - A x^T ${\Vert}_2$ minimal .

Note : use A=QR can solve Least Square Solution x^T of Ax=b .

[Thm] $A \in {I\!\!R}^{ n \times m }$ $\Rightarrow$ A=QR     $Q \in {I\!\!R}^{ n \times m }$     $R \in {I\!\!R}^{ n \times m }$

where Q : Orthogonal R : upper triangular

Use A = QR to solve the system of AX = b :

STEP 1. QRx = b
STEP 2. Rx = Q^Tb
STEP 3. Let   Q^T b = d
STEP 4. Solve  Rx = d   by  the backward subsitution.

In MATLAB , A = QR

>> [ Q , R ] = qr(A)

$\left \{ \matrix{ Rotator \cr Reflector \cr } \right ~~~~~ \left [ \matrix{ \cos \theta & -\sin \theta \cr \sin \theta & \cos \theta \cr } \right ]$: Rotator is an orthogonal matrix

Q orthogonal $\Rightarrow$ ${\Vert Qx \Vert}_2$ = ${\Vert x \Vert}_2$

[Lemma]

< Qx , Qy > = < x , y >

< Qx , Qy > = (Qy)^T (Qx) = y^T ( Q^T Q ) x = y^T x = < x , y >

when   x=y $\Rightarrow$ < Qx , Qy > = < x , x >

$\Vert ~~~~~~~~~~~~~~~~~~\Vert$

$\Vert$ Qx $\Vert$ ²₂        ${\Vert x \Vert}^2_2$

Least-Square Problem :

${min}_{ \~ x }$ $\Vert$ $b - A \~ x$ ${\Vert}_2$ = ${min}_{ \~ x }$ $\Vert$ $Q^T b - Q^T A \~ x$ ${\Vert}_2$ = ${min}_{ \~ x }$ $\Vert$ $d - R \~ x$ ${\Vert}_2$ ( If A=QR )

A is nonsingular

$\Leftrightarrow$ column vectors are l.I. .

$\Leftrightarrow$ row vectors are l.I. .

Rotator :

Q = $\left [ \matrix{ \cos \theta & -\sin \theta \cr \sin \theta & \cos \theta \cr } \right ]$

(Q^-1 = ) = Q^T = $\left [ \matrix{ \cos \theta & \sin \theta \cr -\sin \theta & \cos \theta \cr } \right ]$ $\left [ \matrix{ x_1 \cr x_2 \cr } \right ]$ = $\left [ \matrix{ y \cr 0 \cr} \right ]$

then , cos $\theta$ = ? , sin $\theta$ = ?

$\left \{ \matrix{ x_1 \cos \theta + x_2 \sin \theta = y \cr - x_1 \sin \theta + x_2 \cos \theta = 0 \cr } \right$

$\Rightarrow$ x₁ sin $\theta$ = x₂ cos $\theta$

cos $\theta$ = ${{ x_1 } \over { \sqrt {x^2_1 + x^2_2}}}$ , sin $\theta$ = ${{ x_2 } \over { \sqrt {x^2_1 + x^2_2}}}$

( because must be satisfy ${\cos}^2$ $\theta$ + ${\sin}^2$ $\theta$ = 1 ) Given matrix :

$\left \matrix { \cr \cr i~th~~\rightarrow \cr \cr j~th~~\rightarrow \cr \cr \cr } \right$ $\left [ \matrix{ 1 &&&&&& \cr & \ddots &&&&& \cr && C && -S && \cr &&& \ddots &&& \cr && S && C && \cr &&&&& \ddots & \cr &&&&&& 1 \cr } \right ]$ $\left [ \matrix{ x_1 \cr \vdots \cr x_i \cr \vdots \cr x_j \cr \vdots \cr x_n \cr } \right ]$= $\left [ \matrix{ x_1 \cr \vdots \cr \sqrt 5 \cr \vdots \cr 0 \cr \vdots \cr x_n \cr} \right ]$

$~~~~~~~~~~~~~~~~~~~\uparrow ~~~~~~~~~~~~~~~~\uparrow$

  i th   j th    column C = ${ {x_i} \over { \sqrt {x^2_i + x^2_j}}}$ S = ${ {x_j} \over { \sqrt {x^2_i + x^2_j}}}$

Reflectors : (Picture:)

Reflectors : Q

$\left \{\matrix{ Qu = -u \cr Qv = v \cr } \right$

If P = u u^T    $\Vert u \Vert$ = 1    P² = P ( projection )

1. Pu = -u      $\times$

because   Pu = u u^T u = u
2. Pv = v      $\times$

Pv = u ( u^t v ) = 0

Let   Q = I - 2P    Q² = I  ( idempotent )

then , Qu = I(u) - 2P(u) = u - 2u = -u and QV = I(v) - 2P(v) = v - 0 = v

so satisfy Reflector i.e. Q = I - 2 u u^T ( Householder transformation )

Note : u u^T is the rank 1 matrix .

Q = I - r u u^T , u has no limitation $\Vert u \Vert$ = 1   r = ${2 \over {\Vert u \Vert}^2_2}$

[Thm] ${\Vert x \Vert}_2$ = ${\Vert y \Vert}_2$ , $\exists$ ! Q orthogonal s.t. Qx = y .

Example : A = $\left [ \matrix{ 1 & 2 \cr 2 & 3 } \right ]$ = QR
We hope to find Q^T , x , Q^T . A = R   ( $\Rightarrow$ A=QR )
Q $\left [ \matrix{ 1 \cr 1 \cr } \right ]$ = $\left [ \matrix{ \sqrt 2 \cr 0 \cr } \right ]$

P147 Figure 3.4

1. x = ${1 \over 2} ( x + y )$ + ${1 \over 2} ( x - y )$
[ Note : $( x + y ) \bot ( x - y )$ ]
2. Q = I - r u u^T  ,  r = ${2 \over {\Vert u \Vert}^2_2}$

u₁ = ( x - y )
[ In the analysis of QR . x : the column vector of the origin A . y : the column vector of the origin R ]

reduction u = ${{x - y} \over {{\Vert x - y \Vert}_2}}$
Q = I - 2 u u^T

x - y = $\left [ \matrix{ 1 \cr 1 \cr } \right ] - \left [ \matrix{ \sqrt 2 \cr 0 \cr } \right ] = \left [ \matrix{ 1 - \sqrt 2 \cr 1 \cr } \right ]$

so   u = ${{1} \over {{(4 - 2 \sqrt 2 )}^{1 \over 2}}}$ $\left [ \matrix{ 1 - \sqrt 2 \cr 1 \cr } \right ]$ , $\left [ \matrix{ 1 - \sqrt 2 \cr 1 \cr } \right ]$ $\left [ \matrix{ 1 - \sqrt 2 & 1 \cr } \right ]$ = $\left [ \matrix{ 3 - 2 \sqrt 2 & 1 - \sqrt 2 \cr 1 - \sqrt 2 & 1 \cr } \right ]$

Q = $\left [ \matrix{ 1 & 0 \cr 0 & 1 \cr } \right ]$ - ${ 2 \over {4 - 2 \sqrt 2 }}$ $\left [ \matrix{ 3 - 2 \sqrt 2 & 1 - \sqrt 2 \cr 1 - \sqrt 2 & 1 \cr } \right ]$

Example :

A = $\left [ \matrix{ 1 & 2 & 3 \cr 2 & 3 & 4 \cr 2 & 1 & 3 \cr } \right ]$= QR
Q = I - 2 $\cdot {{u u^T} \over {{\Vert u \Vert}^2_2}}$ =
$\left [ \matrix{ 1 & 0 & 0 \cr 0 & 1 & 0 \cr 0 & 0 & 1 \cr } \right ]$ - ${1 \over 6}$ $\left [ \matrix{ 4 & -4 & -4 \cr -4 & 4 & 4 \cr -4 & 4 & 4 \cr } \right ]$
= $\left [ \matrix{ 1 \over 3 & 2 \over 3 & 2 \over 3 \cr 2 \over 3 & 1 \over 3 & -3 \over 3 \cr 2 \over 3 & -2 \over 3 & 1 \over 3 \cr } \right ]$ = ${1 \over 3} \left [ \matrix{ 1 & 2 & 2 \cr 2 & 1 & -2 \cr 2 & -2 & 1 \cr } \right ]$

Q^T . A = $\left [ \matrix{ 3 & {10} \over 3 & {17} \over 3 \cr 0 & 5 \over 3 & 4 \over 3 \cr 0 & - 1 \over 3 & 1 \over 3 \cr } \right ]$= ${1 \over 3}$ $\underbrace { \left [ \matrix{ 1 & 2 & 2 \cr 2 & 1 & -2 \cr 2 & -2 & 1 \cr } \right ] }_{Q^T}$ $\left [ \matrix{ 1 & 2 & 3 \cr 2 & 3 & 4 \cr 2 & 1 & 3 \cr } \right ]$
u = x - y = $\left [ \matrix{ 1 \cr 2 \cr 3 \cr} \right ]$ - $\left [ \matrix{ 3 \cr 0 \cr 0 \cr} \right ]$ = $\left [ \matrix{ -2 \cr 2 \cr 2 \cr} \right ]$

$\left [ \matrix{ -2 \cr 2 \cr 2 \cr} \right ]$ $\left [ \matrix{ -2 & 2 & 2 \cr} \right ]$= $\left [ \matrix{ 4 & -4 & -4 \cr -4 & 4 & 4 \cr -4 & 4 & 4 \cr } \right ]$
A = QR

1. Use Rotator ( Jacobi matrix ) Q = $\left [ \matrix{ \cos \theta & -\sin \theta \cr \sin \theta & \cos \theta \cr } \right ]$
2. Reflector : Q = I - 2 u u^T ( Orthogonal projector )
3. Gram-Schmidt Orthonomalization