[Linear Algebra] Singular Value Decomposition (SVD), Eckart-Young: The Closest Rank k Matrix to A

Singular Value Decomposition, Eckart-Young: The Closest Rank k Matrix to A

* YAI 9기 송예원님이 선형대수 강의팀에서 MIT 18.065 by Gilbert Strang을 수강한 후 작성한 글입니다.

---

Lecture 6 : Singular Value Decomposition (SVD)

---

Introduciton

6강에서는 rectangular matrix의 factorization 중 하나인 Singular Value Decomposition에 대해 다룬다. 또한 SVD와 linear transformation의 기하학적 의미 및 polar decomposition과의 연관성에 대해 다룰 것이다.

---

Preliminary

singular value

 

singular value(특잇값)은 $\sum$의 대각 성분인 양의 실수를 의미한다. 이후 증명에서 다루겠지만, rectangular matrix A의 singular value는 $A^{T}A $의 eigen value의 제곱과도 같다.

 

3D rotation

물체를 3차원적으로 회전시키는 방법은 총 3가지이다. x, y, z축 중심으로 회전시킬 수 있기 때문이다. 따라서 각 축을 기준으로 회전시키는 것을 roll, pitch, yaw라고 부른다. 이후 3D rotation을 표현하기 위해 필요한 parameter수가 3개라는 사실이 이용된다.

---

Main

Singular Value Decomposition

 

SVD란, 임의의 rectangular matrix를 factorization하는 한 가지 방법이다. 이전까지의 강의에서 다룬 diagonalization은 square matrix에만 적용될 수 있다는 한계점이 존재한다. 데이터 분석에서 사용되는 대다수의 행렬은 square matrix가 아니므로 diagonalization을 확장시키는 개념인 SVD가 등장하게 된다.

 

 

SVD는 다음과 같은 수식으로 표현된다.

$$ A = U\sum V^T$$

A는 임의의 rectangular matrix이며, U는 left-singular vector로 구성된 matrix, V는 right-singular vector로 구성된 matrix, 그리고 $\sum$ 는 양의 실수인 $\sigma_1,\sigma_2,\sigma_3\dots$ 가 대각성분인 diagonal matrix이다. 이 때 관습에 따라 $\sigma_1 \geq \sigma_2 \geq \sigma_3 \cdots $ 임을 가정한다.

 

 

SVD의 증명은 다음과 같은 가정에서 출발한다.

$$AV_1 = \sigma_1u_1$$

$$AV_2 = \sigma_2u_2$$

$$\vdots$$

고윳값과 고유벡터 사이의 관계와 유사하게, v1 벡터에 A라는 linear transformation을 수행하면 u1벡터의 상수배가 된다는 의미이다. 위의 관계를 만족시키는 u, v 벡터와 상수 $\sigma_1,\sigma_2,\sigma_3\dots$ 를 모으면 아래의 행렬식이 된다.

$$AV = U\sum$$

이 때, V를 이루는 v1, v2, … 벡터들은 orthonormal하므로,

$$A = U\sum V^T$$

가 유도된다.

 

 

행렬 V와 U를 이루는 벡터들이 orthonormal한 이유는 각각이 $A^TA$ 와 $AA^T$의 고유벡터이기 때문이다. 행렬$A^TA$ 와 $AA^T$ 는 A의 모양에 상관없이 항상 square, symmetric, positive definite의 성질을 만족한다. 따라서 두 행렬은 다음과 같이 대각화 가능하다.

$$A^TA = V \wedge V^T$$

$$AA^T = U \wedge U^T$$

 

 

위의 두 대각화와 SVD 결과를 조합하면,

$$
A = U \sum V^T
$$

$$
A^TA = (U \sum V^T)^TU \sum V^T = V \sum{}^T U^TU\sum V^T = V(\sum{}^T \sum ) V^T = V \wedge V^T
$$

$$
\sum {}^T \sum = \wedge \rightarrow \sigma_1^2 = \lambda_1
$$

따라서 $\sum$의 대각성분을 이루는 각 시그마 값들은 $A^TA$ 혹은 $AA^T$의 고윳값의 제곱근과 같음을 알 수 있다.

 

linear transformation and SVD

 

SVD의 기하학적 의미는 어떠한 linear transformation도 rotate, stretch 그리고 rotate로 나누어서 해석 가능하다는 것이다. SVD의 수식을 구체적으로 다시 한번 살펴보자.

$$A = U \sum V^T$$

위의 수식에서 U와 V는 orthonormal한 벡터들로 이뤄진 행렬이므로 U와 V는 입력된 벡터를 회전시키는 행렬과도 같다. 반면 $\sum$는 대각성분만 존재하는 행렬이므로 입력된 벡터를 각 entry별로 다르게 늘리거나 줄이는 행렬이다.

2x2 행렬은 4개의 원소를 가진다. 2x2 행렬은 linear transformation의 관점에서 2개의 parameter를 필요로 하는 한 번의 stretch과정과 1개의 parameter(회전각)를 필요로 하는 두 번의 rotate과정으로 쪼개진다. 따라서 4개의 원소는 두 번의 rotate에 필요한 1*2개의 parameter와 stretch에 필요한 2개의 parameter에 대응된다.

 

3x3 행렬은 9개의 원소를 가진다. 3차원 rotate에는 3개의 parameter가 필요하며, 3차원 stretch에는 3개의 parameter가 필요하다. 따라서 2번의 rotate에서 6개, 1번의 stretch에서 3개 총 9개의 parameter가 필요한데 이는 3x3행렬의 원소 개수와 대응된다.

비슷한 확장을 통해 4x4 행렬의 rotate에 필요한 parameter의 수를 역으로 구해낼 수도 있다.


polar decomposition


임의의 rectangular matrix A는 symmetric matrix S와 orthogonal matrix Q의 곱으로 factorization 가능하다. 이를 polar decompositon이라고 한다.

$$ A = U \sum V^T = (U\sum U^T)(UV^T) = SQ$$

 

most important rank 1 part of A

 

SVD는 행렬 속에서 통계학적 의미를 지니는 주요한 값들을 찾아내는데 이용된다. 강의에서 언급된 한 가지 예시는,
$\sum $ 의 대각성분 중 가장 큰 값 즉 $\sigma_1$이 rank =1 인 성분들 중에서 데이터를 이해하는데 가장 중요한 값이라는 점이다.

---

정리하며

Rectangular matrix A는 항상 Singular Value Decomposition이 가능하다. 행렬 A의 SVD는
$$ A = U \sum V^T $$
이며 SVD는 임의의 linear transformation이 기하학적으로 rotation과 stretch로 나뉘는 것으로 해석 가능하다.

---

Lecture 7 : Eckart-Young: The Closest Rank k Matrix to A

---

Introduciton

7강은 데이터의 주요한 의미를 찾아내는 PCA(principal component analysis)와 PCA에 사용되는 Eckart-Young method와 matrix norm에 대해 다룬다.

---

Preliminary

PCA (Principal Component Analysis)

 

PCA는 데이터의 주성분을 찾아내기 위해 수행하는 연산 및 절차이다. 주로 고차원의 데이터를 더 낮은 차원으로 변환시키는데 많이 이용되기도 한다. 이번 강의에서 다룬 PCA는 2가지 parameter를 가지는 데이터들을 잘 나타내는 직선을 찾는 것이었다.

 

vector norm

 

norm은 벡터 공간과 0이상의 실수 값을 대응시키는 함수이다. norm 함수를 적용시키는 대상에 따라 vector norm과 matrix norm으로 구별되며 vector norm에도 여러 종류가 존재한다.
대표적인 vector norm의 종류는 다음과 같다.
$$\lvert \lvert x \rvert \rvert_2 : = \sqrt{x_1^2 + \cdots + x_n^2} $$
L2 norm of vector: n차원 유클리드 공간에서의 벡터의 길이이다.
$$\lvert \lvert x \rvert \rvert_1 : = \sum_{i=1}^n \lvert x_i \rvert. $$
L1 norm of vector: 각 성분의 절댓값을 모두 합한 값이다.
$$\lvert \lvert x \rvert \rvert_{\infty} : = max(\lvert x_1 \rvert, \cdots , \lvert x_n \rvert) $$
infinity norm: 각 성분의 절댓값 중 최댓값이다.

 

matrix norm

 

matrix norm은 matrix와 실수 값을 대응시키는 함수이다. matrix 또한 벡터 공간의 원소이므로 vector norm와 연관된 개념이다. 대표적인 matrix norm의 종류는 다음과 같다.
$$ \lvert \lvert A \rvert \rvert _2 = \sigma_{max}(A) $$
-L2 norm of matrix: 행렬의 가장 큰 singular value이다.
$$ \lvert \lvert A \rvert \rvert _F \equiv \sqrt{\sum_{i=1}^m \sum_{j=1}^n \lvert a_{ij} \rvert ^2} $$
-Frobenius norm: 각 element의 제곱을 모두 더한 후 제곱근을 취한 값이다. 이는 마치 행렬을 하나의 긴 벡터처럼 취급해서 L2 norm을 구한 값이다.

- Nuclear norm: 모든 singular value의 합이다. Netflix의 영화 추천 알고리즘에 유용하게 사용된 norm이라고 한다. 일부 원소가 비어 있는 행렬을 채우는데 유용하게 사용된다. MRI 이미지를 분석하는데 사용되기도 한다.

---

Main

Eckart-Young Theorem

 

$$\text{if B has rank k, then} \lvert \lvert A- B \rvert \rvert \geq \lvert \lvert A-A_k \rvert \rvert$$
$$\quad \text{ where,} A_k = \sigma_1u_1v_1^T + \sigma_2u_2v_2^T + \cdots + \sigma_ku_kv_k^T$$
Eckart-Young Theorem은 기존 행렬 A와 가장 가까운, 혹은 A를 가장 잘 표현할 수 있는 rank = k인 행렬은 $A_k$라는 것을 보여준다. 이 때 $A_k$는 A의 left singular vector와 right singular vector를 곱한 행렬을 k개 더한 값이며 각 행렬은 독립적인 기저를 가진다.

 

norm of A involves $\sum$

 

A의 matrix norm은 결국 A의 singular value들과 관련된 값이므로 A의 SVD 결과의 $\sum$ 에 의해 결정된다고 할 수 있다. 만약 A에 orthogonal matrix Q를 곱한다면 QA의 SVD결과의 $\sum$값은 변하지 않는다.

QU의 값 또한 orthogonal matrix이므로 이 전체를 left singular matrix로 취급할 수 있기 때문이다. 따라서 QA의 norm에는 변화가 없다.

 

Finding PCA best line

 

n명의 사람의 age와 height가 담긴 데이터 셋을 생각해보자. 해당 데이터 셋은 2xn 행렬에 담길 수 있다. 데이터 셋이 담긴 행렬을 $A_0$라 하자. $A_0$에 가장 먼저 수행해야하는 통계적 기법은 $A_0$의 age와 height 정보를 정규화하는 것이다.

 

따라서 모든 age 데이터와 height 데이터의 평균을 구해 각 데이터 값에서 빼야 한다. 정규화된 데이터셋을 A라고 하자. A를 2차원 평면 상에 나타내면 원점을 중심으로 우상향하는 점들의 집합이 나타날 것이다. 해당 데이터들을 가장 잘 나타내는 직선은 어떤 것일까?

least square 방법은 데이터와 직선 사이의 y방향 오차를 최소화하는 방식이다. 반면 PCA 방법은 각각의 데이터와 직선 사이의 수직 거리를 최소화하는 직선을 찾아낸다. PCA 방법을 통해 찾은 최적의 직선은 SVD를 통해 구할 수 있다고 한다.

---

정리하며

7강에서는 PCA 방법에 사용되는 Eckart-Young method, Vector norm, 그리고 matrix norm에 대해 소개했다. norm은 벡터(혹은 행렬)를 실수와 대응시키는 하나의 함수로 벡터(혹은 행렬)의 특성(기하학적 거리 등)을 나타낸다. norm을 구하는 실질적인 방법은 행렬의 SVD를 수행해 singular value들을 찾아내는 것이었다.