Orthogonal Vector and Subspace

Orthogonal Vector

직교(Orthogonal)한다는 것은 수직(Perpendicular)과는 다른 의미이다.
Orthogonal은 두 벡터의 내적이 0인 것을 의미한다.
즉, 영벡터도 포함된다.
수직은 의미가 조금 다르다.

증명은 피타고라스 정리로 할 수 있다.

Norm

L-1 Norm, L-2 Norm …
L-0 Norm이란건 원래 없지만 관례적으로 0이 아닌 벡터의 갯수를 나타냄.

벡터의 곱

\(x^Tx\) 와 같은 형태로 나타낼 수 있음.
이는 \({||x||}^2\)와 같음.

Orthogonality of subspaces

subspace들의 orthogonality는 각 subspace에 속하는 어떤 임의의 벡터 v, w에 대해서도 vw=0이 성립하여야 한다.

Orthogonality in row space and null space

Row space의 차원 + null space의 차원 = n

Row space와 null space는 \(R^n\) 차원에서 정의되며, 서로 직교하며 이 공간을 두개의 수직인 공간으로 나눈다. 이 둘은 서로의 보완재(complements)이다.

Orthogonality in column space and left null space

Column space의 차원 + Left null space의 차원 = m

마찬가지.

Ax=b with no solution, Overdetermined case

Solving Ax=b when there is no solution

이 때 가장 근사한 해를 구하는 것이 목표가 될 수 있다.
미지수의 갯수보다 방정식이 더 많은 경우 이를 overdetermined라고 한다.(m > n) 이 때 rank는 최소 n이어야 한다. 즉, Full column rank여야 한다

A가 m x n 행렬이고 m > n 일 때, 이는 overdetermined하다.

\(A^TA\) 는 Symmetric한 Square matrix가 되는데,
이는 역행렬이 존재한다.

\(Ax=b\)
는 해가 존재하지 않는다.

\(A^TA\hat{x}=A^Tb\)
는 이를 만족시키는 \(\hat{x}\) 해가 존재한다.

여기서 \(\hat{x}\)의 의미는 \(Ax=b\)의 최고로 근사한 해라는 것으로, 최적해(best solution)이라고 한다.

양변에 \((A^TA)^{-1}\)을 곱하여
\(\hat{x}=(A^TA)^{-1}A^Tb\)
로 Best solution을 찾을 수 있다.

가장 error가 작은 해를 찾는 것이 best solution이다.

overdetermined case라고 해도 해가 존재할 수도 있는데, 이런 경우에는 Best solution이 실제 solution과 같다.

Not invertible case

Overdetermined case에서 Full column rank가 아닌 경우 Best solution조차 찾을 수 없다.

\(A^TA\) 는 n x m 에 m x n 행렬을 곱한 것으로 결과는 n x n 이다.
만약 rank가 n보다 작으면 \(A^TA\)의 rank도 n보다 작으며, 이 때문에 역행렬이 존재하지 않아 Best solution을 찾을 수 없다.

결론적으로 \(A^TA\)가 역행렬을 가지기 위해선 이것이 Full rank여야하는데, 이는 A가 Full column rank, 즉 column이 독립이어야 한다는 것이다.

그런데 Full Rank가 아니어도 구할 수 있는 방법이 Moore-Penrose psuedoinverse 방법이다.
Moore-Penrose psuedoinverse

\(A^TA\)가 Full Rank이면, \(A^TA\hat{x}\)에 대해 우변에 어떤 b가 나와도 해가 하나 존재한다.

Projection matrix and Subspaces

2D-Vector Projection

하나의 벡터를 다른 벡터에 투영시키는 것을 Vector projection이라고 한다.

벡터 b에서 벡터a로 투영한 벡터를 p(=xa, x는 스칼라), a와 수직하는 b와 p를 잇는 점이 e(=b-p)라고 하자.
이는 xa인 벡터들 중 b와 가장 가까운 벡터를 찾는 것과 같다. 이를 만족시키는 스케일 상수 x를 찾는 것이 vector projection의 핵심이다.
e는 error라고 한다. 투영 후와 투영 전의 거리상 차이를 나타내기 때문이다.

벡터 a와 e가 수직임을 이용해 이를 찾아낼 수 있다.
\(a^Te=0\)
\(a^T(b-xa)=0\)

이를 전개하면,
\(a^Tb-xa^Ta=0\)
\(xa^Ta=a^Tb\)
\(x=\frac{a^Tb}{a^Ta}\)

dot product로 표현하면,
\(x=\frac{a\dot b}{a \dot a}\)

결국 투영벡터인 p는,
\(p=xa\)
\(p=(\frac{a^Tb}{a^a})a\)
이다.

Projection matrix of n-dimensional vectors

이를 투영행렬(projection matrix)로 표현해보자.
위에서 p=xa로 표현을 하였는데, x는 스칼라이므로 p=ax로 표현할 수 있다.
\(p=ax\)
\(p=a \frac{a^Tb}{a^Ta}\)

행렬 곱셈은 결합법칙이 성립하므로,
위의 식을 투영되는 대상인 벡터 b에 대한 식으로 나타내면,
\(p=\frac{aa^T}{a^Ta}b\) \(p=Pb\)
\(P=\frac{aa^T}{a^Ta}\)
가 된다.

여기 P가 Projection Matrix이다.
\(aa^T\)는 column*row이므로 matrix가된다.

궁금증: 단위를 맞춰주기 위해선 \(a^Tb\) 벡터 내적 결과에 제곱근을 취해주어야 하는 게 아닐까?

Properties of projection matrix

어떤 행렬 A가 있을 때 A의 column vector들의 Linear combination을 통해 만들 수 있는 공간을 column space라고 하였다.
행렬 A에 벡터 x를 곱하는 것은 무엇을 뜻할까?
A에 곱해진 벡터 x가 A의 column space에 안착(landing)하는 것을 의미한다.

그러면 투영행렬 P의 column space는 무엇일까? 바로 벡터 a를 지나가는 Line이라는 것을 의미한다.

여기서 rank 1의 의미가 나온다.
Rank 1

Rank 1 행렬은 Column Space가 \(R^m\)에서 정의된 직선임을 의미한다.

\(aa^T\)는 column x row 이므로 투영행렬이 rank 1이 되고, 벡터 a는 행렬 P의 column space의 기저(basis)가 된다.

투영 행렬은 Symmetric하다.

N-Dimensional Vector Projection

\(Ax=b\)가 해가 존재하지 않는다면, 근접해 \(\hat{x}\)를 구할 수 있다,
\(A\hat{x}=Pb=p\), p가 b의 column space로의 projection일 때.

\(Ax=b\)가 해가 존재하지 않는다는 것은 b가 A의 column space상에 존재하지 않는다는 것이다.
그래서 column space에서 가장 근접한 해를 찾기 위해 Projection을 구하는 것이다.

평면에 대한 Projection은 어떻게 할까?

\(p=A\hat{x}\), Find \(\hat{x}\)

Key Point,
\(b-p\)
\(b-A\hat{x} \perp\) plane

이는 a1과 a2 두개의 방정식에 대해 정리할 수 있다.

A가 a1과 a2 두개의 column vector로 이루어져있고, x hat도 x1과 x2로 이루어져 있기 때문이다.
오차에 대한 라인 e가 a1에도 수직이고 a2에도 수직이라는 의미이다.

a1과 a2에 모두 수직이면 a1, a2의 LC로 이루어진 모든 평면에 대해서도 수직이다.

\(a_1^T(b-A\hat{x})=0\), \(a_2^T(b-A\hat{x})=0\)

\(\begin{bmatrix} a_1^T \\ a_2^T \\ \end{bmatrix} (b-A\hat{x}) = \begin{bmatrix} 0 \\ 0 \\ \end{bmatrix}\)
\(A^T(b-A\hat{x})=0 \cdots(1)\)
\(A^TA\hat{x}=A^Tb\)

(1)은 Left null space의 형태와 같다. 따라서 오차 벡터\(e=b-A\hat{x}\) 는 행렬 A에 대한 Left null space에 존재한다.
또한 Left null space는 A의 column space와 직교하는데, 잘 생각해보면 A의 column space가 바로 투영의 목적지인 평면과 같다고 볼 수 있다.

\(e\) is in \(N(A^T)\)
\(e \perp C(A)\)
이 관계로부터 모든 것이 나온다.

Solution of the x hat and projection matrix

이제 이를 통해 \(\hat{x}\)의 solution을 구해보자.

\(\hat{x}=(A^TA)^{-1}A^Tb\)
\(p=A\hat{x}=A(A^TA)^{-1}A^Tb\)
\(P=A(A^TA)^{-1}A^T\)
\(p=Pb\)

같은 공간에 있는 어떤 벡터든지 Projection matrix를 곱하면 행렬 A의 column space로 landing한다.
위의 식들은 바로 N차원에 대한 투영 행렬을 구하는 일반적인 방법을 의미한다.

만약 A가 정방행렬이고 invertible하면 전개했을 때 P=I가 된다.
하지만 overdetermined case와 같은 경우에 역행렬이 존재하지 않기 때문에 P는 I와 다르다.

또한 Projection Matrix는 Transpose시켜도 변하지 않는다. 즉, Symmetric하다.

또한 Projection Matrix는 제곱시켜도 변하지 않는다.

Projection and Least Square Method

투영을 다시 복습해보자.

Projection

Two extreme cases

\(P=A(A^TA)^{-1}A^T\)
벡터 b를 A의 column space에 존재하는 가장 가까운 벡터로 바꿔준다.

벡터 b가 이미 column space에 존재한다면? 그대로 b가 나온다. 이 때는 Ax=b의 해가 존재하니까.

벡터 b가 column space와 수직이라면? 영벡터가 나온다. 이 때 b는 A의 Left null space에 존재한다.
\(b = p + e\)
\(p = Pb\)
\(e = b - p = (I - P)b\)

Least Square Method

Basics of Least Square

Linear Regression 풀 때 사용.

\[Ax=b\]

이 때 A가 overdetermined라서 해가 존재하지 않으면, Full rank인 경우 다음으로 근사시켜 풀 수 있다.

\[A^TA\hat{x}=A^Tb\]

이처럼 해가 존재하지 않는다면, 데이터와 직선 사이의 에러의 총합이 최소가 되게끔 하는 선에 근사시키는 것이 목적이 된다.

여기서 오차(error)를 구체적으로 정의해보자.

\(y=ax+b\) 표기를
\(b=ct+d\) 바꾸어 표현하겠다.

c, d의 파라미터 값을 추정하였을 경우 좌변의 b와 우변의 ct+d의 차이를 계산한 것이 error이다.
error는 제곱을 해주어야하는데, 음수값이 나올 수도 있기 때문이다.
이 error를 최소화하는 c,d를 찾는 것이 목표이다.

이를 식으로 표현하면 다음과 같다.

Minimize \(\sum_{j=1}^{m}(ct_j+d-b_j)^2 \cdots (1)\)

이는 미적분을 통해 각 c, d에 대한 편미분이 =0이 되도록 정리하면 c와 d에 대한 식을 구할 수 있다.
이제 이를 행렬식으로 다시 표현해보자.

Minimize \(\|Ax-b\|^2=\|e\|^2 \cdots (2)\)

Ax-b 벡터의 2-norm의 제곱이 최소가 되는 것을 찾는 것이다.
Ax-b 벡터의 길이 자체가 에러의 크기를 나타낸다!

(1)은 (2)의 Ax-b의 각 j번째 row의 차이를 제곱한 것을 전부 summation한 것이다. 즉, Ax-b의 2-norm의 제곱이라는 뜻이다.

LSM을 정의하면 다음과 같다.
주어진 모든 데이터에 대하여, predicted value와 measured value사이의 error의 제곱의 합을 최소화 하는 parameter를 찾는 방법

그렇기 때문에 Line fitting은 리그레션 라인에 대한 수직선을 긋는 것이 아닌, y축에 대한 차이만을 제곱하여 더하는 것이다.

에러의 총합은 각 점과 라인과의 차이의 제곱의 총합이다.
overall error = \({e_1}^2 + {e_2}^2 + {e_3}^2\)

Outliers in Least square

아웃라이어와의 에러를 고려하다보니 Line Fitting을 잘 반영하지 못하는 경우를 overcompensate되었다고 표현한다.
overcompensate를 해결하기 위해서는 Random Sample Consensus(RANSAC) 등의 방법이 존재한다.

Solution of Least square

\(Ax=b\)

b를 A의 column space로 투영시키면

\[A\hat{x}=p\] \[A^TA\hat{x}=A^Tb\]

\(\hat{x}\)의 각 entry가 (변수가 하나라면 직선의)방정식을 만드는 parameter가 된다.
\(\hat{x}= \begin{bmatrix} \theta_0 \\ \theta_1 \\ \end{bmatrix}\)

\(p=\theta_1 t + \theta_0\)
\(e=b-p\)

Error vector

원래의 데이터 값인 b벡터는 에러 벡터인 e와 투영 벡터인 p의 합으로 이루어져있다.
즉, b=e+p이다.

이를 개개의 데이터가 아닌 벡터의 기준으로 생각해보자. p는 e와 직교한다.
e가 최소가 되려면 A의 column space와 직교해야하기 때문이다.

실제로 LSM으로 계산해보면 e의 값이 p와 직교한다는 것을 알 수 있다.

벡터의 기준으로 다음과 같이 표현할 수 있다.
\(b = e + p\)
\(e \perp p\)

여기서 e는 p와만 직교한 것이 아니라, p가 존재하는 A의 column space 전체와 직교한다.
이처럼 어떤 벡터를 다른 공간의 성분의 벡터와 그와 직교하는 성분의 벡터로 나누는 것이 가능하다.

핵심 방정식 정리
\(A^TA\hat{x}=A^Tb\)
\(A\hat{x}=Pb=p\)

마지막으로 \(A^TA\)의 역행렬이 존재해야 \(\hat{x}\)를 찾을 수 있는데, 그러기 위해선 A의 column vector들이 독립해야 한다는 것이다. 그렇지 않으면 해를 구할 수 없다. Full column Rank의 조건을 기억하자.

A의 Column space와 P의 Column space는 같다.
P는 Symmetric matrix이므로 P의 column space와 row space는 같고, P의 row space와 A의 Column space는 같다.

Orthogonal Matrices

Orthonormal Vector

Unit Vector

단위벡터(Unit vector): \(\hat{v}=\frac{v}{\|v\|}\)

이는 정규화 벡터(Normalized vector)라고도 한다.

Orthonormal vector

정규직교벡터는 벡터들이 서로 직교하면서, 각 벡터의 길이가 1인 벡터를 의미한다.

어떤 벡터는 다른 벡터와의 내적을 할 시 0이 되고, 자기 자신과의 내적만이 1을 나타낸다.

Orthonormal vector들을 행렬의 column vector에 삽입하면 직교행렬이 되고, 이를 Q라고 할 때, orthonormal vector들이 Q의 정규직교기저가 된다.
Numerical Linear Algebra의 대부분의 연산은 orthonormal vector를 기반으로 이루어진다.

square가 아닌 경우 row 기준으로 생각해서는 안된다.

Orthogonal Matrices

Basic of Orthogonal Matrix

\(Q^TQ=I\)
벡터들은 자기 자신과의 내적만 1이기 때문이다.

Square Orthogonal Matrix

\(Q^TQ=I\) 이고, Square Matrix 이므로,
\(Q^T=Q^{-1}\)

Block Matrix로 구성해도 직교행렬이다.
그런걸 Adhemar matrix라고 한다.

Rectangular Orthogonal Matrix

column에 하나씩 끼워넣을 때, 어떻게 이전의 vector들과 orthonormal한 관계의 vector를 찾아서 끼워넣을 수 있을 까?

이를 위해 사용하는 것이 Gram-Schmidt Process이다.

Advantage of using Orthogonal Matrix

\(P=A(A^Ta)^{-1}A^T\)

이를 Q를 이용해 투영행렬을 만들면?

if Q is orthogonal matrix then, \(P=Q(Q^TQ)^{-1}Q^T=QQ^T\)

Q는 orthogonal matrix인데, orthogonal matrix의 특성에 따라 아주 간단하게 정리될 수 있다. 이 때 Q가 임의의 rectangular matrix라면 P는 symmetric matrix가 된다.

Q가 square matrix라면?
\(P=QQ^T=I\)

원래 투영 행렬은 b를 A의 column space로 투영시키는 역할을 하는데, Q가 정방행렬이 되어버리면, Q의 column space가 전체 공간과 같아져버린다.

마지막으로 Projection matrix의 특성인 제곱을 살펴보자. \(P^2=P\)
\((QQ^T)(QQ^T)=QQ^T\)

Solution을 구하는것도 간단해진다.

\[A^TA\hat{x}=A^Tb\]

\(Q^TQ\hat{x}=Q^Tb\)
\(\hat{x}=Q^Tb\)

A가 Q와 같은 column space를 공유하도록 A의 column vector들을 기반으로 A와 같은 column space, 혹은 subspace를 이루는 행렬 Q를 만들어 낼 수 있다면 계산이 정말 편리해지는 것이다. Gram Schmidt 과정은 이것을 해낼 수 있다. 이 때 A의 column space들은 독립이어야 한다.

Gram Schmidt Process

Independent Vector를 Orthogonal Vecotr로 만들고, 이를 Normalize하여 Orthonormal Vector로 만드는 것이 Gram-Schmidt Process이다.

행렬 단위의 Normalization이라고 보면 될것 같다.(개인적인 생각임)

Making Orthogonal Vectors

어떤 벡터를 다른 벡터의 성분과, 그와 직교하는 성분으로 분해하는 것이 projcetion 과정이다.

여기서 a, b, c 벡터를 q1, q2, q3로 만들어 보자.

a는 바로 q1이 된다.

먼저 q1에 대해 q2를 생성하자.
벡터를 벡터에 투영하는 식을 떠올려보자.

\(e = b-p\)
\(q_2=b-\frac{q_1^Tb}{q_1^Tq_1}q_1\)

b에서 projection 벡터를 빼면 그게 q1과 직교하게 된다. 그것을 q2로 삼자.

이와 같이 q3도 생성할 수 있는데, q1과 q2에 대해 각각 해주어야한다.

\(e_{c1} = c-p\)
\(e_{c1}=c-\frac{q_1^Tc}{q_1^Tq_1}q_1\)

이러면 q1과 직교하는 벡터 \(e_{c1}\)이 생성된다.
이를 또 q2에 투영시켜 \(e_{c2}\)를 구해 직교하게 해보자.

\(e_{c2} = e_{c1}-p\)
\(e_{c2}=e_{c1}-\frac{q_2^Te_{c1}}{q_2^Tq_2}q_2\)

이 때 a,b,c가 각각 독립이어야 한다.

그리고 q3를 만들 때, c를 q1과 직교하는 성분을 찾고, 그다음 q2와 직교하는 성분을 각각 찾기 때문에(없는 성분을 추가하는게 아니기 때문에) e_c1은 q1과 직교하는 subspace에 존재하고, 이 subspace에는 q2도 존재한다. 그러니 q2 방향에 해당하는 성분을 빼더라도 여전히 같은 subspace에 존재하고, 이는 q3가 여전히 q1과 직교한다는 것을 의미한다.

Making Orthonormal Vectors

이제 q1, q2, q3를 전부 Normalize하면 된다.

Subspaces

기존의 행렬 A를 통해 직교행렬 Q를 만들게 되면, A와 Q는 같은 column space를 공유하게 된다.

A의 column vector를 LC하여 Q를 만들기 때문이다.

QR Decomposition

QR decomposition basic

\(A=QR\)

QR decomposition wiki
QR decomposition은 eigenvalue algorithm의 기본이 되기도 한단다.

링크에서 확인 Link