7강: 벡터와 직교분해

벡터(Vector)

벡터 : 길이와 방향의 물리량

벡터의 내적(inner product 또는 dot product)

• 좌표계 없이 표현

  두 $n$-벡터의 길이와 두 벡터 간의 사이각 $\theta$ 을 통해 다음과 같이 정의된다.

  $u \sdot v=\|u\|\|v\|\cos\theta$

• 좌표게를 도입하여 표현

  $u=(u_1, u_2, \dots, u_{n}), v=(v_1, v_2, \dots,v_{n})$의 좌표값을 통해 다음과 같이 계산된다.

  $u \sdot v = u_1v_1+u_2v_2+\dots+u_{n}v_{n}$

벡터의 내적 - 두 벡터의 내적이 0이면 두 벡터는 직교(orthogonal)이다.

$u \perp v$ 일 때, $u$ 방향으로의 전진은 $v$ 방향에서 전혀 측정되지 않는다. 그 반대도 마찬가지.

(고교 과정에서 배운 $xy$-좌표계나 $xyz$-좌표계는 직교좌표계)

투영(Projection)

투영 : 어떤 벡터의 주어진 방향에의 성분을 구하는 것

👇($u$를 $A$x=$b$에서의 $b$로 생각해도 무방!)

두 벡터 $u$, $a$ 가 있을 때

벡터 $u$를 $a$ 위에 투영한 벡터를 $proj_{a}u$라 하고 다음과 같이 구한다.

벡터 u를 a위에 투영하고 남은 보완 벡터(complement vector)는 $u-proj_au$ 이다

벡터 $u$에서 $u$를 $a$에 투영한 벡터를 빼면

$u$를 $a$에 투영한 벡터에서 $u$를 가리키는 벡터를 구할 수 있음. 이것이 보완 벡터!

투영한 벡터와 보완 벡터는 직교한다!

📌정리

1. 투영(projection) 벡터와 보완(complement) 벡터는 직교한다.

   $proj_au \perp (u-proj_au)$

2. 투영(projection) 벡터와 보완(complement) 벡터를 합하면 원래 벡터를 구할 수 있다.

   $u=proj_au+(u-proj_au)\\\:(projection)\;+\;(complement)$

   (원래 벡터는 투영 벡터와 보완 벡터로 나눌 수 있고, 이 나눔은 직교성을 보장한다)

🔥투영과 보완의 개념을 이용하여 직교분할이 가능하다!

직교행렬(Orthogonal Matrix)

행렬 : 각 열벡터가 기저(basis)를 이루는 좌표계

직교행렬(orthogonal matrix)

행렬의 모든 열벡터가 서로 직교하는 행렬

직교행렬은 직교좌표계를 의미

정규직교행렬(orthonormal matrix)

행렬이 직교행렬이고 모든 열벡터의 길이가 1인 행렬

정규직교행렬은 정규직교좌표계를 의미

직교행렬을 이용한 선형시스템

일반적인 행렬(직교행렬이 아닌 행렬)에서는

각 열벡터들이 서로 연관성을 가지고 있어서 해를 구하기가 어려움

(첫 번째 열벡터와 두 번째 열벡터를 각각 얼마큼 쓰냐에 대해서 연관성이 존재 → 첫 번째 열벡터를 많이 쓰면 두 번째 열벡터는 적어지고, 첫 번째 열벡터를 조금 쓰면 두 번째 열벡터는 많이 쓰게 됨)

• 직교행렬(orthogonal matrix)

  선형시스템 $Ax = b$에서 행렬 $A$가 직교행렬이면, $x$는 역행렬 $A^{-1}$의 계산 없이 다음과 같이 구할 수 있다.

  • $x$의 $i$-번째 요소는 투영(projection)으로 계산할 수 있다.

    → 벡터 $b$를 행렬 $A$의 각 열벡터 $a_{i}$에 투영한 $proj_{a_i}b$ 로부터 다음을 계산할 수 있다.

    $proj_{a_i}b=\frac{b \sdot a_i}{\|a_i\|^2}=x_i$

• 정규직교행렬(orthonormal matrix) (==회전행렬)

  선형시스템 $Ax = b$에서 행렬 $A$가 정규직교행렬이면, $x$는 역행렬 $A^{-1}$의 계산 없이 다음과 같이 구할 수 있다.

  • $x$의 $i$-번째 요소는 투영(projection)으로 계산할 수 있다.

    → 벡터 $b$를 행렬 $A$의 각 열벡터 $a_{i}$에 투영한 $proj_{a_i}b$ 로부터 다음을 계산할 수 있다.

    $proj_{a_i}b=b \sdot a_i=x_i$

    정규직교행렬에서 모든 $a_i$(행렬 $A$의 열벡터)의 길이 $\|a\|$ 는 1이기 때문에 내적만 수행하여도 된다.

📌직교행렬의 장점

🔥1. 역행렬 계산 없이 해를 구하는 것이 가능

🔥2. $x_i$ 와 $x_j$의 계산은 독립적 → x의 계산은 병렬처리가 가능

QR 분해

주어진 행렬을 직교행렬로 만들 수 있으면 직교행렬의 장점을 이용할 수 있음.

QR 분해

: 주어진 행렬 $A$에서 정규직교행렬 $Q$ 와 그 나머지 $R$을 추출하는 행렬분해

• Q: 행렬 $A$에서 정규직교성을 추출한 정규직교행렬
• R: 행렬 $A$에서 정규직교성을 추출 후 남은 나머지들(residual), (상삼각행렬 모양)

1. $Q$ (정규직교행렬)로부터에서 내적을 이용하여 풀고
2. $R$ (상삼각행렬)에서 후방대치법을 이용하여 연산

→ LU 분해와 유사

📌QR분해의 의미

QR 분해는 주어진 행렬에서 정규직교성을 추출하여 계산의 편의를 도모함

QR 분해의 활용

• 빠른 계산

  : 선형시스템 $Ax = b$의 해를 구할 때, 정규직교행렬 Q를 이용한 계산 부분은 병렬처리로 빠르게 계산 가능. (하지만 R을 이용한 계산 부분은 병렬처리 불가!)

• ⚡$b$가 자주 업데이트 되는 경우 # LU분해와 동일

  : 선형시스템 $Ax=b$에서 행렬 $A$는 고정되어 있고 $b$가 자주 변하는 문제가 종종 있음. 이런 경우, 행렬 A를 미리 $QR$로 분해해두면 $b$가 업데이트될 때마다 선형시스템의 해 $x$를 실시간으로 구할 수 있음

QR 분해 vs LU 분해 (각 단점)

• $LU$ 분해의 경우, 선형시스템을 풀 때 병렬처리 불가능
• $QR$ 분해의 경우, $Q$ 행렬이 꽉찬 구조를 가진 행렬이므로 메모리 사용량이 많음

8강: SVD, PCA

특이값 분해(SVD, Singular Value Decomposition)

$LU$ 분해와 $QR$분해는 $n\times n$ 정방행렬(square matrix)에 대한 행렬분해인 반면,

특이값 분해는 일반적인 $m \times n$ 행렬에 관한 행렬 분해이다.

👉특이값 분해는 직교분할, 확대축소, 차원변환 등과 관련이 있다.

특이값 분해는 주어진 아래의 형태를 가지는 세 행렬의 곱으로 나누는 행렬분해이다.

![https://velog.velcdn.com/images%2Fleeyongjoo%2Fpost%2F2ec6fb15-19dc-425d-9f64-8096a9b55493%2Fimage.png%5D(https%3A%2F%2Fimages.velog.io%2Fimages%2Fleeyongjoo%2Fpost%2F2ec6fb15-19dc-425d-9f64-8096a9b55493%2Fimage.png)

• $U$: $m$차원 회전행렬 (정규직교행렬)
• $D$: $n$차원 확대축소 (확대축소 크기에 따른 정렬 형태)
• $V$: $n$차원 회전행렬

$V → D → U$ 방식으로 구성됨

특이값 분해 예제

![https://velog.velcdn.com/images%2Fleeyongjoo%2Fpost%2F742dd28f-dcce-4fc6-9eda-cb6cca67eb62%2Fimage.png%5D(https%3A%2F%2Fimages.velog.io%2Fimages%2Fleeyongjoo%2Fpost%2F742dd28f-dcce-4fc6-9eda-cb6cca67eb62%2Fimage.png)

특이값 분해 의미

![https://velog.velcdn.com/images%2Fleeyongjoo%2Fpost%2F47584678-486b-4b07-9787-1385fb8b4d0e%2Fimage.png%5D(https%3A%2F%2Fimages.velog.io%2Fimages%2Fleeyongjoo%2Fpost%2F47584678-486b-4b07-9787-1385fb8b4d0e%2Fimage.png)

특이값 분해 활용

A의 특이값 분해 U, D, V는 각각 열벡터의 순서대로

행렬 A의 열벡터가 어떤 방향으로 강한 응집성을 보이고 있는지를 분석한 것

U, D, V의 열벡터 순서대로 p 개 취한다면, 강한 응집성을 가지는 p개의 방향으로 수선의 발을 내린 $A$의 근사치 $A\rq$를 재구성할 수 있다.

(강한 응집성이라는 것은 원래 행렬에 대해서 가장 높은 응집성을 가진 방향을 의미! D 행렬이 정렬이 되어있다고 했는데, 큰 것부터 작은 것으로 정렬되어있을 때 수치가 가장 큰 부분 → 첫 열벡터)

응집성이 가장 강한 부분의 값이 높을수록 응집성이 강하다고 할 수 있음!

주성분분석(Principal Component Analysis, PCA)

다수의 n차원 데이터에 대해, 데이터의 중심으로부터 데이터의 응집력이 좋은 n개의 직교 방향을 분석하는 방법

주성분분석은 데이터의 공분산행렬(covariance matrix)에 대한 고유값 분해에 기반을 둔 직교분해이다.

공분산행렬(covariance matrix) : 중심으로부터 각각의 데이터가 어느 방향으로 뻗어 나가있는 지에 대한 외적행렬을 구하고, 외적행렬의 합을 도출

![https://velog.velcdn.com/images%2Fleeyongjoo%2Fpost%2Ff62ebc49-9a9d-4692-a9f1-d55b99299042%2Fimage.png%5D(https%3A%2F%2Fimages.velog.io%2Fimages%2Fleeyongjoo%2Fpost%2Ff62ebc49-9a9d-4692-a9f1-d55b99299042%2Fimage.png)

빨간색 벡터는 응집력이 높고, 파란색 벡터는 응집력이 낮음 (서로 직교)

![https://velog.velcdn.com/images%2Fleeyongjoo%2Fpost%2F1f916f00-7e4c-42e0-9db0-15390e9d7f6e%2Fimage.png%5D(https%3A%2F%2Fimages.velog.io%2Fimages%2Fleeyongjoo%2Fpost%2F1f916f00-7e4c-42e0-9db0-15390e9d7f6e%2Fimage.png)

![https://velog.velcdn.com/images%2Fleeyongjoo%2Fpost%2Fff051e52-dba0-4ef0-be2c-027c8bda9016%2Fimage.png%5D(https%3A%2F%2Fimages.velog.io%2Fimages%2Fleeyongjoo%2Fpost%2Fff051e52-dba0-4ef0-be2c-027c8bda9016%2Fimage.png)

다음과 같은 데이터가 있을 때, 공분산행렬과 이에 대한 주성분분석(PCA)는 다음과 같다.

![https://velog.velcdn.com/images%2Fleeyongjoo%2Fpost%2Fb856826e-732f-469e-b5eb-c940b04ceb5c%2Fimage.png%5D(https%3A%2F%2Fimages.velog.io%2Fimages%2Fleeyongjoo%2Fpost%2Fb856826e-732f-469e-b5eb-c940b04ceb5c%2Fimage.png)

*$W^{T}$ 는 Transpose(전치)

모든 데이터에 대해서 각각 외적을 하고 합을 구하면 $\begin{bmatrix}28 & 18\\18&12\end{bmatrix}$ 가 나오게 되는데

여기서 6개의 데이터니까 그 수만큼 나누어서 평균을 구함(1/6)

📌 외적

$\begin{pmatrix}2,1\end{pmatrix}$ 데이터에 대한 외적은 $\begin{bmatrix}2\\1\end{bmatrix} \begin{bmatrix}2&1\end{bmatrix}$ 외적을 하면 $\begin{bmatrix}4&2\\2&1\end{bmatrix}$ 이 나오게됨

• W → 빨간색 벡터와 파란색 벡터를 그림
• D → 빨간색 백터는 6.3 만큼, 파란색 벡터는 0.55 만큼 증폭

👉차원축소를 한다면 빨간색 벡터만 남기고 파란색 벡터 없애도 데이터를 표현하는데에 있어서 어느정도 오차는 있겠지만 받아들일 수 있는 적은 오차이어서 가능하다.

9강: 벡터공간과 최소제곱법

집합(set) : 임의의 원소(element)를 수집하여 만든 모임

"집합이 OO연산에 닫혀 있다" == 연산을 수행 후 결과가 원래 집합에도 포함되어 있다.

예시)

1. ${\{x|x\in R(실수)\}}$ → 덧셈 연산, 곱셈 연산에 닫혀 있다.
2. $\{{-1,0,1}\}$ → 덧셈 연산은 닫혀있지 않고, 곱셉 연산에는 닫혀 있다.

공간(Space)

공간(space)은 다음 두 연산에 닫혀 있는 집합이다.

• 덧셈연산에 닫혀 있다

  : 집합에서 임의의 두 원소 x, y를 뽑아 더해도 그 결과인 x + y는 집합의 원소이다.

• 스칼라 곱 연산에 닫혀 있다

  : 집합에서 임의의 한 원소 x를 뽑아 임의의 스칼라 s배 한 결과인 sx는 집합의 원소이다.

🤔선형함수의 조건이랑 같은 듯?

👉모든 $n$-벡터 집합 $\mathbb{R}^n$ 은 n차원 벡터 공간(vector space)라 부를 수 있다.

열공간(Column Space)

행렬 A의 열벡터들에 대한 가능한 모든 선형조합의 결과를 모아 집합으로 구성한 것

![https://velog.velcdn.com/images%2Fleeyongjoo%2Fpost%2Fdfd422e8-fbbc-4d9a-9b2f-925a296abe52%2Fimage.png%5D(https%3A%2F%2Fimages.velog.io%2Fimages%2Fleeyongjoo%2Fpost%2Fdfd422e8-fbbc-4d9a-9b2f-925a296abe52%2Fimage.png)

$Ax = b$ 에서

A의 열벡터를 조합해서 b를 만들 수 있으면 해가 존재한다.

→ 열공간에 존재하면 해가 존재한다.

최소제곱법(Least Squares Method)

최소제곱법의 의미

선형시스템 Ax = b에 대한 해가 없음에도 불구하고, 우리가 할 수 있는 최선이 무엇인가

b가 A의 열공간에 없기 때문에 풀 수 없지만 제일 가까운 지점은 찾을 수 있다.

![https://velog.velcdn.com/images%2Fleeyongjoo%2Fpost%2Fa79a56fd-8782-45bd-9bdc-ddbba7ad2746%2Fimage.png%5D(https%3A%2F%2Fimages.velog.io%2Fimages%2Fleeyongjoo%2Fpost%2Fa79a56fd-8782-45bd-9bdc-ddbba7ad2746%2Fimage.png)

행렬 A가 정의하는 열공간에서 우리의 목표 b와 가장 가까운 지점은 b를 열공간에 투영(projection)한 지점일 것이다.

→ b를 A의 열공간 col(A)로 투영(projection)

즉, 달성가능한 최선의 목표 $proj_wb$ 를 생각할 수 있다.

최소제곱법(Least Squares Method)

최소제곱법은 선형시스템 Ax=b 에 대한 해 x가 없음에도 불구하고

할 수 있는 최선의 대안 $\bar{x}$를 내놓는 기법이다.

최소 제곱법은 원래의 선형시스템 $Ax=b$가 아닌 다음의 선형시스템을 해결한다.

$A\bar{x}=\bar{b} \hspace{1em}(단,\;\bar{b}=proj_wb)$

이 방법은

원래 목표 $b$ 와 달성 가능한 목표 $\bar{b}$의 차이를 나타내는

벡터 (b-\bar{b})의 제곱길이를 최소화시키는 의미를 가지기 때문에 최소제곱법(least square method)

최소제곱법의 해 구하기

주어진 선형시스템의 양변에 전치행렬 $A^{T}$를 곱하면 최소제곱법의 해를 구할 수 있다.

![https://velog.velcdn.com/images%2Fleeyongjoo%2Fpost%2Fa360b30f-ecb6-4165-aa93-2c7474bb2ae9%2Fimage.png%5D(https%3A%2F%2Fimages.velog.io%2Fimages%2Fleeyongjoo%2Fpost%2Fa360b30f-ecb6-4165-aa93-2c7474bb2ae9%2Fimage.png)

최소제곱법 응용: 선형회귀

선형회귀 문제는 다음과 같이 최소제곱법으로 풀 수 있다.

1. 선형시스템 구성

   : 직선이 각 정점을 모두 지나간다고 가정하고 선형시스템 Ax=b 구성

   (단, 주어진 모든 정점을 지나가는 직선은 존재하지 않으므로 선형시스템의 해는 존재하지 않음.)

   ![https://velog.velcdn.com/images%2Fleeyongjoo%2Fpost%2Ffa2b9af6-9e51-4bfa-b4a7-c0c1ca2a5798%2Fimage.png%5D(https%3A%2F%2Fimages.velog.io%2Fimages%2Fleeyongjoo%2Fpost%2Ffa2b9af6-9e51-4bfa-b4a7-c0c1ca2a5798%2Fimage.png)

2. 최소제곱법 적용

   : $A^{T}A\bar{x}=A^{T}b$ 를 생각하고, $\bar{x}=\begin{bmatrix}\bar{m}\\\bar{b}\end{bmatrix}$ 를 구한다.

   ![https://velog.velcdn.com/images%2Fleeyongjoo%2Fpost%2Ff6b47924-0878-4289-8892-ea4ba86cf802%2Fimage.png%5D(https%3A%2F%2Fimages.velog.io%2Fimages%2Fleeyongjoo%2Fpost%2Ff6b47924-0878-4289-8892-ea4ba86cf802%2Fimage.png)