[MIT 18.065] 1.1. Multiplication Ax Using Columns of A

---

💡 이 글은 MIT의 선형대수학 강의 MIT 18.065 Spring 2018 및 Gilbert Strang 교수님의 책 『Linear Algebra and Learning from Data』을 따라 정리했습니다. 강의 내용과 일부 연습문제 풀이를 포함합니다.

1. Introduction

들어가기에 앞서 이 강의를 듣고, 이 책을 읽게 된 이유에 대하여 간단히 소개하고자 한다. 먼저 지금까지 내가 기초수학 쪽으로 들었던 강의는 다음 두 가지 뿐이다.

• Elementary Linear Algebra (11th Ed, Anton) - 고등학교 때 수업으로 들었다.
• Thomas’ Calculus: Early Transcendentals (13th Ed, Thomas) - 고등학교 때 수업, 대학교 때 교양으로 들었다.

ML 및 DL을 공부하면서 굉장히 많은 부분에 선형대수적 아이디어가 사용된다. 의료계에서 사용되는 많은 방법론들도 선형대수를 이해하지 않으면 그 본질을 파악하기 어렵다고 느껴졌다. (이해하지 않아도 단순히 “사용”하는 데에는 지장이 없긴 하지만…) 선형대수학 입문 수업을 들은 적은 있지만 사실 그것이 어떻게 데이터에 적용되고 있는지는 잘 모르겠다. 그래서 이번에는 데이터를 다루는 영역에서 필요한 선형대수학을 깊게 이해하고자 했고, 이 강의는 그러한 목적에 아주 적합하다고 생각했다. 워낙 유명한 강의이기도 하고. 그래서 강의를 선정해서 공부하게 되었는데, 앞으로 이 강의를 완독하는 데 꽤나 오랜 시간(약 3개월?)이 걸릴 것으로 생각된다. 그때까지 지치지 않고 잘 할 수 있길 바라본다 😊

참고: 시중에 『딥러닝을 위한 선형대수학』이라는 이름으로 번역본이 나와 있다. 영어가 익숙하지 않은 경우에는 이 책을 참고해도 좋겠지만, 개인적으로는 영어로 공부하는 것이 더 저자의 원 의도를 파악하기에 좋다고 생각한다. 그리고 조금 읽어보니, 기초적인 선형대수학 입문 수준의 지식은 필요하다.

2. Interpretation of Matrix-Vector Multiplication

Matrix-vector multiplication은 다음과 같이 두 가지 방법으로 표현할 수 있다.

1. Row interpretation: $A$의 각 row를 vector로 취급하고, 이를 $x$와 내적한다.
2. Column interpretation: $A$의 각 column을 vector로 취급하고, 이를 $x$와 선형결합한다.

예를 들면 row interpretation은 다음과 같다.

\[\begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 1x_1 + 2x_2 \\ 3x_1 + 4x_2 \end{bmatrix}\]

그리고 column interpretation은 다음과 같다.

\[\begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = x_1 \begin{bmatrix} 1 \\ 3 \end{bmatrix} + x_2 \begin{bmatrix} 2 \\ 4 \end{bmatrix}\]

일반적인 matrix-vector multiplication은 row interpretation으로 이해하는 것이 더 직관적이다. 그러나 column interpretation으로 이해하는 것도 필요하다. 결론은 다음과 같다.

$Ax$는 $A$의 column의 linear combination이다.

Column space라는 것이 columns의 combination으로 이루어진 공간이므로, $Ax$가 만드는 공간이 곧 column space인 것이다. 그럼 다음과 같은 진술도 참이다.

$Ax=b$가 해를 가진다는 것은 곧 $b$가 column space에 속한다는 것이다.

당연히 $n \times n$ invertible matrix $A$의 column space $\mathbf{C} (A) = \mathbb{R}^ n$이 될 것이다. 이는 $A$의 column이 linearly independent하기 때문이다.

3. Independent Columns and the Rank of $A$

Matrix $A$의 basis를 찾음으로써 $A=CR$로 분해할 수 있다. 여기서 $C$는 $A$의 column들 중 서로 linearly independent한 column들로 이루어진 matrix이고, 따라서 $C$는 $A$의 column space의 basis를 모아둔 matrix라고 볼 수 있다. 이때 $R$은 $\text{rref} (A)$ (row-reduced echelon form of $A$ w/o zero rows, 0인 행들을 모두 제거한 기약 행사다리꼴) 이다. 이때 $C$를 찾는 방법은 다음과 같다.

1. $A$의 column 1이 0이 아니라면, 이를 $C$의 첫 번째 column으로 넣는다.
2. $A$의 column 2가 $C$의 첫 번째 column의 배수가 아님라면, 이를 $C$의 두 번째 column으로 넣는다.
3. $A$의 column 3이 $C$의 첫 번째, 두 번째 column의 선형결합이 아니라면, 이를 $C$의 세 번째 column으로 넣는다.
4. …
5. 마지막에 $C$는 $r$개의 column을 가지게 된다. ($r \leq n$)

여기서 구한 $r$을 $A$의 rank라고 한다. 즉 $A$의 independent column의 개수이고, 이는 $A$의 column space의 dimension이다. 예를 들면 다음과 같다.

\[A = \begin{bmatrix} 1 & 3 & 8 \\ 1 & 2 & 6 \\ 0 & 1 & 2 \end{bmatrix} \quad \Rightarrow \quad C = \begin{bmatrix} 1 & 3 \\ 1 & 2 \\ 0 & 1 \end{bmatrix}, \quad R = \begin{bmatrix} 1 & 0 & 2 \\ 0 & 1 & 2 \end{bmatrix}\] \[A = \begin{bmatrix} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 0 & 0 & 6 \end{bmatrix} \quad \Rightarrow \quad C = \begin{bmatrix} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 0 & 0 & 6 \end{bmatrix}, \quad R = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}\] \[A = \begin{bmatrix} 1 & 2 & 5 \\ 1 & 2 & 5 \\ 1 & 2 & 5 \end{bmatrix} \quad \Rightarrow \quad C = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \quad R = \begin{bmatrix} 1 & 2 & 5 \end{bmatrix}\]

$A = CR$의 차원은 $\left(m \times n \right) = \left(m \times r \right) \left(r \times n \right)$이 되고, 이로부터 다음을 알 수 있다.

Independent columns의 수와 independent rows의 수는 같다.

그리고 $A=CR$을 row 관점에서 보면 $R$의 $r$개의 row로부터 $A$의 row를 만들어낼 수 있으며, $r$개의 row는 linearly independent하므로 $R$의 각 row는 $A$의 row space의 basis가 된다.

정리하자면 다음과 같다.

$\text{dim}(\mathbf{C} (A)) = \text{dim}(\mathbf{R} (A)) = r$
Basis of $\mathbf{C} (A)$: Columns of $C$ / Basis of $\mathbf{R} (A)$: Rows of $R$

4. Selected Solutions to Problems

Problem 15.

Q. $A=CR$일 때, $A$의 first row가 $R$의 row들의 combination으로 이루어짐을 보여라.

$A=CR$을 다음과 같이 나타낼 수 있다.

\[\begin{bmatrix} - & a_1^* & - \\ & \vdots & \\ - & a_m^* & - \end{bmatrix} = \begin{bmatrix} - & c_1^* & - \\ & \vdots & \\ - & c_m^* & - \end{bmatrix} \begin{bmatrix} - & r_1^* & - \\ & \vdots & \\ - & r_r^* & - \end{bmatrix}\]

따라서 $a_1^* = c_ {11} r_1^* + \cdots + c_ {1r} r_r^*$이므로, $A$의 first row는 $R$의 row들의 combination으로 이루어져 있다.

Problem 21. [$A = \mathbf{CMR}$]

Q. 행렬 $A$과 다음과 같을 때, $A = \mathbf{CMR}$로 분해하라.

\[A = \begin{bmatrix} 1 & 3 & 8 \\ 1 & 2 & 6 \\ 0 & 1 & 2 \end{bmatrix}\]

$A = \mathbf{CMR}$ 분해는 $A = CR$ 분해와 유사한데, 다른 점은 $R$이 $\text{rref} (A)$이 아니라, $C$와 동일한 방법으로 $A$로부터 직접 얻을 수 있다는 점이다. 따라서 notation을 다르게 하여 $C, R$이 아니라 $\mathbf{C}, \mathbf{R}$이라고 한다. 위 matrix의 $\mathbf{C}$와 $\mathbf{R}$은 다음과 같다. $A=CR$일 때보다 훨씬 쉽게 $R$을 구할 수 있게 되었다.

\[\mathbf{C} = \begin{bmatrix} 1 & 3 \\ 1 & 2 \\ 0 & 1 \end{bmatrix}, \quad \mathbf{R} = \begin{bmatrix} 1 & 3 & 8 \\ 1 & 2 & 6 \end{bmatrix}\]

그렇다면 $r \times r$ matrix인 mixing matrix $\mathbf{M}$은 어떻게 구하는가? 이는 다음 과정을 통해 알 수 있다.

\[\begin{aligned} A &= \mathbf{CMR} \\ \mathbf{C} ^T A \mathbf{R} ^T &= \mathbf{C} ^T \mathbf{CMR} \mathbf{R} ^T \\ \therefore \mathbf{M} &= \left( \mathbf{C} ^T \mathbf{C} \right) ^{-1} \left( \mathbf{C} ^T A \mathbf{R} ^T \right) \left( \mathbf{R} \mathbf{R} ^T \right) ^{-1} \end{aligned}\]

1.3절에서 알게 되지만, $\mathbf{C} ^T \mathbf{C}$ 및 $\mathbf{R} \mathbf{R} ^T$는 $r \times r$ matrix이고 rank $r$을 가지고 있어 invertible하다. 따라서 $\mathbf{M}$은 단순 계산으로 구할 수 있는 것이다. 차근차근히 계산해보면 다음과 같다.

\[\begin{aligned} \mathbf{C} ^T \mathbf{C} &= \begin{bmatrix} 1 & 1 & 0 \\ 3 & 2 & 1 \end{bmatrix} \begin{bmatrix} 1 & 3 \\ 1 & 2 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 2 & 5 \\ 5 & 14 \end{bmatrix} \\ \mathbf{R} \mathbf{R} ^T &= \begin{bmatrix} 1 & 3 & 8 \\ 1 & 2 & 6 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 3 & 2 \\ 8 & 6 \end{bmatrix} = \begin{bmatrix} 74 & 55 \\ 55 & 41 \end{bmatrix} \\ \end{aligned}\]

이들의 역행렬을 계산하면 다음과 같다.

\[\begin{aligned} \left( \mathbf{C} ^T \mathbf{C} \right) ^{-1} &= \frac{1}{3} \begin{bmatrix} 14 & -5 \\ -5 & 2 \end{bmatrix} \\ \left( \mathbf{R} \mathbf{R} ^T \right) ^{-1} &= \frac{1}{9} \begin{bmatrix} 41 & -55 \\ -55 & 74 \end{bmatrix} \end{aligned}\]

이제 M을 다음 계산식으로 구할 수 있다. (계산은 생략)

\[\mathbf{M} = \left( \mathbf{C} ^T \mathbf{C} \right) ^{-1} \left( \mathbf{C} ^T A \mathbf{R} ^T \right) \left( \mathbf{R} \mathbf{R} ^T \right) ^{-1}\]

$A = \mathbf{CMR}$ 분해(factorization)는 다른 분해들, 즉 QR-decomposition, SVD와는 달리 $A$의 특성들을 많이 보존하고 있다. 따라서 다음 두 가지가 성립한다.

• $A$가 nonnegative이면, $\mathbf{C}, \mathbf{R}$도 nonnegative이다.
• $A$가 sparse하면, $\mathbf{C}, \mathbf{R}$도 sparse하다.

MIT 18.065 카테고리 내 다른 글 보러가기