Pseudo Inverse(유사 역행렬) 및 SVD(특이값 분해)_v2

<질문>

Q. Least Square (최소 자승법) 과 Pseudo Inverse(유사 역행렬)는 어떤 연관이 있는가?
Q. AX=0 의 선형 연립방정식을 풀때는 어떤 방식을 사용하여야 하는가?
Q. Ax=0 식에서 왜 x가 Right Singular Vector라고 할수 있는가? 

---

Q. Least Square (최소 자승법) 과 Pseudo Inverse(유사 역행렬)는 어떤 연관이 있는가?

A. 변환 행렬 A가 역행렬이 존재하지 않는 경우만 관련이 있다. 예를 들어 A가 m by n 행렬(m > n)인 경우이다.

 

사전지식 참고)

(n by n) 정방행렬 중에는 역행렬이 존재하는 경우도 있고 존재하지 않는 경우도 있다. 하지만 정방행렬이 아니면 무조건 역행렬이 존재하지 않는다.

(상황)
최소 자승법 해 $E_{LLS} = ||Ax - b||^2$를 최소화 하는 x를 구할 때 $E_{LLS}$를 미분하게 되는데 이때 미분값 최소가 되는 Ax - b = 0인 x를 구하게 된다. 

(방법)
변환 행렬 A가 선형이고 역행렬이 존재한다면(A는 Full Rank이고 n by n) $x = A^{-1}b$로 해를 구할 수 있지만, Ax = b에서 A가 선형이 아니라면 유사 역행렬 $A^+ (\simeq A^{-1})$로 대신할 수 있다.
즉, 유사 역행렬은 최소 자승법 풀이의 한 방법이라고 할 수 있다.

대부분의 경우 A가 선형이 아니고, 최소 자승법을 거의 유사 역행렬을 이용해 풀이 하므로 본인은 최소 자승법과 유사 역행렬을 동일하다고 착각했던 것 같다

최소 자승법을 구하는 방법도 유사 역행렬 외에 가우스-뉴턴(Gauss-Newton) 방법 등이 존재하며,

유사 역행렬을 구하는 방법도 Moore-Penrose, SVD 등 여러가지가 있다.

 

$A^+$는 언급하였듯 두가지 방법으로 구할 수 있다.

1) Moore-Penrose 방법

$A^+$가 m by n 행렬이고(미지수가 n개, 식의 갯수가 m개, m>=n), 행렬 A의 각 열이 선형 독립일 때 다음과 같이 표현된다.
$$A^+ = (A^TA)^{-1}A^T$$
이렇게 구한 $ x = (A^TA)^{-1}A^{T}b $ 가  $x = A^{-1}b$에 가장 가깝다고(Closest) 할 수 있다.

당연하게도 Moore-Penrose 방법은 $A^TA$ 의 역행렬이 존재해야 한다. 식에 존재하기 때문에.

 

A 열들이 선형 독립이면 $A^TA$ 역행렬이 존재한다. 하지만, 선형 종속이면 $A^TA$ 역행렬이 존재하지 않는다.

 

2) SVD 방법

$A^+ = V \sum^{+} U^{T}$

 

A의 SVD는 $A = U\sum V^{T}$ 라 할때, 여기서 $\sum^{+}$는 $\sum$의 '0이 아닌 원소'를 Transpose 시킨 것이다.

 

(결론)

What is the 'Least Square Estimation' solution??

Sol 1) Pseudo Inverse
- Moore-Penrose Pseudo Inverse
- SVD(Singluar Value Decomposition) Pseudo Inverse

Sol 2) Gauss-Netwon's Method (Iterative Local Linearlization)

 

---

Q. AX=0의 선형 연립방정식을 풀때는 어떤 방식을 사용하여야 하는가?

A. 위의 식을 Homogeneous(동차) 선형연립 방정식 형태라고 말하고, SVD를 이용해 풀이한다.

결론 부터 말하자면, $A = U\sum V^{T}$ 라 할때, (A의 역행렬이 존재하지 않는) $Ax = 0$ 에서 (x=0인 경우를 제외한) x는 가장 값은 특이값(Smallest Singular Value) 에 대응되는 Singular Vector이다. 즉, Right Singular Vector. 이 x 값은 ||Ax||를 최소로 하는 근사해를 의미한다.

 

가장 작은 Singular Value에 대응하는 Singular Vector (위의 그림에서 N과 9는 예시이다)

 

그림으로 나타내면 회색 대각 성분이 특이값을 나타내고, 우측 하단 값이 가장 작은 특이값이다. 그리고, 파란색 원소가 이에 대응하는 특이값 벡터가 된다.

 

만약 특이값에 0이 포함된 경우라면, 특이값 0에 대응하는 Right Singular Vector는 (특이값 0이 여러개 존재할 경우에는 다수의 Right Singular Vector가) 모두 Ax=0 식의 해가 된다.이들 식의 일차결합도 해가 된다.

 

 

(결론)

Ax=b인 경우는 Pseudo-Inverse(Moore Penrose, SVD) 혹은 Iterative한 방법을 고려해 볼 수 있지만, Ax=0인 경우는 SVD를 고려한다.

---

Q, 왜 Ax=0 식에서 x가 Right Singular Vector이라고 할수 있는가?

A. 여기서는 Determinded 경우로 한정한다. 즉 m>n인 경우.

 

 

(추후 정리...)

---

[1] https://www.itl.nist.gov/div898/software/dataplot/refman2/auxillar/pseudinv.htm

[2] https://darkpgmr.tistory.com/108