next up previous
Next: About this document ...

Chapter 3 Orthoginal Matrices and the Least-Squares Problem

[Def] Q is orthogonal matrix if QQT = I ( $\Rightarrow$ QT = Q-1)

Note : If Q orthogonal

$\Rightarrow$ < gi , gj > = $\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 > = xT y = yT x

${\Vert x \Vert}^2_2$ = < x , x > = xT x ( because If  x = < x1 , x2 , ... , xn >

$\Rightarrow$ ${\Vert x \Vert}^2_2$ = x21 + x22 + ... , x2n )

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 xT , satisfy $\Vert$ b - A xT ${\Vert}_2$ minimal .

Note : use A=QR can solve Least Square Solution xT 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 = QTb
STEP 3. Let   QT 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) = yT ( QT Q ) x = yT x = < x , y >

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

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

$\Vert$ Qx $\Vert$ 22        ${\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 = ) = QT = $\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$ x1 sin $\theta$ = x2 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 uT    $\Vert u \Vert$ = 1    P2 = P ( projection )

1. Pu = -u      $\times$

because   Pu = u uT u = u
2. Pv = v      $\times$

Pv = u ( ut v ) = 0

Let   Q = I - 2P    Q2 = 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 uT ( Householder transformation )

Note : u uT is the rank 1 matrix .

Q = I - r u uT , 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 QT , x , QT . 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 uT  ,  r = ${2 \over {\Vert u \Vert}^2_2} $

u1 = ( 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 uT

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 ]$

QT . 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 uT ( Orthogonal projector )
3. Gram-Schmidt Orthonomalization



 
next up previous
Next: About this document ...

1998-08-20