[LA] Pseudo Inverse Matrix

참고로 아래에 Singular Vector Decomposition으로 Pseudo Inverse를 구하는 방법이 있음.

Pseudo Inverse Matrix

square matrix 가 아닌 matrix $A_{m\times n}$에서 inverse에 해당하는 matrix를 구하는데 사용됨.

$$ A^+_{n\times m}=\left\{\begin{array}{ll} (A^TA)^{-1}A^T &,A^+A=I_{n\times n}&\text{if }m \ge n&(1)\\A^T(AA^T)^{-1}&,AA^+=I_{m\times m}& \text{if }m\le n&(2)\end{array}\right. $$

• 사실 (1)의 경우는 엄밀히 쓰면 $(A^HA)^{-1}A^H$이며 $A$의 column vector들이 linearly independent한 경우의 Moore-Penrose Pseudoinverse Matrix임. (left inverse matrix라고 불림)
• (2)의 경우도 엄밀히 쓰면 $A^H(AA^H)^{-1}$이며 $A$의 row vector들이 linearly independent한 경우의 Moore-Penrose Pseudoinverse Matrix임. (right inverse matrix라고도 불림.)

$A^H$는 $A$의 entry들에 complex conjugate를 시킨 후 transpose를 취한 것을 의미

참고 : Moore-Penrose Pseudoinverse Matrix가 반드시 만족해야하는 4가지 조건.

• $AA^+A=A$ : $AA^+$가 반드시 unit identity matrix일 필요는 없으나, $A$의 모든 column vector를 보존해야함.
• $A^+AA^+=A^+$ :
• $(AA^+)^H=AA^+$ : $AA^+$는 Hermitian matrix 여야 함.
• $(A^+A)^H = A^+A$ : $A^+A$는 Hermitian matrix 여야 함.

위의 4가지 조건을 만족하는 경우, $A^+$는 항상 존재하며 유일함!

참고 : Moore-Penrose Pseudoinverse Matrix가 가지는 성질은 다음과 같음.

• $(A^T)^+=(A^+)^T$
• $(A^*)^+=(A^+)^*$ : $^*$는 complex conjugate를 의미함.
• $(A^H)^+=(A^+)^H$ : $^H$는 entry들에 complex conjugate를 시킨 후 transpose를 취한 것을 의미.
• $(cA)^+ =\frac{A^+}{c}$ : $c$로 scalar multiple한 경우임.
• $(A^+)^+ =A$

(1) Left Inverse

주로 많이 사용되는 경우는 (1)의 경우로, $A\textbf{x}=\textbf{b}$가 over-determined system에 대한 solution을 구하는 데 사용됨.

이는 least square 로 solution의 arrproximation을 구하는 것에 해당하며 normal equation을 이용하여 solution이 없는 over-determeined system에서 가장 residual error가 적은 least square solution (or approximation of solution, 근사해) $\hat{\textbf{x}}$를 구하게 해줌.

 

Least square solutoin $\hat{\textbf{x}}$은 다음을 가르킴.

(정의 상으로는 difference의 norm만을 최소화 시켜도 되지만, quadratic form을 사용하는게 훨씬 많이 사용됨)

Given an over-determined system $A\textbf{x} \simeq \textbf{b}$ where $A \in \mathbb{R}^{m\times n}, \textbf{b} \in \mathbb{R}^n$, and $m \gg n$, a least square solution $\hat{\textbf{x}}$ is defined as
$$ \begin{aligned}\hat{\textbf{x}}&= \text{arg } \underset{\textbf{x}} { \text{min }} \Vert \textbf{b}-A\textbf{x} \Vert \\ &= \text{arg }\underset{\textbf{x}} {\text{min }} \|\textbf{b}-A\textbf{x}\|^2\end{aligned} $$

다음의 OLS의 normal equation과도 연관성이 깊으므로 참고할 것.

https://dsaint31.tistory.com/entry/Ordinary-Least-Squares-OSL-%EC%B5%9C%EC%86%8C%EC%9E%90%EC%8A%B9%EB%B2%95

Ordinary Least Squares : OLS, 최소자승법

 

(2) Right Inverse

(2)의 경우는 $A\textbf{x}=\textbf{b}$가 under-determined system이며, 이 경우의 pseudo inverse는 무수히 많이 존재하는 solution(해) 중에서 한 개의 solution을 찾게 해줌.

---

Singular Value Decomposition 과 Pseudo Inverse ***

$A$를 $U\Sigma V^T$ (복소수 고려시 $U\Sigma V^H$임)로 SVD를 하고 이를 통해 pseudo inverse를 구하는 게 일반적임.

$$ \begin{aligned}(A^TA)^{-1}A^T&= ((U\Sigma V^T)^T U\Sigma V^T)^{-1}(U\Sigma V^T)^T\\&=((V\Sigma^T U^T)U\Sigma V^T)^{-1}(U\Sigma V^T)^T\\&=(V\Sigma^2V^T)^{-1}(U\Sigma V^T)^T\\&=((V^T)^{-1}\Sigma^{-2}V^{-1})(V\Sigma^TU^T)\\&=(V\Sigma^{-2}V^T)(V\Sigma U^T)\\&=V\Sigma^{-1}U^T \end{aligned} $$

where

• $\Sigma^{-1}$: singular value들의 diagonal matrix의 inverse이므로 main diagonal에 있는 singular value들을 역수로만 바꾸면 ($\lambda_{ii}\to \frac{1}{\lambda_{ii}}$) 됨.
• $U$ : orthonormal column으로 구성된 orthogonal $m\times m$ matrix. $U^{-1}=U^T$
• $V$ : 역시 orthogonal matrix. $n\times n$ matrix임. $V^{-1}=V^T$

Right inverse도 결과는 같으며, 유도는 다음과 같음.

$$ \begin{aligned}A^T(AA^T)^{-1}&=(U\Sigma V^T)^T(AA^T)^{-1}\\&=(V\Sigma U^T)(U\Sigma V^T V\Sigma^T U^T)^{-1}\\&=(V\Sigma U^T)(U\Sigma^{2}U^T)^{-1}\\&=(V\Sigma U^T)( {(U^T)}^{-1}\Sigma^{-2}U^{-1})\\&=(V\Sigma U^T)(U\Sigma^{-2}U^T)\\&=V\Sigma^{-1}U^T\end{aligned} $$