선형대수 note 33: Left and Right Inverses; Pseudoinverse.

양면-역행렬 (Two sided inverse)

A 가 정방 full rank 일때 (m = n = r)
dim(N(A)) = dim(N(A^T)) = 0
A 의 양면 역행렬은 A^{-1}

    \[A^{-1}A = I = AA^{-1}\]

좌-역행렬 (Left inverse)

A 가 세로로 긴 full column rank 일때 (m \ge n = r)
dim(N(A)) = 0,\ dim(N(A^T) = m - r
A\mathbf{x} = \mathbf{b} 의 해는 (\mathbf{b}A 의 column space 에 존재하지 않을 수 있으므로) 1 개 이거나 해가 없다.
A 가 full column rank 이기 때문에 A^T A 은 가역 대칭 행렬이다. 그러므로 A 의 좌역행렬은

    \[\underbrace{(A^T A)^{-1} A^T}_{A_{\text{left}}^{-1}}A = I\]

A\mathbf{x}\mathbf{x} 를 row space 에서 column space 로 변환하고, A_{\text{left}}^{-1} A \mathbf{x} 는 원래의 \mathbf{x} 로 돌려놓는다.

우-역행렬 (Right inverse)

A 가 가로로 긴 full row rank 일때 (n \ge m = r)
dim(N(A)) = n - r,\ dim(N(A^T)) = 0
A\mathbf{x} = \mathbf{b} 의 해는 (\mathbf{b}A 의 column space 에 반드시 존재한다) \infty or 적어도 1 개가 존재한다.
A 가 full row rank 이기 때문에 A A^T 는 가역 대칭 행렬이다. 그러므로 A 의 우역행렬은

    \[A \underbrace{A^T (A A^T)^{-1}}_{A_{\text{right}}^{-1}} = I\]

\mathbf{x}^T A\mathbf{x} 를 column space 에서 row space 로 변환하고, \mathbf{x}^T A A_{\text{right}}^{-1} 는 원래의 \mathbf{x} 로 돌려놓는다.

Pseudo-역행렬

양면-역행렬, 좌-역행렬, 우-역행렬은 모두 full rank 일 때만 존재한다. 그 외에 경우 (r < n,\ r < m) 까지 포함하는 일반적인 행렬의 역행렬에는 Pseudo-역행렬을 적용할 수 있다. Pseudo-역행렬은 모든 벡터를 역으로 돌려 놓지는 못한다. nullspace 에 있는 벡터는 \mathbf{0} 벡터로 매핑되기 때문에 Pseudo-역행렬을 곱해도 \mathbf{0} 벡터가 된다. 하지만 row space 벡터는 항상 column space 벡터로 1 대 1 로 변환된다. 즉, \mathbf{x} 가 row space 의 벡터라면 A\mathbf{x} 는 column space 의 벡터고, A^{+}A\mathbf{x} = \mathbf{x} 가 된다. \mathbf{x} 가 row space 에 존재하지 않는다고 해도 A^{+}A\mathbf{x} 는 최대한 \mathbf{x} 에 가까운 벡터가 되도록 한다.

pseudo 역행렬은 SVD 를 이용해서 구할 수 있다.

    \[\begin{aligned} A^{+}  &= (U\Sigma V^T)^{+}\\ &= V\Sigma^{+} U^T\\ &=  \underbrace{\begin{bmatrix}  \\ \mathbf{v}_1 & \dots & \mathbf{v}_r & \dots & \mathbf{v}_n\\ \\ \end{bmatrix}}_{n\times n}  \underbrace{\begin{bmatrix} \frac{1}{\sigma_1} \\ & \frac{1}{\sigma_2} \\ & & \ddots \\ & & & \frac{1}{\sigma_r} \\ & & & & \\ \end{bmatrix}}_{n\times m} \underbrace{\begin{bmatrix} \\ \mathbf{u}_1 & \dots & \mathbf{u}_r & \dots & \mathbf{u}_m\\ \\ \end{bmatrix}^T}_{m\times m} \end{aligned}\]

\Sigma^{+}\Sigma0 이 아닌 대각 성분을 역수로 바꾸고 transpose 한 것이다.

A 가 정방 full rank 일때 A 는 가역행렬이므로 \Sigma 의 대각 성분들은 모두 0 보다 크고, A^{+} 는 양면-역행렬과 같다.
A 가 세로로 긴 full column rank 일때 A^TA 는 가역행렬이므로 \Sigma 의 대각 성분들은 모두 0 보다 크고, A^{+} 는 좌-역행렬과 같다.
A 가 가로로 긴 full row rank 일때 AA^T 는 가역행렬이므로 \Sigma 의 대각 성분들은 모두 0 보다 크고, A^{+} 는 우-역행렬과 같다.

pseudo-inverse-map

AA^{+} 는 벡터를 column space 로 투영한다.
A^{+}A 는 벡터를 row space 로 투영한다.

Least Square

Least square 문제는 A 가 full column rank 행렬일때 A\mathbf{x} = \mathbf{b} 라는 해가 없는 식에서 \mathbf{b}A 의 column space 에 투영하여 A\mathbf{\hat{x}} = \mathbf{p} 로 바꿔서 풀었었다. Pseudo 역행렬을 적용하면 A 가 full rank 가 아니더라도 해는 \mathbf{x}^{+} = A^{+}\mathbf{b} 가 된다. A 의 nullspace 벡터를 \mathbf{x}^{+} 에 더해도 A\mathbf{x}^{+} = \mathbf{p} 의 해가 되지만 가장 짧은 해는 \mathbf{x}^{+} 가 된다.


선형대수 note 목록

선형대수 note 30: Linear Transformations and Their Matrices

선형 변환은 계산을 하려면 행렬과 좌표가 필요하지만 행렬과 좌표가 없어도 표현이 가능하다.

선형변환을 좌표 없이 표현

벡터 공간 \mathbb{R}^2 에서 \mathbb{R}^2 로의 선형 변환 T 는 다음과 같이 쓸 수 있다.

    \[T : \mathbb{R}^2 \rightarrow \mathbb{R}^2\]

T 가 투영변환일 경우 \mathbb{R}^2 안의 모든 벡터 \mathbf{v} 는 라인위에 있는 T(\mathbf{v}) 로 매핑된다. 좌표가 없으므로 기하학적인 그림으로 밖에 표현할 수 없다.

선형성 (Linearity)

변환 T 는 모든 \mathbf{v}\mathbf{w} 에 대해서 아래를 만족한다면 선형 (Linear) 이다.

    \[\begin{aligned} T(\mathbf{v} + \mathbf{w}) &= T(\mathbf{v}) + T(\mathbf{w}) \\ T(c\mathbf{v}) &= cT(\mathbf{v}) \end{aligned}\]

한줄로 표현하면

    \[T(c\mathbf{v} + d\mathbf{w}) &= cT(\mathbf{v}) + dT(\mathbf{w})\]

투영 변환 외에도 회전 변환, 스케일 변환등은 선형성을 유지하는 선형 변환이다.

선형변환을 좌표와 행렬로 표현

모든 종류의 선형 변환은 좌표가 명시되어 있으면 행렬로 표현할 수 있다. 다르게 말하면 선형 변환은 행렬 곱셈의 추상적 표현이다.

    \[\begin{aligned} T(\mathbf{v}) &= A\mathbf{v} \\ A(c\mathbf{v} + d\mathbf{w}) &= cA\mathbf{v} + dA\mathbf{w} \end{aligned}\]

모든 선형 변환 T : \mathbb{R}^n \rightarrow \mathbb{R}^mm\times n 행렬의 곱셈으로 표현할 수 있다.

선형 변환 T(\mathbf{v})

모든 입력 \mathbf{v} 에 대해서 모든 출력 T(\mathbf{v}) 를 알려면 얼만큼의 정보가 필요할까? T 가 벡터 \mathbf{v}_1 을 어떻게 변환하는지 안다면, c\mathbf{v}_1 에 대해서도 어떻게 변환되는지 알 수 있다. T 가 선형 독립인 벡터 \mathbf{v}_1, \mathbf{v}_2 를 어떻게 변환하는지 안다면, c\mathbf{v}_1 + d\mathbf{v}_2 인 평면의 모든 벡터들에 대해서도 어떻게 변환되는지 알 수 있다. \mathbb{R}^n 의 모든 벡터들 \mathbf{v} 가 어떻게 변환되는지 알고 싶다면 기저벡터들 \mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_n 의 결과인 T(\mathbf{v}_1), T(\mathbf{v}_2), \dots, T(\mathbf{v}_n) 들을 알면 된다. \mathbf{v} 는 입력 공간 기저의 선형결합으로 표현할 수 있고 T 가 선형변환이기 때문이다.

    \[\begin{aligned} \mathbf{v} &= c_1 \mathbf{v}_1 + c_2 \mathbf{v}_2 + \dots + c_n \mathbf{v}_n \\ T(\mathbf{v}) &= c_1 T(\mathbf{v}_1) + c_2 T(\mathbf{v}_2) + \dots + c_n T(\mathbf{v}_n) \end{aligned}\]

기저의 계수 c_i 는 좌표가 된다. 좌표는 기저를 기반으로 표시한다. 기저가 바뀌면 같은 벡터의 좌표도 바뀐다. 다른 말로 하면 좌표가 같다고 해도 기저가 다르다면 다른 벡터라고 할 수 있다. 일반적으로 쓰는 3차원 좌표는 표준기저벡터 \begin{bmatrix}1\\0\\0\end{bmatrix}, \begin{bmatrix}0\\1\\0\end{bmatrix}, \begin{bmatrix}0\\0\\1\end{bmatrix} 의 계수다.

선형 변환 행렬

행렬은 입력 좌표 (입력 기저의 좌표) 를 출력 좌표 (출력 기저의 좌표) 로 변환한다. 입력 기저가 \mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_n 이고, 출력 기저가 \mathbf{w}_1, \mathbf{w}_2, \dots, \mathbf{w}_m 일 때 각 입력기저들에 대한 선형변환은 출력 기저들의 선형 결합으로 나타낼 수 있다. 이를 통해 행렬 A 의 성분을 알 수 있다.

    \[\begin{aligned} T(\mathbf{v}_1) &= a_{11}\mathbf{w}_1 + a_{21}\mathbf{w}_2 + \dots + a_{m1}\mathbf{w}_m \\ T(\mathbf{v}_2) &= a_{12}\mathbf{w}_1 + a_{22}\mathbf{w}_2 + \dots + a_{m2}\mathbf{w}_m \\ \vdots \\ T(\mathbf{v}_n) &= a_{1n}\mathbf{w}_1 + a_{2n}\mathbf{w}_2 + \dots + a_{mn}\mathbf{w}_m  \end{aligned} \quad A = \begin{bmatrix} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \dots & a_{mn} \end{bmatrix}\]


선형대수 note 목록

선형대수 note 29: Singular value decomposition

고유값 분해 A = Q\Lambda Q^{T} 가 가능하려면 A 는 대칭행렬이어야 한다. 특이값 분해 (Singular Value Decomposition) 는 A 가 임의의 직사각행렬이어도 적용할 수 있다.

    \[A = U\Sigma V^T\]

U 는 직교행렬, \Sigma 는 대각행렬, V 는 직교행렬이다. 행렬 A 가 대칭행렬이고, 양준정부호 행렬일 때 SVD 는 고유값 분해 Q \Lambda Q^T 와 같은 형태가 된다. 좀 더 자세히 알아보자.

직사각행렬 A\text{rank} = r 일 때 row space 의 차원은 r 이다. r 개의 직교하는 기저벡터를 찾을 수 있을 것이다. column space 도 마찬가지다. r 개의 기저벡터들을 찾을 수 있다. 아무 기저나 찾는 것이 아니라 특별히 A 를 곱해서 row space 기저에서 column space 기저로 변환이 되는 기저들을 찾을 것이다.
row space 에 존재하는 직교 벡터들 \mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_rA 를 곱하면 A 의 column space 에 존재하는 직교 벡터 \sigma_1 \mathbf{u}_1, \sigma_2 \mathbf{u}_2, \dots, \sigma_r \mathbf{u}_r 으로 변환된다. 여기서 \sigma > 0 이다. A\mathbf{x}_i = \lambda_i \mathbf{x}_iAS = S\Lambda 였던 것 처럼, A\mathbf{v}_i = \sigma_i \mathbf{u}_iAV_r = \Sigma_r U_r 이 된다.

    \[\begin{aligned} A V_r &= U_r \Sigma_r \\  \underbrace{A}_{(m\times n)}  \underbrace{\begin{bmatrix}  \\ \mathbf{v}_1 & \dots & \mathbf{v}_r \\ \\ \end{bmatrix}}_{(n\times r)} &= \underbrace{\begin{bmatrix}  \\ \mathbf{u}_1 & \dots & \mathbf{u}_r \\ \\ \end{bmatrix}}_{(m\times r)} \underbrace{\begin{bmatrix} \sigma_1 \\ & \ddots \\ & & \sigma_r \\ \end{bmatrix}}_{(r\times r)} \end{aligned}\]

V_r 는 직교행렬이므로 양변의 오른쪽에 V_r^T 를 곱하면 A = U_r \Sigma_r V_r^T 가 되고, 이것을 reduced SVD 라고 한다.

\mathbf{v}_i 는 nullspace 와 직교하므로 추가적인 n - r 개의 직교벡터 \mathbf{v}_i 들을 nullspace 에서 찾을 수 있다. 마찬가지로 \mathbf{u}_i 는 left nullspace 와 직교하므로 추가적인 m - r 개의 직교벡터 \mathbf{u}_i 들을 left nullspace 에서 찾을 수 있다. n - r 개의 v_i 들은 A 에 의해서 \mathbf{0} 으로 맵핑된다. 따라서 이 벡터들을 포함하면,

    \[\begin{aligned} AV &= U\Sigma \\ \underbrace{A}_{(m\times n)}  \underbrace{\begin{bmatrix}  \\ \mathbf{v}_1 & \dots & \mathbf{v}_r & \dots & \mathbf{v}_n \\ \\ \end{bmatrix}}_{(n\times n)} &= \underbrace{\begin{bmatrix}  \\ \mathbf{u}_1 & \dots & \mathbf{u}_r & \dots & \mathbf{u}_m \\ \\ \end{bmatrix}}_{(m\times m)} \underbrace{\begin{bmatrix} \sigma_1 \\ & \ddots \\ & & \sigma_r \\ \\ \end{bmatrix}}_{(m\times n)} \end{aligned}\]

VU 는 정방행렬이고, \Sigma\Sigma_r 에서 m-r 만큼 0 행이 추가되고, n-r 만큼 0 열이 추가된다.
VU 는 직교 정방행렬이므로 V^{-1} = V^T,\ U^{-1} = U^T 이다. 그러므로 AV = U\SigmaA = U\Sigma V^T 로 쓸 수 있다.

그림으로 그려보면,

singular-vector-mapping

계산

정방행렬 A^TA 를 특이값 분해하면,

    \[\begin{aligned} A^T A &= (U\Sigma V^T)^T U\Sigma V^T \\ &= V\Sigma^T U^T U\Sigma V^T \\ &= V\Sigma^2 V^T \end{aligned}\]

위의 식은 Q\Lambda Q^T 와 같은 형태다. \mathbf{v}_i = \mathbf{q}_i 이고, \sigma_i^2 = \lambda_i 가 된다. A^TA 는 적어도 positive semi-definite 행렬이므로 \Lambda 의 성분들은 0 이상이고, 이것은 \sigma_i0 이상인 이유가 된다. A\mathbf{v}_i = \sigma_i \mathbf{u}_i 이므로 \mathbf{u}_i = \frac{A\mathbf{v}_i}{\sigma_i} 이다. 이로써 V, \Sigma, U 를 모두 구할 수 있다.

SVD 는 선형대수의 Key 가 되는 주제인 positive definite 행렬과 4 fundamental subspaces 를 모두 아우르는 중요한 주제라고 할 수 있다. 또 임의의 직사각 행렬에 적용가능하기 때문에 가장 유용한 분해 방법 중 하나다.

\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_r row space 의 orthonormal basis
\mathbf{v}_{r+1}, \mathbf{v}_{r+2}, \dots, \mathbf{v}_n nullspace 의 orthonormal basis
\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_r column space 의 orthonormal basis
\mathbf{u}_{r+1}, \mathbf{u}_{r+2}, \dots, \mathbf{u}_m left nullspace 의 orthonormal basis

활용

A 를 특이값 분해하면,

    \[A = \sigma_1 \mathbf{u}_1 \mathbf{v}_1^T + \sigma_2 \mathbf{u}_2 \mathbf{v}_2^T + \dots + \sigma_r \mathbf{u}_r \mathbf{v}_r^T\]

\mathbf{u}_i \mathbf{v}_i^T\text{rank} = 1 행렬이다. 즉 A\text{rank} = 1 행렬의 합으로 나타낼 수 있다. \sigma_i 를 값이 큰 순서대로 정렬하면 A 를 표현하는데 있어서 뒷부분은 덜 중요한 행렬이 된다. 256 \times 512 이미지를 행렬로 나타내면 256\times 512 = 131072 개의 픽셀정보가 필요하다. 이 이미지를 특이값 분해하면 몇개의 \text{rank}=1 행렬로 근사할 수 있을 것이다. 예를 들어 16 개의 \sigma 를 사용한다면, 16 \times (256 + 512) = 12288 개의 값만 있으면 된다.


선형대수 note 목록