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

Posted on 2015-12-272016-01-07 by Lee Ju Hyung

양면-역행렬 (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^{+}$ 는 $\Sigma$ 의 $0$ 이 아닌 대각 성분을 역수로 바꾸고 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 1: Geometry of linear equations (9/30/2015)
선형대수 note 2: Elimination with Matrices (9/30/2015)
선형대수 note 3: Multiplication and Inverse Matrices (9/30/2015)
선형대수 note 4: Factorization into A = LU (9/30/2015)
선형대수 note 5: Transposes, permutations, space R^n (9/30/2015)
선형대수 note 6: Column space and nullspace (10/2/2015)
선형대수 note 7: Solving Ax = 0 pivot variables, special solutions (10/2/2015)
선형대수 note 8: Solving Ax = b row reduced form R (10/2/2015)
선형대수 note 9: Independence, basis, and dimension (10/2/2015)
선형대수 note 10: The four fundamental subspaces (10/3/2015)
선형대수 note 11: Matrix spaces; rank 1; small world graphs (10/4/2015)
선형대수 note 14: Orthogonal vectors and subspaces (10/4/2015)
선형대수 note 15: Projections onto subspaces (10/4/2015)
선형대수 note 16: Projection matrices and least squares (10/6/2015)
선형대수 note 17: Orthogonal matrices and Gram-Schmidt (10/10/2015)
선형대수 note 18: Properties of determinants (10/10/2015)
선형대수 note 19: Determinant formulas and cofactors (10/12/2015)
선형대수 note 20: Cramer’s rule, inverse matrix, and volume (10/13/2015)
선형대수 note 21: Eigenvalues and Eigenvectors (10/14/2015)
선형대수 note 22: Diagonalization and Powers of A (10/18/2015)
선형대수 note 23: Differential equations and exp(At) (12/23/2015)
선형대수 note 24: Markov matrices; fourier series (12/23/2015)
선형대수 note 25: Symmetric matrices and positive definiteness (12/23/2015)
선형대수 note 26: Complex matrices; fast fourier transform (12/23/2015)
선형대수 note 27: Positive definite matrices and minima (12/24/2015)
선형대수 note 28: Similar matrices and jordan form (12/24/2015)
선형대수 note 29: Singular value decomposition (12/25/2015)
선형대수 note 30: Linear Transformations and Their Matrices (12/26/2015)
선형대수 note 33: Left and Right Inverses; Pseudoinverse. (12/27/2015)

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

Posted on 2015-12-262016-01-07 by Lee Ju Hyung

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

선형변환을 좌표 없이 표현

벡터 공간 $\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}^m$ 은 $m\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 1: Geometry of linear equations (9/30/2015)
선형대수 note 2: Elimination with Matrices (9/30/2015)
선형대수 note 3: Multiplication and Inverse Matrices (9/30/2015)
선형대수 note 4: Factorization into A = LU (9/30/2015)
선형대수 note 5: Transposes, permutations, space R^n (9/30/2015)
선형대수 note 6: Column space and nullspace (10/2/2015)
선형대수 note 7: Solving Ax = 0 pivot variables, special solutions (10/2/2015)
선형대수 note 8: Solving Ax = b row reduced form R (10/2/2015)
선형대수 note 9: Independence, basis, and dimension (10/2/2015)
선형대수 note 10: The four fundamental subspaces (10/3/2015)
선형대수 note 11: Matrix spaces; rank 1; small world graphs (10/4/2015)
선형대수 note 14: Orthogonal vectors and subspaces (10/4/2015)
선형대수 note 15: Projections onto subspaces (10/4/2015)
선형대수 note 16: Projection matrices and least squares (10/6/2015)
선형대수 note 17: Orthogonal matrices and Gram-Schmidt (10/10/2015)
선형대수 note 18: Properties of determinants (10/10/2015)
선형대수 note 19: Determinant formulas and cofactors (10/12/2015)
선형대수 note 20: Cramer’s rule, inverse matrix, and volume (10/13/2015)
선형대수 note 21: Eigenvalues and Eigenvectors (10/14/2015)
선형대수 note 22: Diagonalization and Powers of A (10/18/2015)
선형대수 note 23: Differential equations and exp(At) (12/23/2015)
선형대수 note 24: Markov matrices; fourier series (12/23/2015)
선형대수 note 25: Symmetric matrices and positive definiteness (12/23/2015)
선형대수 note 26: Complex matrices; fast fourier transform (12/23/2015)
선형대수 note 27: Positive definite matrices and minima (12/24/2015)
선형대수 note 28: Similar matrices and jordan form (12/24/2015)
선형대수 note 29: Singular value decomposition (12/25/2015)
선형대수 note 30: Linear Transformations and Their Matrices (12/26/2015)
선형대수 note 33: Left and Right Inverses; Pseudoinverse. (12/27/2015)

선형대수 note 29: Singular value decomposition

Posted on 2015-12-252016-01-07 by Lee Ju Hyung

고유값 분해 $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}_r$ 에 $A$ 를 곱하면 $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}_i$ 가 $AS = S\Lambda$ 였던 것 처럼, $A\mathbf{v}_i = \sigma_i \mathbf{u}_i$ 도 $AV_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}$

$V$ 와 $U$ 는 정방행렬이고, $\Sigma$ 는 $\Sigma_r$ 에서 $m-r$ 만큼 $0$ 행이 추가되고, $n-r$ 만큼 $0$ 열이 추가된다.
$V$ 와 $U$ 는 직교 정방행렬이므로 $V^{-1} = V^T,\ U^{-1} = U^T$ 이다. 그러므로 $AV = U\Sigma$ 는 $A = 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_i$ 가 $0$ 이상인 이유가 된다. $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$ 개의 값만 있으면 된다.