[LA] Pseudoinverse Matrix (수정중)

Pseudo-Inverse (Moore-Penrose Pseudoinverse)

Moore-Penrose Pseudoinverse는 일반적인 행렬에서 정의되어 inverse matrix처럼 사용가능한 개념 으로,

inverse가 full rank square matrix에만 정의되는 것과 달리,

• square matrix가 아니거나
• rank deficient matrix라 inverse가 존재하지않는 경우에도 구할 수 있음.

Moore-Penrose Pseudoinverse 의 특별한 경우가 left inverse와 right inverse임: 위 그림의 (푸른색) 4가지 조건을 만족하는 $A^\dagger$는 항상 존재하며 항상 유일하게 결정됨.

 

Moore-Penrose Pseudoinverse는 주로 SVD를 이용하여 구해지며 다음과 같음:

$$A^\dagger = V \Sigma^\dagger U^\top$$

• $A^\dagger$ 외에 $A^+$로도 자주 표기됨.
• inverse처럼 사용가능한 일종의 inverse approximation 이라고 봐야함: right inverse와 left inverse를 적절히 선택해야함.
• $\Sigma^\dagger$는 singular value 들로 구성된 $\Sigma$에서
  • 0이 아닌 singular value는 역수(reciprocal)를 취하고 
  • Transpose를 통해 얻어짐.

다음의 4개의 조건을 만족하는 $A^\dagger$가 Moore-Penrose Pseudoinverse Matrix임.

• $AA^\dagger A=A$ 
• $A^\dagger AA^\dagger =A^\dagger$
• $(AA^\dagger)^H=AA^\dagger $ : $AA^\dagger $는 Hermitian matrix 여야 함.
• $(A^\dagger A)^H = A^\dagger A$ : $A^\dagger A$는 Hermitian matrix 여야 함.

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

 

---

0. Pseudoinverse Matrix for Full Column Rank or Full Row Rank

square matrix 가 아닌 matrix $A_{m\times n}$가 만약 full column rank이거나 full row rank인 경우에는
inverse에 해당하는 matrix가 다음과 같이 구해짐:

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

• 사실 (1)의 경우는 엄밀히 쓰면 $(A^HA)^{-1}A^H$임:
  • $A$의 column vector들이 linearly independent한 경우 (full column rank)의
  • Pseudoinverse Matrix임.
  • left inverse matrix라고 불림: full column rank의 경우 left inverse와 Moore-Penrose Pseudo Inverse가 동일함.
  • $A^\dagger = V \Sigma^\dagger U^T = (A^H A)^{-1}A^H$ 가 성립하고,
  • $A^\dagger A = I_{n}$이 됨.
• (2)의 경우도 엄밀히 쓰면 $A^H(AA^H)^{-1}$임:
  • $A$의 row vector들이 linearly independent한 경우 (full row rank)의
  • Pseudoinverse Matrix임.
  • right inverse matrix라고도 불림: full row rank의 경우 right inverse와 Moore-Penrose Pseudo Inverse가 동일함.
  • $A^\dagger = V \Sigma^\dagger U^T = A^H (A A^H)^{-1}$ 가 성립하고,
  • $A A^\dagger = I_{m \times m}$ 

full row rank 또는 full column rank 일 때,
Normal Equation이 유일해를 가짐을 기억할 것.

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

---

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

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

---

1. Left Inverse

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

• 이는 Least Square 로 Solution의 approximation을 구하는 것에 해당
• 사실상 normal equation을 이용하여 solution이 없는 over-determeined system에서 가장 residual error가 적은 least square solution (or approximation of solution, 근사해) $\hat{\textbf{x}}$를 구하는 것과 같음
• Pseudoinverse는 full column rank가 아니더라도 적용이 가능함.

Least Square Solution $\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과도 연관성이 깊으므로 다음 URL을 참고할 것.

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이며,
이 경우의 pseudoinverse는 무수히 많이 존재하는 solution(해) 중에서 한 개의 solution ($\|\mathbf{x}\|$가 최소인)을 찾게 해줌.

---

3. Singular Value Decomposition 과 Pseudoinverse ***

full column rank 나 full row rank가 아니더라도 Moore-Penroze Pseudoinverse는 구할 수 있음:

• SVD에서 singular value가 0은 Pseudoinverse를 구하는데 제외(더 나아가, 매우 작은 일정값 이하를 0으로 처리하여 제외)하는 reduced form을 이용하여 구함.
• 이 경우엔, $A^\dagger A$나 $A A^\dagger$가 Identity Matrix가 되지 않고, 거기에 근접한 matrix가 됨:
  • $A^\dagger A$ 은 A의 column space에 대한 orthogonal projection matrix임: column space 정보를 보존
  • $A A^\dagger$은 A의 row space에 대한 orthogonal projection matrix임: row space 정보를 보존
• rank에 해당하는 갯수의 rank-1 outer product 들(=0이 아닌 singular value에 대응하는 것들)의 합이 바로 Pseudoinverse임: 즉, rank deficient의 경우, $A A^\dagger$와 $A^\dagger A$는 완벽한 Identity가 되진 못함.
• full column rank인 경우는 left inverse를 사용하고, full row rank인 경우 right inverse를 사용하나,
  이 두 경우 모두 SVD 기반으로 구한 Pseudoinverse와 같음.

즉, $A$를 $U\Sigma V^\top$ (복소수 고려시 $U\Sigma V^H$임)로 SVD를 하고 이를 통해 pseudoinverse를 구하는 게 일반적임: $A^\dagger = V \Sigma^\dagger U^T$

 

다음은 full column rank에서 left inverse가 $A^\dagger$와 같아짐을 보임:

$$ \begin{aligned}(A^\top A)^{-1}A^\top &= ((U\Sigma V^\top)^\top U\Sigma V^\top)^{-1}(U\Sigma V^\top)^\top\\&=((V\Sigma^\top U^\top)U\Sigma V^\top)^{-1}(U\Sigma V^\top)^\top \\&=(V\Sigma^\top \Sigma V^\top)^{-1}(U\Sigma V^\top)^\top\\&=((V^\top)^{-1}\Sigma^\dagger (\Sigma^\top)^\dagger V^{-1})(V\Sigma^\top U^\top)\\&=(V\Sigma^\dagger (\Sigma^\top)^\dagger V^\top )(V\Sigma^\top U^\top )\\&=V\Sigma^\dagger U^\top \end{aligned} $$

where

• $\Sigma^{\dagger}$: singular value들의 diagonal matrix의 inverse 역할로 main diagonal에 있는 singular value들을 역수로만 바꾸고 ($\lambda_{ii}\to \frac{1}{\lambda_{ii}}$), transpose 시켜 얻어냄.
• $U$ : orthonormal column으로 구성된 orthogonal $m\times m$ matrix. $U^{-1}=U^\top$
• $V$ : 역시 orthogonal matrix. $n\times n$ matrix임. $V^{-1}=V^\top$

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

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

---

참고자료

https://youtu.be/vXk-o3PVUdU?si=urefRv3sG9rKefL8

https://youtu.be/oj49PMYuZKc?si=EA1NAnEvrk_AIlhh

https://youtu.be/9oJX8lAtRBE?si=_IupIGUSaQY_4S78