4. Matrix Decomposition

4. Matrix Decomposition

• 내용

  how to summarize matrices

  how matrices can be decomposed

  how these decompositions can be used for matrix approximations

Determinant

---

nxn 행렬에만 있으며, 행렬의 가역성(invertible)을 판단할 수 있음. n개의 열벡터를 n차원으로 매핑했을 때의 부호가 있는 부피를 의미함. 고유값 고유벡터를 구하기 위한 특성방정식(characteristic polynomial)에 활용.

• 라플라스 확장

  

  

  

• 성질

  

  마지막 3개의 성질과 가우시안 소거법으로 보다 편하게 구할 수 있음

Trace

---

정방행렬의 대각합

• 성질

  

  

  

  (4번째 부분, cyclic permutation)

특성방정식(characteristic polynomial)

---

고유값 고유벡터

---

고유값은 descending order로 나타내는 것이 convention이다. 고유값은 행렬의 특성방정식의 해이다. 고유값이 λ인 고유벡터들로 span한 subspace를 고유 공간(eigenspace)라고 한다. 또한 고유값 λ들의 집합을 eigenspectrum 또는 spectrum이라고 한다.

• 대수적 중복도 (Algebraic Multiplicity)

  특성방정식의 근, 고유값이 n중근 이상을 가지면, 대수적 중복도가 n이라고 한다.

• collinear & codirection

  codirection: 두 벡터의 방향이 같은것

  collinear: 두 벡터가 하나의 상수배로 나타낼 수 있는 것

• 성질
  • $A, A^T$의 고유값은 같지만, 고유벡터는 다를 수 있다.
  • eigenspace는 A행렬의 특성방정식의 영공간이다
  • 유사행렬들간의 고유값은 같다. 따라서 선형사상 $\phi$는 해당 매핑의 변환행렬의 기저와 Independent한 고유값을 가진다. 고유값, determinant, 대각합은 선형사상의 특성을 나타내는 핵심 파라미터이다.
  • Symmetric, Positive Definite 행렬은 항상 양의 실수인 고유값을 갖는다.
  • 대수적 중복도에 의해 하나의 고유값에 대한 고유벡터공간은 1차원 이상일 수도 있다(고유벡터가 2개일 수 있음).
  • 하나의 고유값에 대한 기하적 중복도(geometric multiplicity)는 최소 1이다. 기하적중복도는 대수적중복도보다 클 수는 없다. ex. [[2, 1],[0,2]] → 고유벡터 [1,0]^T 이며, 고유값은 2로 대수적중복도는 2이고, 기하적중복도는 1이다.
  • 서로 다른 고유 값에 대한 고유벡터는 서로 선형독립(linear independent)이다.
  • 정방행렬(nxn)이 n개보다 적은 고유벡터를 갖는다면, defective라고 한다.
  • mxn 행렬 A에 대하여 S:= A^TA는 항상, symmetric, positive semidefinite matrix S를 가질 수 있다. A의 rank가 n이라면, symmetric positive definite이다. (평균을 빼면, 공분산 행렬)
  • Spectral Theorem. A가 Symmetric하면, A의 고유벡터가 이루는 벡터공간 V는 기저는 orthonormal하며, 고유값은 실수값을 갖는다. (실제로 아니더라도, 만들 수 있다.) (theorem 4.15)

    

  • nxn행렬 A의 determinat는 고유값의 곱이다. 고유값이 중복되어도 적용된다.
  • nxn행렬 A의 trace는 고유값의 합과 같다. 고유값이 중복되어도 적용된다.

    기하학적으로 정규직교 행렬 R^2를 A행렬로 변환한다면, 넓이는 $|\lambda_{1}\lambda_{2}|$로 변환되고 둘레는 ${{1}\over{2}}(|\lambda_{1}|+|\lambda_{2}|)$로 변환된 것을 의미한다.

  • 구글의 페이지랭크 알고리즘

    구글은 검색의 페이지 순위(rank)를 매기기 위해, 행렬 A의 가장 큰 고유값의 고유벡터를 사용한다. 페이지 랭크의 알고리즘은, 웹페이지 중요도를 연결되는 페이지의 중요도로 approximate할 수 있다는 아이디어를 사용한다.(Larry Page, et al., 1999) 이를 위해, 어떤 페이지와 어떤 페이지가 연결되어있는지, 연결된 그래프로 웹페이지를 표현한다. 페이지랭크 알고리즘은 ai를 가리키는 페이지의 수를 세어 ai의 가중치(중요도)를 계산한다. 그런 다음 사용자의 탐색 동작(navigation behavior)을 이 그래프의 transition matrix A에 의해 모델링되며, 이 행렬은 다른 웹 사이트에 어떤(클릭) 확률로 나타날지 표현한다.

    행렬 A는 모든 순위(중요도) 벡터 x에 대하여, x, Ax, A^2x로 이어질 때, x*로 수렴하는 특징이 있다. 그리고 이 수렴하는 벡터 x*가 A의 고유벡터이며, 대응되는 고유값은 1이다. x* 벡터의 크기를 1로 정규화하면, 확률로서 해석할 수 있다.

• 2차원에서 변환행렬 고유값 고유벡터의 변화에 따른 변화

  

Cholesky Decomposition/Factorization

---

숄레스키 분해는 Symmetric, Positive Definite Matrix에 대하여, 양의 실수에 제곱근을 하면 동일한 요소로 분해할 수 있듯이, 제곱근과 동일한 연산을 할 수 있으며 실전에서도 유용하게 사용할 수 있다.

머신러닝에 기반한 수치계산에서 중요한 도구이다. 예를 들어, 다변량가우시안 변수의 공분산행렬과 같이 Symmetric, Positive Definite Matrix은 자주 계산에 사용된다. 공분산행렬에 대한, 숄레스키 분해는 가우시안분포에서 샘플을 생성할 수 있게 해준다.

확률변수의 선형변환을 가능하게 하며, 이는 VAE와 같은 깊은 확률모델의 gradient를 계산과 같은 연산에 큰 도움을 준다.

또한, A를 $LL^T$로 분할 할 경우 determinant를 쉽게 구할 수 있다. 삼각행렬(triangular matrix)의 deteminant가 대각행렬의 곱이기 때문에 det(A) det(L)^2를 이용하면 된다.

Eigendecomposition and Diagonalization (고유값 분해와 대각화)

---

대각행렬은 대각성분이외에 모두 0인 행렬로, determinant, 제곱, 역을 계산할 때 쉽게 한다. 유사행렬의 정의는 가역행렬 P가 있고, $D=P^{-1}AP$를 만족한다면, A, D는 서로 유사행렬이라고한다는 것이다. 그리고, 고유값분해에서는 대각행렬이 고유값으로 구성된 점이 다르다.

• 성질

  제곱 계산이 쉬움, determinant값 계산이 쉬움

  

  

• 대각화 가능(Diagonalizable)

  행렬 A의 고유값으로 구성한 행렬 D에 대하여, $D = P^{-1}AP$을 만족하는 가역행렬 P가 있다면, A는 대각화가 가능하다고 한다.(def 4.19)

  이 때, AP = PD라는 것은 P가 A에 대한, 고유벡터로 구성될 때만 가능하며 이는 필요충분조건이다. 그리고 이는 아래의 의미를 내포한다.

  

  nxn 행렬 A에 대하여, 고유값 분해(eigendecomposition)는 A의 고유벡터가 R^n의 벡터공간의 기저를 구성할 때이며 이는 필요충분조건이다. (theorem 4.20)

  즉, non-defective(nxn 행렬의 고유벡터가 n개)인 행렬만 대각화가 가능하다.

  대칭행렬 S는 항상 대각화가 가능하다(theorem 4.21) (spectral theorem에 의함)

  추가로 어떤 행렬의 Jordan normal form은 defective matrix에 대하여, 대각화를 수행할 수 있게 한다. (https://bskyvision.com/188)

• 대각화의 기하학적 직관

  표준기저로부터의 사상을 행렬 A로 보면, $P^{-1}$은 기존기저에서 고유값에 대한 기저로의 변환이고, 대각행렬 D는 고유값으로의 크기변화(scaling)이다. P는 다시 표준기저로의 변환하는 역할을 한다.

  

• 예시

  

SVD

---

선형대수의 가장 기본이론이다. 항상 존재하며, 모든 행렬에 대해 구할 수 있다. SVD의 깊은 수학적 이해를 위해 아래 두 자료를 추천한다.

https://datajobs.com/data-science-repo/SVD-[Dan-Kalman].pdf

http://webéducation.com/wp-content/uploads/2018/06/Linear-Algebra-and-Matrix-Analysis-for-Statistics.pdf

SVD Review

https://www.youtube.com/watch?v=2HQ5Z1y0bEg&list=PLRCdqbn4-qwqqC-ksijw-PCQbt92pugvV

SVD는 차원축소 뿐만 아니라, Matrix completion, Matrix Factorization(행렬 분해) 등에 사용한다.

• Rank

  랭크란 intrinsic dimensionality이다

  rank가 1이라는 것은 열벡터(행벡터)끼리 어떤 하나의 벡터의 곱으로 나타낼 수 있어 자유도는 0이라는 것이다. rank 가 mxn 행렬에서 min(m,n)이면 full rank 라고 한다.

• SVD

  모든 mxn 행렬 A에 대하여 A행렬의 rank가 r인 경우 다음과 같이 분해가능하다

  • SVD 구하기

    $V^T$는 $A^{T}A$의 고유벡터로 구성되며, 시그마 행렬은 고유값의 루트값 그리고, U벡터는 아래와 같다. U행렬의 마지막 벡터는 $A^T$의 좌영공간(A의 left null space) 벡터를 그 벡터의 크기로 나눈 것과 같다

    

    https://www.youtube.com/watch?v=Ls2TgGFfZnU&t=129s

  

  

  또한 동일하게, D행렬(시그마 행렬)의 대각 원소를 통해 다음과 같이 표현할 수 있다. ui는 U행렬의 열벡터, vi 는 $V^T$ 행렬의 행벡터이다. 이것은 r개의 rank가 1인 행렬들을 더한 것으로 볼 수 있다. ($u_{1}v_{1}^T$는 rank가 1임)

  $A = \sum_{i=1}^{r} d_{i}u_{i}v_{i}^{T}$

  eigen value decomposition(고유값 분해)와 다른 점은 SVD의 대각행렬(D, 시그마)의 원소는 항상 양수인 것이다. singular value는 항상 양수이다. eigenvalue는 복소수나 음수일 수 있다.

  $A = \sum_{i=1}^{r} d_{i}u_{i}v_{i}^{T} = \sum_{i=1}^{n} d_{i}u_{i}v_{i}^{T}$

  그리고 1부터 n까지로 나타내고, $d_{r+1} , \cdots d_{n} = 0$ 으로 표현이 가능해, 여러 표현이 가능하며, 헷갈릴 수 있음.

  

• SVD와 관련된 행렬의 Norm

  l1, l2 - 벡터의 길이를 측정, infinity norm - 벡터의 박스(?)를 포착하듯이,

  이 3가지 노름은 행렬의 힘, 에너지, 크기 등을 측정한다고 볼 수 있으며 SVD와 관계가 있다.

  • Frobenius Norm(Hilbert Schmidt norm)

    

    벡터에서의 l2 norm처럼 프로비니우스 노름을 사용한다. 4번째 항은 SVD를 사용해 표현한 것이고, 5번째 항은 norm(a,b) = norm(b,a)인 노름의 성질을 이용한 것이다.

    따라서, A행렬의 SVD의 대각행렬의 제곱합이 프로비니우스 노름이며, dot product에서 유도된 것이다.

  • Operator Norm or Spectral Norm

    

    행렬 A의 singular value 중 가장 큰 값이 A의 operator norm이다. 또한 동일하게 A^T A나 AA^T의 가장 큰 고유값의 제곱근은 operator norm은 같다. PCA의 기본적인 아이디어가 operator norm을 사용한 것이다.

  • Nuclear Norm or Trace Norm

    

    A행렬의 singular value들의 합은 Nuclear Norm이다.

• Matrix Approximation

  SVD가 어떤 것을 하는지 이해하기 위해 Matrix Approximation을 아는 것은 중요하다.

  SVD는 best approximation을 제공한다.

  $\argmin_{B \ rank1} ||A-B||_{op} = d_{1}u_{1}v_{1}^{T}$

  A를 근사하는 가장 좋은 rank가 1인 행렬 B는 $d_{1}u_{1}v_{1}^T$ 이다. 그리고 op 노름(가장 큰 singular value)가장 큰 으로 계산한 에러는 d2(두번째로 큰 singular value)이다. 즉, 가장 큰 singular value와 singular vector가 가장 큰 에너지를 차지한다.

  유사하게 A에 근사하는 rank가 2이면서, 손실이 가장 작은 행렬 B는 $d1u1v1^T + d2u2v2^T$일 것이다.

  오차를 프로비니어스 노름으로 계산하면 다음과 같을 것이다. $||A-d_{1}u_{1}v_{1}^{T}||_{F} = \sqrt{\sum_{i=2}^{r}d_{i}^{2}}$

  → 결론적으로 rank k의 행렬과 프로비니어스 노름과 operator 노름으로 계산했을 때 가장 오차가 작은 행렬 B는 $\Sigma_{i=1}^{k} d_{i}u_{i}v_{i}^{T}$ 이다.

  rank가 줄기 때문에 굉장히 차원축소를 많이 할 수 있는 것이다.

  $u_{1}v_{1}^T$행렬과 $u_{2}v_{2}^T$의 행렬은 서로 직교하기 때문에 0 이다. 또한, $u_{i}v_{i}^T$는 행렬 A의 기저이며, 어떤 기저가 가장 중요한지 SVD 찾게 해준다.

---

→ SVD Review: SVD를 통해, Matrix Approximation을 수행할 수 있다. operator norm(singular value 중 가장 큰 값, A^TA의 고유값의 제곱근) , 프로비니우스 노름(대각성분의 제곱합의 제곱근)등의 기준을 통해, 우리가 원하는 기저의 수로 행렬을 근사하거나, 차원 축소를 할 수 있다.

위와 같이 SVD를 분해한다고 정의할 때, $V^T$는 기저 변환 행렬, 시그마는 차원 변환 및 크기변환(scaling), U는 기저 변환으로 볼 수 있음. SVD는 정의역과 공역(codomain)에서의 기저 변환을 표현하는 것이, 기저 변환한 뒤 취소하는 방식으로 수행하는 고유값분해와 다르다.

• SVD의 방법

  ref. http://savanna.korea.ac.kr/wp/?page_id=1085

  

• SVD, Eigenvalue Decomposition 비교

  

  • Symmetric한 행렬의 고유값 분해와 SVD는 Spectral Theorem에 의해 같다.

• SVD의 활용 예시

  

  3명의 사람이 4개의 영화에 대해 평점을 매긴 행렬 A를 고려해보자.

  SVD를 통해 행렬 A를 분해하면, 사람들이 영화를 어떻게 평가하는지, 특히 어떤 사람들이 어떤 영화를 좋아하는지 연결해주는 구조가 있다면 그 관계를 포착할 수 있는 방법이 제시된다.

  SVD를 데이터 행렬 A에 적용할 때의 가정

  • 모든 리뷰어는 동일한 선형 사상을 사용해, 영화를 일관적으로 평가한다.
  • 평점에는 에러나 노이즈가 없다.
  • left singular 벡터 ui를 stereotypical movie(영화의 변하지 않는 특징 벡터로 볼 수 있다는 느낌인듯)로, right singular 벡터 vj를 stereotypical viewer로 해석한다.

  이러한 위 가정 아래에서, 모든 평가자는 특정 영화에 대한 선호도를 vj에 대한 선형 결합으로 표현할 수 있고, 모든 영화의 선호현상은 ui벡터의 선형 결합으로 표현될 수 있다고 가정할 수 있다. 이는 SVD의 정의역의 벡터는 평가자들의 공간을 표현하고, SVD의 공역의 벡터는 영화의 공간을 표현한다. 이러한 두 공간은 리뷰어와 영화의 데이터가 충분히 다양할 때 더 의미 있게 표현된다.

  

  첫 번째 left-singular vector인 u1을 보면 2개의 SF영화에 대응하는 부분에 높은 절댓값을 가지며, 대각행렬 시그마의 특이값이 높게 나타남을 확인할 수 있다.(빨간 부분) 또한, $v1^T$는 SF영화에 높은 평점을 주는 Ali와 Beatrix에 큰 절대값을 보여준다.(초록색)

  비슷하게 u2를 보면 프랑스 예술 영화 주제를 포착하며, $v2^T$를 보면 Chandra가 해당 장르의 영화 장르를 좋아하는 것을 볼 수 있다.(파란색, $v2^T$의 -0.9807)

• SVD의 표현

  

  ref. https://blog.naver.com/PostView.nhn?blogId=tjdqja0508&logNo=222298714881

  MML에서는 thin SVD → reduced SVD로 표현

• SVD의 응용

  선형 연립방정식, 최소제곱법, 수치 반올림 오류에 강력한 계산, 작은 기저로의 행렬 근사화, 차원축소, 토픽모델링, 데이터 압축, 클러스터링 등.

• Matrix Approximation
  • Rank-r matrix

    

  • Rank-k Approximation

    

    

  • Spectral Norm

    

    행렬 A의 spectral norm은 singular value 중 가장 큰 값이다.

  • Eckart-Young Theorem: Rank-k Approximation의 오차 설명

    

    이 이론은 spectral norm과 SVD로 A를 근사하는 것이 가장 최적임을 보인다. 행렬의 적은 랭크의 근사는 많은 이미지 처리, 노이즈 제거, 해당도복원(ill-posed problem) 등의 ML 애플리케이션에 사용된다. 또한, PCA에서도 중요한 역할을 함.

  • 영화-리뷰어 행렬에서의 예시에서의 예시

    

    

정리

---

• 실수 행렬에 대해 pseudo-inverse와 SVD는 항상 존재

• 정방행렬(nxn)에 대해서 determinanat가 0이 아닌 경우, 가역행렬(Regular, Invertible, non-singular)이며, 0인 경우 비가역(Singular) 행렬이다.

• 정방행렬이 n개의 선형 독립인 고유벡터를 갖는 경우, non-defective(diagonalizable)하며, 고유값 분해를 할 수 있다. 그렇지 않는 경우는 defective하다고 하며, defective 행렬에 고유값이 있을 수 있지만 n개의 선형독립인 고유벡터를 갖지 않는 경우, 대각화는 할 수 없다. non-sigular와 non-defective 함은 드라다. 예를 들어, 회전 행렬은 가역행렬이지만, 대각화를 실수로는 보장되지 않는다. 또한, [[1, 1], [0, 1]] 행렬도 가역이지만, non-defective하다.

• non-defective 행렬은 normal condition으로 행렬을 구분할 수 있다. normal 조건은 $A^{T}A = AA^{T}$이 성립되는지 아닌지로 구분된다. 만약, $A^{T}A = AA^{T}= I$인 경우라면, A는 orthonormal한 행렬이며, 역행렬이 전치행렬인 경우이다.

• normal 행렬의 부분집합으로 기존 행렬 A와 A의 전치행렬이 같은 대칭행렬이 있다. 대칭행렬은 항상 실수 값의 고유값을 갖는다.

• 대칭행렬 중 $x^{T}Px > 0$이 항상 성립하는 경우, Positive-Definite 행렬이라고 한다. PDM은 항상 양수의 고유값을 가지며, 가역행렬이며 Cholesky decomposition $A=LL^{T}$를 수행하는 경우 L은 A에 unique하다.

• 응용과 추후 읽을 거리
  • determinant, eigenspace: 행렬을 분류하고 분석하기 위한 기본 조건 제공. 데이터를 표현하고, 데이터를 매핑할 때 수치 계산의 안정성 판단으로 확장 가능
  • Cholesky decomposition: random event 시뮬레이션하거나 계산할 때 사용(Rubinstein and Kroese, 2016) VAE에서 확률변수에 대해 continuous differentiation을 수행하는 데( reparametrization trick) 사용함.
  • 고유값분해: 선형 매핑을 특징짓는 의미 있고 해석 가능한 정보를 추출할 수 있도록 하는 데 필수. Positive-Definite 커널의 고유값을 분해하는 sepctral methods는 일반적인 ML 알고리즘의 기초이다. 이러한 spectral decompostion에는 PCA, FDA(Fisher discriminant analysis), MDS, Isomap, Laplacian eigenmaps, Hessian eigenmaps, spectral clustering와 같은 것들이 있다. 위와 같은 방법의 핵심 계산 방법은 SVD를 통해 low rank 행렬 근사 기술들과 함께 사용된다.
  • SVD: 독립변수(예측변수)를 전처리할 때, 손실 압축, 차원축소

    행렬을 고차원 배열로 확장한 것을 텐서라고 하는데, 텐서에서의 SVD와 유사한 연산은 Tucker 분해와 CP분해가 있다.

    SVD low-rank 근사는 기계학습의 계산효율성을 위해 자주 사용된다. 이는 0이 아닌 큰 행렬의 곱셈연산의 메모리와 연산량을 줄인다.