Search
Duplicate

김영길/ 선형대수학/ orthogonal complement, LU decomposition, least square, correlation matrix

Def

inner product space VV의 nonempty subset SS에 대하여, SS의 orthogonal complement(직교 여공간)는 다음과 같이 정의한다.
S={xVx,y=0,yS}S \bot = \{ x \in V | \langle x, y \rangle = 0, \forall y \in S \}
SS \botVV의 벡터 중에 SS의 모든 벡터들과 orthogonal한 것을 모아 놓은 집합
Ex 9)
V=R3,S={(0,0,1)}V = R^{3}, S = \{ (0, 0, 1) \} 일 때
S=xy planeS \bot = \text{xy plane}

Thm 6.7

WVW \subseteq V 일 때
dim(V)=dim(W)+dim(W)dim(V) = dim(W) + dim(W \bot)
Ex 11)
V=R3V = R^{3} 에서
W=span({(1,0,0),(0,1,0)})={(a,b,0)a,bR}W = span(\{(1, 0, 0), (0, 1, 0)\}) = \{(a, b, 0) | a, b \in R\} 이면
dim(W)=2dim(W) = 2
W={(0,0,c)cR}W \bot = \{ (0, 0, c) | c \in R \}
dim(W)=1dim(W \bot) = 1
Ex 12)
(Null space of AA)\bot = row space of AA
AA의 널공간은 AA의 모든 row와 수직인 것을 모아 놓은 것이 된다.
(Null space of AtA^{t})\bot = column space of AA
이것을 Left Null Space라고도 한다.

LU decomposition

n×nn \times n 정사각행렬 AA에 대하여
만일 row exchange를 하지 않고 AUA \to U를 만들 수 있으면
A=LUA = LU
LL 는 lower triangular matrix
UU 는 upper triangular matrix
(예시 생략)

Least square solution (최소제곱해)

overdetermined problems의 least square solution
Ax=bAx = b의 꼴에서 xx를 구할 수 없을 때
[12342042][x1x2]=[2103]\left[ \begin{array}{rrrr} 1 & 2 \\ 3 & 4 \\ 2 & 0 \\ 4 & 2 \end{array} \right] \left[ \begin{array}{rr} x_{1} \\ x_{2} \end{array} \right] = \left[ \begin{array}{rrrr} 2 \\ 1 \\ 0 \\ 3 \end{array} \right]
위와 같은 경우 해가 없다. (Inconsistent system)
이럴 때는 bb에 최대한 가깝게 xx 를 조정한다.
x^=argminxAxb2\hat{x} = \arg \min_{x} \| Ax - b \|^{2}
이때 bb 와 가장 가까워지는 x^\hat{x}는 (error vector - bb와의 간격이 error값이 된다) AA의 모든 벡터와 수직인 값이 된다. (거꾸로 말하면 AA의 모든 벡터와 수직이 되는 값을 찾으면 된다.)
(bAx^)aj(j)(b - A \hat{x}) \bot a_{j} (\forall j)

Orthogonality principle

앞서 살펴본 경우의 AA와 수직인 벡터를 찾는 방법
ajT(bAx^)=0(j=1,2,...,n)a_{j}^{T} (b - A \hat{x}) = 0 (j = 1, 2, ... , n)
[a1Ta2T...anT][bAx^]=[00...0]\left[ \begin{array}{rrrr} - & a_{1}^{T} & - \\ - & a_{2}^{T} & - \\ & ... & \\ - & a_{n}^{T} & - \end{array} \right] \left[ \begin{array}{rrr} | \\ b - A \hat{x} \\ | \end{array} \right] = \left[ \begin{array}{rrrr} 0 \\ 0 \\ ... \\ 0 \end{array} \right]
AT(bAx^)=0A^{T}(b - A \hat{x}) = 0
ATAx^=ATbA^{T} A \hat{x} = A^{T} b
AA가 full rank일 때
x^=(ATA)1ATb\hat{x} = (A^{T}A)^{-1}A^{T}b
AA의 Moore Penrose pseudo-inverse는 (ATA)1AT(A^{T}A)^{-1}A^{T}가 된다.
AA의 column space로 향하는 BB의 Projection
p=Ax^=A(ATA)1ATb=Pbp = A \hat{x} = A(A^{T}A)^{-1}A^{T}b = Pb
Projection matrix
P=A(ATA)1ATP = A(A^{T}A)^{-1}A^{T}
P2=PP^{2} = P
PP는 Projection 되었기 때문에 제곱해도 변하지 않는다.

Ex. Measurements

다음과 같이 점이 주어졌을 때
(x1,y1)=(1,1)(x_{1}, y_{1}) = (-1, 1)
(x2,y2)=(1,1)(x_{2}, y_{2}) = (1, 1)
(x3,y3)=(2,3)(x_{3}, y_{3}) = (2, 3)
y=C+Dxy = C + Dx가 되는 line을 찾으려고 한다. (error를 최소화하는 직선을 찾는 문제. 제곱은 결국 거리기 때문에 거리를 최소화한다는 의미에서 최소제곱을 찾는 문제이다)
[111112][CD]=[113]\left[ \begin{array}{rrr} 1 & -1 \\ 1 & 1 \\ 1 & 2 \end{array} \right] \left[ \begin{array}{rr} C \\ D \end{array} \right] = \left[ \begin{array}{rrr} 1 \\ 1 \\ 3 \end{array} \right]
ATA=[111112][111112]=[3226]A^{T}A = \left[ \begin{array}{rrr} 1 & 1 & 1 \\ -1 & 1 & 2 \end{array} \right] \left[ \begin{array}{rrr} 1 & -1 \\ 1 & 1 \\ 1 & 2 \end{array} \right] = \left[ \begin{array}{rr} 3 & 2 \\ 2 & 6 \end{array} \right]
ATb=[111112][113]=[56]A^{T}b = \left[ \begin{array}{rrr} 1 & 1 & 1 \\ -1 & 1 & 2 \end{array} \right] \left[ \begin{array}{rrr} 1 \\ 1 \\ 3 \end{array} \right] = \left[ \begin{array}{rr} 5 \\ 6 \end{array} \right]
ATAx^=ATbA^{T} A \hat{x} = A^{T} b
[3226][CD]=[56]\left[ \begin{array}{rr} 3 & 2 \\ 2 & 6 \end{array} \right] \left[ \begin{array}{rr} C \\ D \end{array} \right] = \left[ \begin{array}{rr} 5 \\ 6 \end{array} \right]
C=97,D=47C = {9 \over 7}, D = {4 \over 7}
y=97+47x\therefore y = {9 \over 7} + {4 \over 7}x

Unitary matrix

Unitary matrix란 Rows도 orthonormal이고 Columns도 orthonormal한 matrix를 말한다.
AA=AA=IAA^{\dagger} = A^{\dagger}A = I
det(A)=1det(A) = 1

Matrix in random processes

Random vectors의 Second-Moment Descriptions
Random vector z=[z(u,1)z(u,2)...z(u,n)]z = \left[ \begin{array}{rrrr} z(u, 1) \\ z(u, 2) \\ ... \\ z(u, n) \end{array} \right]
Mean vector MzM_{z}
Mz=[mz(1)mz(2)...mz(n)]=[E{z(u,1)}E{z(u,2)}...E{z(u,n)}]=E{z(u)}M_{z} = \left[ \begin{array}{rrrr} m_{z}(1) \\ m_{z}(2) \\ ... \\ m_{z}(n) \end{array} \right] = \left[ \begin{array}{rrrr} E\{z(u, 1)\} \\ E\{z(u, 2)\} \\ ... \\ E\{z(u, n)\} \end{array} \right] = E\{z(u)\}
Correlation matrix RzR_{z}
Rz=[Rz(1,1)Rz(1,2)...Rz(1,n)Rz(2,1)Rz(2,2)...Rz(2,n)...Rz(n,1)Rz(n,2)...Rz(n,n)]R_{z} = \left[ \begin{array}{rrrr} R_{z}(1, 1) & R_{z}(1, 2) & ... & R_{z}(1, n) \\ R_{z}(2, 1) & R_{z}(2, 2) & ... & R_{z}(2, n) \\ ... \\ R_{z}(n, 1) & R_{z}(n, 2) & ... & R_{z}(n, n) \end{array} \right]
=[E{z(u,1)z(u,1)}E{z(u,1)z(u,2)}...E{z(u,1)z(u,n)}E{z(u,2)z(u,1)}E{z(u,2)z(u,2)}...E{z(u,2)z(u,n)}...E{z(u,n)z(u,1)}E{z(u,n)z(u,2)}...E{z(u,n)z(u,n)}]= \left[ \begin{array}{rrrr} E\{z(u,1) z^{*}(u, 1)\} & E\{z(u,1) z^{*}(u, 2)\} & ... & E\{z(u,1) z^{*}(u, n)\} \\ E\{z(u,2) z^{*}(u, 1)\} & E\{z(u,2) z^{*}(u, 2)\} & ... & E\{z(u,2) z^{*}(u, n)\} \\ ... \\ E\{z(u,n) z^{*}(u, 1)\} & E\{z(u,n) z^{*}(u, 2)\} & ... & E\{z(u,n) z^{*}(u, n)\} \end{array} \right]
=E{[z(u,1)z(u,2)...z(u,n)][z(u,1)z(u,2)...z(u,n)]}= E \{ \left[ \begin{array}{rrrr} z(u, 1) \\ z(u, 2) \\ ... \\ z(u, n) \end{array} \right] \left[ \begin{array}{rrrr} z^{*}(u, 1) & z^{*}(u, 2) & ... & z^{*}(u, n) \end{array} \right] \}
=E{z(u)z(u)}= E\{z(u)z^{\dagger}(u)\}