Chapter 3.4 O.N. vectors and the Gram-Schmidt Process

$A \in {I\!\!R}^{ n \times n }$ , and $\{ e_1 , \cdots , e_n \}$

then $[A e_1 , A e_2 , \cdots , A e_n ]$

A e_j : the j-th column of A

(e_i^T A : the i-th row of A )

$Ax : span \{ A_1 , \cdots , A_n \} , A_i ~column~vectors~of~A .$

$x^T A :span \{ a_1 ,\cdots , a_n \} , a_j ~row~vectors~of~A .$

[Def] $Q \in {I\!\!R}^{ n \times m }$ , $n \geq m$ is called isometric $\Leftrightarrow Q^T Q = I_m$

( $Q Q^T = I \ne Q ~~is~isometric$ )

i.e. the column vectors are O.N.

$A \in {I\!\!R}^{ n \times m } , n \geq m$, then $A = \hat Q \hat R$ where $\hat Q \in {I\!\!R}^{ n \times m }$

$\hat R \in {I\!\!R}^{ m \times m }$ and $\hat Q$ is isometric .

<Proof> A = QR , Q $\in {I\!\!R}^{ n \times n }$ , $R \in {I\!\!R}^{ n \times m }~~$ $n \geq m$where $Q = [ \hat Q , \hat Q ]$ , R = $\left [ \matrix{ \hat R \cr 0 \cr } \right ]$ $\Rightarrow A = QR =$ $\left [ \matrix{ \hat Q , \hat Q } \right ]$ $\left [ \matrix{ \hat R \cr 0 \cr } \right ]$ = $\hat Q \hat R + \hat Q 0$ = $\hat Q \hat R$

Gram-Schmidt

$\{ v_1 , v_2 ,\cdots , v_m \} \leftrightarrow \{ g_1 , g_2 , \cdots , g_m \} , g_i$ : O.N.vectors

Exercise : P168 Ex3.4.1 Ex3.4.3 Gram-Schmidt process $\{ v_1 , \cdots , v_m \}$ is a basis

$\Rightarrow \{ g_1 , g_2 , \cdots , g_n \}$ orthonormal basis

such procsee is called Gram-Schmidt orthonomalization .

$v_1 \rightarrow g_1 = {{ v_1 } \over {\Vert v_1 \Vert}}$

$\left \{ \matrix{ {\~ g}_2 = v_2 - < v_2 , g_1 > \cdot g_1 \cr {g_2} = {{{\~ g}_2} \over {\Vert g_2} \Vert} \cr } \right$

$\left \{ \matrix{ {\~ g}_3 = v_3 - < v_3 , g_2 > \cdot g_2 - < v_3 , g_1 > \cdot g_1 \cr {g_3} = {{{\~ g}_3} \over {\Vert g_3} \Vert} \cr } \right$

In general

$\left \{ \matrix{ {\~ g}_k = v_k - \sum^{ k - 1 }_{ i = 1 } < v_k , g_j > g_j \cr g_k ={ {{\~ g}_k } \over {\Vert g_k \Vert}} \cr } \right$ $\Rightarrow$ $v_k = \sum_{j=1} r_{jk} g_j + r_{kk} g_k$,

Let $r_{kk} = \Vert {\~ g}_k \Vert , j=k$

Let r_jk = < v_k , g_j > , j < k

$V=[ v_1 , v_2 ,\cdots , v_n ]$ = $[ g_1 , g_2 , \cdots , g_n ]$ $\left [ \matrix{ r_{11}& r_{12} & \cdots & r_{1n} \cr 0 & r_{22} & \cdots & r_{2n} \cr 0 & 0 & \ddots & \vdots \cr 0 & 0 & 0 & r_{nn} \cr } \right ]$

v_i are the column vextors of V

$\left \{ \matrix{ r_{jk} = < v_k , g_j > \cr r_{kk} = \Vert {\~ g}_k \Vert \cr } \right$

1. Subspace : $\varphi \subset {I\!\!R}^n$ is subspace of ${I\!\!R}^n$

if $\varphi \ne 0$ and $\left \{ \matrix{ u,v \in \varphi \Rightarrow u + v \in \varphi \cr cu \in \varphi , c \in I\!\!R \cr} \right$

2. Linear Independent 3. Span $\{ v_1 , v_2 , \cdots , v_n \}$ = $< v_1 , v_2 , \cdots , v_n >$ $\left \{ \matrix{ < v_1 > = < g_1 > \cr < v_1 , v_2 > = < g_1 , g_2 > \cr \vdots \cr < v_1 , \cdots , v_n > = < g_1 , \cdots , g_n > \cr } \right$

If $< v_1 , v_2 , \cdots , v_m >$ = $< w_1 , w_2 , \cdots , w_m >$

$\Rightarrow < v_1 , v_2 , \cdots , v_m , u >$ = $< w_1 , w_2 , \cdots , w_m , u >$

$\varphi \subset {I\!\!R}^n$ subspace of ${I\!\!R}^n$

${\varphi}^{\bot} = \{ x \in {I\!\!R}^n \vert ( x , y ) = 0 , \forall y \in \varphi \}$ is the orthogonal complement of $\varphi$ .

Note : 1. $\varphi^{\bot}$ is also a subspace of ${I\!\!R}^n$ . 2. $\varphi = < g_1 , g_2 , \cdots , g_k >$ $\Rightarrow {\varphi}^{\bot} < g_{k+1} , \cdots , g_n > g_i$ are the O.N. vectors .

[Thm] $\varphi \in {I\!\!R}^n$ subspace of ${I\!\!R}^n$ , then ${I\!\!R}^n = \varphi \oplus {\varphi}^{\bot}$

( i.e. $\Rightarrow$ if $x \in {I\!\!R}^n$ , then $x = \rho + {\rho}^{\bot}$,where $\rho \in \varphi , \rho \in {\varphi}^{\bot}$

moreever , $\varphi \cap {\rho}^{\bot} = \{ 0 \}$ )

<Proof> $\varphi = < v_1 , \cdots , v_m > = < g_1 , \cdots , g_m >$

${I\!\!R}^n$ = $< v_1 , \cdots , v_m , v_{m+1} , \cdots , v_n >$ = $< g_1 , \cdots , g_m , g_{m+1} , \cdots , g_n >$

and $< v_{m+1} , \cdots , v_n >$ = $< g_{m+1} , \cdots , g_n >$

$\varphi$ = $< g_1 , \cdots , g_m >$ = $< g_{m+1} , \cdots , g_n > = {\varphi}^{\bot}$

$\Rightarrow x = \rho + {\rho}^{\bot}$

$\varphi \cap {\varphi}^{\bot} = \{ 0 \} \par\Rightarrow {I\!\!R}^n = \varphi \oplus {\varphi}^{\bot}$

$A : {I\!\!R}^m \rightarrow {I\!\!R}^n ( A \in {I\!\!R}^{n \times m} )$

N(A) = null space of $A = \{ x \vert Ax = 0 \} \subset {I\!\!R}^m$

R(A) = range of $A = \{ Ax \vert x \in {I\!\!R}^m \} \subset {I\!\!R}^n$ [Thm] $A : {I\!\!R}^m \rightarrow {I\!\!R}^n ( A \in {I\!\!R}^{n \times m}) ~~x \in {I\!\!R}^m , y \in {I\!\!R}^n$ then < nx , y > = < x , A^T y >

$\Rightarrow$ y^T A x = (A^T y)^T x

[Thm] $R {(A)}^{\bot} = N( A^T )$

[Thm] ${I\!\!R}^m = R(A) \oplus N( A^T )$

${I\!\!R}^n = R( A^T ) \oplus N(A)$

[Thm] If A is symmetric , ${I\!\!R}^n = N(A) \oplus R(A)$

$\varphi \subset {I\!\!R}^n$

${\varphi}^{\bot} = \{ x \vert ( x , y ) = 0 , \forall y \in \varphi \}$

If $A \in {I\!\!R}^{ n \times m }$ ( i.e. $A : {I\!\!R}^m \rightarrow {I\!\!R}^n$)

Range : R(A) = $\{ Ax \vert x \in {I\!\!R}^m \} \subset {I\!\!R}^n$

Null space : N(A) = $\{ x \in {I\!\!R}^m \vert Ax = 0 \} \subset {I\!\!R}^m$

<Proof of $R {(A)}^{\bot} = N( A^T )$>

$( \Rightarrow )$ If $y \in R{(A)}^T \Rightarrow ( Ax , y ) = 0 \Rightarrow ( x , A^T y ) = 0$ for all x

$\Rightarrow A^T y = 0 \Rightarrow y \in N( A^T )$

In particular $= {\Vert A^T y \Vert}^2_2 = ( A^T y , A^T y ) = 0$

i.e. $R {(A)}^{\bot} < N( A^T )$

$( \Leftarrow )$ If $y \in N( A^T ) \Rightarrow A^T y = 0 \Rightarrow ( x , A^T y ) = 0 \par\Rightarrow ( Ax , y ) = 0 \Rightarrow y \in R{(A)}^{\bot}$

i.e. $N( A^T ) \subset R {(A)}^T$

[Lemma] ${\varphi}^{\bot \bot} = \varphi$

[Thm] $R( A^T ) = N {(A)}^{\bot}$

<Proof> Because $R {(A)}^{\bot} = N( A^T ) \par\Rightarrow R{( A^T )}^{\bot} = N( A^{TT} ) = N(A) \par\Rightarrow {[ R{( A^T )}^{\bot} ]}^{\bot} = {[ N(A) ]^{\bot}}$

$\left \{ \eqalign{ {I\!\!R}^n = R(A) \oplus N( A^T ) \cr {I\!\!R}^m = R( A^T ) \oplus N(A) \cr } \right$

Note : nullity (T) + range (T) = dim S

( If T : S $\rightarrow$ S linear transformation )

Exercise : 3.5.7

$\left \{ \matrix{ The ~colume~space~ = R(A) \cr The ~row~space~of~A~ = N {(A)}^{\bot} } \right$ $\Rightarrow \left \{ \matrix{ R {(A)}^{\bot} = N (A^T) \cr N {(A)}^{\bot} = R (A^T) \cr } \right \}$ ( because column space A = row space of A^T )

$\S$ The Discrete Least-Square Problem

If $A \in {I\!\!R}^{n \times m} , n > m$

$\Vert b - Ay \Vert = {min}_{ w \in {I\!\!R}^n } \Vert b - Aw \Vert$

[Thm] ( Pythagorean Thm. )

${\Vert u + v \Vert}^2 = {\Vert u \Vert}^2 + {\Vert v \Vert}^2$ if ( u ,v ) = 0

<Proof> ${\Vert u + v \Vert}^2 = < u + v , u + v >$ = < u , u > + < u , v > + < v , u > + < v , v > = ${\Vert u \Vert}^2 + {\Vert v \Vert}^2$

Note : The Least-Square Error $b - Ay \in R {(A)}^2$

[Thm] If $\varphi \in {I\!\!R}^n , b \in {I\!\!R}^n$ , then $\exists y \in \varphi$

such that ${\Vert b - y \Vert}_2 = {min}_{ s \in \varphi } {\Vert b - s \Vert}_2$

where y is the unique element in $\varphi$

such that $b - y \in {\varphi}^{\bot}$

( i.e. y is the orthogonal projection of b into $\varphi$ )

[Cor] Let $A \in {I\!\!R}^{ n \times m }$ . Then ${\Vert b - Ax \Vert}_2$ = ${min}_{w \in {I\!\!R}^m} {\Vert b - Aw \Vert}_2 \par\Leftrightarrow b - Ax \in R {(A)}^{\bot}$

<Proof> ${I\!\!R}^n = \varphi \oplus {\varphi}^{\bot}$

b = y + z , where $y \in \varphi , z \in {\varphi}^{\bot}$

$b - y = z \in {\varphi}^{\bot}$ ${I\!\!R}^n = \varphi \oplus {\varphi}^{\bot}$

b = y + z uniquelly , with $y \in \varphi , z \in {\varphi}^{\bot}$ and $b - y = z \in {\varphi}^{\bot}$

If $w \in \varphi$ s.t. $b = w + ( b - w ) \Rightarrow w = y$

$( {\Vert b - y \Vert}_2 = {min}_{s \in \varphi} {\vert b - s \vert}_2 )$

consider b - s = ( b - y ) + ( y - s ) , where $s \in \varphi , y \in \varphi$

$\Rightarrow$ ${\Vert b - s \Vert}^2_2$ = ${\Vert b - y \Vert}^2_2 + {\Vert y - s \Vert}^2_2$

$\Rightarrow$ ${\Vert b - s \Vert}_2$ is $min \Leftrightarrow y = s$

i.e. $\Vert b - y \Vert = {min}_{s \in \varphi } \Vert b - s \Vert$

$Ax = b . A \in {I\!\!R}^{n \times m} , n > m$

$\Leftrightarrow$ $b - Ax \in R {(A)}^{\bot} = N( A^T )$

$\Leftrightarrow$ A^T ( b - Ax ) = 0

$\Leftrightarrow$ A^T A x = A^T b ( normal equation )

Note : $A^T A \in {I\!\!R}^{ m \times m}$

Note : 1. Solving L.S. Problems Ax = b , $A \in {I\!\!R}^{ n \times m }$ is the same to solving normal equation A^T A x = A^T b . 2. A^T A i. symmetry . ii. nonneqative defined ( Positive semidefined $x^T B x \geq 0$ ). 3. If A is full rank ( i.e. rank A = m ) , then A^T A is positive define $\Rightarrow$ Chelosky Decomposition ( on A^T A ) to solve the ( A^T A ) x = A^T b

The way of solving Least Square Solution :

1. QR 2. Cholesky 3, A $\backslash$ b

1. (A^T A)^T = A^T A^TT = A^T A2. nonnegative defined

$\forall x \ne 0 , x^T (A^T A) x \geq 0$ $\Rightarrow {\Vert Ax \Vert}^2_2 \geq 0$3. <Proof> A is full rank , A^T A is nonsingular . If $(A^T A) x = 0 \Rightarrow x = 0$ for all $x \ne 0 , x^T (A^T A) x > 0 .$

$\S$ The Continuous Least Square Problem

Discrete ${\Vert b - Ax \Vert}_2 = min \Vert b - Aw \Vert$

Continuous ${\Vert f - \phi \Vert}_2 = min \Vert f - \psi \Vert$

$\Rightarrow f - \phi \in {\varphi}^{\bot} , \phi \in \varphi (unique) \Rightarrow < f - \phi , \psi > = 0 , \forall \psi \in \varphi$

Inner Product :

$< x , y > = \sum^n_{i=1} x_i y_i = y^T x$

$< f , g > = \int f(x) g(x) dx$

2-norm

${\Vert x \Vert}^2_2 = < x , x > = \sum^n_{i=1} x^2_i ( {\Vert \cdot \Vert}_{l_2} )$
${\Vert f \Vert}^2_2 = < f , f > = \int 1^2 dx ( {\Vert \cdot \Vert}_{L_2} )$

${\Vert f - \phi \Vert}_2 = min \Vert f - \psi \Vert$

$\Rightarrow f - \phi \in {\varphi}^{\bot} , \phi \in \varphi (unique)$

$\Rightarrow < f - \phi , \psi > = 0 , \forall \psi \in \varphi$

If $\{ {\phi}_1 , \cdots , {\phi}_m \}$ are basis of $\varphi$ .

$\Rightarrow < f - \sum^m_{i=1} c_i {\phi}_i , {\phi}_i > = 0$ , $i = 1 , 2 , \cdots , m , \phi = \sum c_i {\phi}_i$

$\Rightarrow < f , {\phi}_i > = < \sum^m_{i=1} c_i {\phi}_i , {\phi}_i >$ , $i = 1 , 2 , \cdots , m$

( m equations )

$c_1 < {\phi}_1 , {\phi}_1 > + c_2 < {\phi}_2 , {\phi}_1 >$ , $\cdots , c_m < {\phi}_m , {\phi}_1 > = < f , {\phi}_1 >$

$c_1 < {\phi}_1 , {\phi}_2 > + c_2 < {\phi}_2 , {\phi}_2 >$ , $\cdots , c_m < {\phi}_m , {\phi}_2 > = < f , {\phi}_2 >$

$$\vdots$$

$c_1 < {\phi}_1 , {\phi}_m > + c_2 < {\phi}_2 , {\phi}_m >$ , $\cdots , c_m < {\phi}_m , {\phi}_m > = < f , {\phi}_m >$

cx = d

c = $\left [ \matrix{ < {\phi}_1 , {\phi}_1 > , < {\phi}_2 , {\phi}_1 > , \cdots , <... ...> , < {\phi}_2 , {\phi}_m > , \cdots , < {\phi}_m , {\phi}_m > \cr } \right ]$

$\left [ \matrix{ c_1 \cr c_2 \cr \vdots \cr c_m \cr } \right ] = \left [ \matrix{ < f , {\phi}_1 > \cr \vdots \cr < f , {\phi}_m > \cr } \right ]$

Note : c is 1. Symmetry . 2. Positive defined .