선형대수 용어 정리

매 번 볼 때는 기억이 나는데 조금 있으면 까먹는..... 기본적인 용어들을 정리해두기 위한 포스팅입니다. 간단한 정의, 특징 등을 정리하고자 합니다.

 

 

행렬로 나타낼 수 있는 연립방정식 풀기

  - Gaussian elimination

  - Cramer's rule

 

 

Linear independence

  - Vector 여러 개({$x_{i}$})가 있을 때, non-trivial한 linear combination 있으면 linearly dependent

    - $\vec{0} = \sum_{i=1}^n \lambda_{i}x_{i}$ with at least one $\lambda_{i} \neq 0$

      - 그래서 영벡터 있으면 정의에 따라 항상 linear dependent

  - Only trivial sol exists -> linearly independent

    - 위 식을 만족시키는 조건이 오직 {$\lambda_{i}$}=0이면, {$x_{i}$}는 서로 linear independent

    - 저 중 벡터 1개라도 제거하면, 무언가 정보를 잃게 됨(dimension이든, 만들 수 있는 정보든....)

  - Linear independent 확인하는 practical way: Gaussian elimination

    - Row-echleon form으로 만들고, column 개수와 pivot 개수 비교

 

 

Set, Span

  - Let vector space V, set of vectors A = {$x_{i}$} $\subseteq$ V

    - 모든 v $\in$ V가 $x_{i}$의 linear combination으로 만들어지면, "A는 V의 generating set"

    - 이 때 만들어지는 모든 linear combination vector들은 "span of A"

      - A가 vector space V를 span할 수 있다면, V = span[A] = span[$x_{i}$]

 

 

Basis

  - Vector space의 generating set 중 "Minimal set"

  - Basis == Minimal generating set == Maximal linearly independent set

    - Basis가 특정 vector space에 대해 unique하지는 않지만, dimension은 같음

  - 그러니까, 어떤 vector space를 구성할 수 있는 vector set

 

 

Dimension

  - Dimension of a vector space $\neq$ vector 내 원소 갯수

  - The dimension of vector space corresponds to the number of its basis vectors.

 

 

Rank

  - # of linear independent column(row)

  - Gaussian elimination을 통해 구한 pivot 개수

  - Matrix의 column들로 생성될 수 있는 vector space의 dimension

    - Basis의 개수에 의해 결정 -> 선형 독립인 column의 개수

    - 저렇게 생성되는 subspace를 image/range/column space

  - nxn vector space의 rank = n -> Invertible

  - Ax=b can solved <=> rank(A) = rank(A|b)

  - For mxn matrix A, subspace of solution for Ax=0의 dim = n-rank(A)

    - 이 subspace를 kernel/null space

 

 

Determinant

  - Square matrix에서만 정의 가능

  - 역행렬 존재 여부 판단 -> full rank

  - 넓이, 부피 계산

 

 

Norm

  - 벡터 크기의 일반화!

  - 조건 3개

    - Absolutely homogeneous: $\lVert \lambda x \rVert = \lvert \lambda \rvert \lVert x \rVert$

    - Triangle inequality: $\lVert x + y \rVert \leq \lVert x \rVert + \lVert y \rVert$

    - Positive definite: $\lVert x \rVert \geq 0 \; and \; \lVert x \rVert = 0 \iff x = 0$

 

  - Manhattan Norm($l_{1}$ norm)

    - $\lVert x \rVert_{1} = \sum_{i=1}^{n} \lvert x_{i} \rvert$

  - Euclidean Norm($l_{2}$ norm)

    - $\lVert x \rVert_{2} = \sqrt{\sum_{i=1}^{n} x_{i}^{2}} = \sqrt{x^{T}x}$

 

 

Gram-Schmidt Orthogonalization

  - Vector들이 주어졌을 때, 그것들에 대한 orthogonal/orthonormal basis를 구하자!

    - Projection 개념 사용

      - 이미 만들어 놓은 k개 orthogonal basis set에 모두 orthogonal한 k+1번째 basis를 projection 통해 생성

  - 두 벡터의 각도 정의

    - $cos w = \frac{<x,y>}{\lVert x \rVert \lVert y \rVert}$

  - Orthogonal, orthonormal

    - 두 벡터가 수직이면($cos w = 0 \ \Rightarrow \ <x,y> = 0$) orthogonal!

    - 여기에 $\lVert x \rVert = \lVert y \rVert = 1$이면, orthonormal!

  - 한 벡터를 기준점으로 잡고, 나머지 벡터들을 하나씩 projection 시켜서 orthogonal한 basis 생성

    - basis $b_{1} ... b_{n}$ 존재 -> orthogonal/orthonormal basis $u_{1} ... u_{n}$ 만들자!

    - $u_{1} = b_{1}$: 기준점

    - $u_{k} = b_{k} - \pi_{span[u_{1}, ... ,u_{k-1}]}(b_{k}),\ k = 2,...,n$

      - $\pi_{span[u_{1}, ... ,u_{k-1}]}(b_{k}) = \sum_{i=1}^{k-1}proj_{u_{i}}(b_k)$

      - 그러니까 k-1번 projection하면 됨!

Projection 예시, x를 b로 projection하자!

    - Vector b가 기준점이면, x를 b로 projection 시켜서 orthogonal basis를 만들 수 있음

      - Orthogonal의 정의를 이용해서, <$x - \pi_{U}(x), b$> = 0을 만족하는 $\pi_{U}(x)$를 구하자

      - $\pi_{U}(x)$는 vector b의 상수배니까 이를 $\lambda b$로 두면, <$x - \lambda b, b$> = 0 만족하는 $\lambda$ 구하면 됨

      - <$x - \lambda b, b$> = <$x, b$> - <$\lambda b, b$> = 0 만족하는 $\lambda$ = $\frac{<x,b>}{<b,b>}$ = $\frac{x^{T}b}{\lVert x \rVert^{2}}$

 

      - 좀 더 나가서, projection matrix까지 구해보자!

        - $\pi_{U}(x) = P_{x}x = \lambda b = b \cdot \frac{b^{T}x}{\lVert b \rVert^{2}} = \frac{bb^{T}}{\lVert b \rVert^2}x$, 결국 $P_{x} = \frac{bb^{T}}{\lVert b \rVert^{2}}$

 

 

Eigenvector, Eigenvalue

참고하면 (매우)좋은 블로그: 다크 프로그래머

  - Matrix A를 linear mapping으로 생각할 때, A에 의한 mapping 결과(Ax)가 0이 아닌 상수배($\lambda$)가 되는 벡터 x

    - $Ax = \lambda x, \lambda \neq 0$ : Eigenvalue equation

  - 이 때 가능한 $\lambda$가 eigenvalue

  - 가능한 $\lambda$에 따라 eigenvector x도 각각 존재

  - 다른 eigenvalue에 해당하는 eigenvector set -> Independent

 

  - 다음은 모두 동치

    - $\lambda$가 A(n*n)의 eigenvalue

    - 영벡터가 아닌 $Ax = \lambda x$ 만족하는 x 존재 <=> $(A-\lambda I_{n})x$ = 0은 non-trivial하게 풀림(ex. x $\neq \vec{0}$)

    - rank($A-\lambda I_{n}$) < n

    - det($A-\lambda I_{n}$) = 0

      - Non-trivial한 sol 존재하니까, $A-\lambda I_{n}$는 linear dependent

 

  - 어떻게 구하나?

    - $(A-\lambda I_{n})x$ = 0 -> $x \neq \vec{0}$이니까, $A-\lambda I_{n}$ 의 null space가 $\vec{0}$ 외에 다른 vector 포함

    - 그럼 $A-\lambda I_{n}$는 역행렬을 가지지 않음

    - det($A-\lambda I_{n}$) = 0

      - 이걸 만족하는 $\lambda$ 찾으면 eigenvalue!

    - 구한 eigenvalue들을 $(A - \lambda I_{n})x$에 넣어서 eigenvalue마다 eigenvector 구하기

      - Eigenvalue 1개 -> eigenvector가 1개 아닐 수 있음

        - 블로그 5절 예시에서는 $\lambda = 1$인 경우 eigenvector 2개(Geometric 2, Algebraic 2)

        - MML Ex 4.6에서는 2*2 행렬에서 eigenvalue 1개 - eigenvector 1개(Geometric 1, Algebraic 2)

          - Geometric multiplicity $\le$ Algebraic multiplicity

 

  -  Geometrical intuition

    - Matrix A를 linear mapping으로 생각하면,

      - Eigenvector: 보존되는 방향

      - Corresponding eigenvalue: eigenvector가 변하는 scale

 

 

Diagonalize

  - 대각화!

    - determinants, powers, inverse 등을 간단하게 연산 가능, 해석 용이!

 

 

Cholesky Decomposition

  - Symmetric, positive definite matrix A = $L^{T}L$로 분해

    - Positive definite matrix 정의: 영벡터가 아닌 모든 vector x에 대해, $x^{T}Ax > 0$

      - Positive (semi)definite matrix의 모든 eigenvalue는 0 이상 -> SVD에서 사용

    - Multivariate Gaussian variable의 covariance matrix가 해당

 

 

Eigendecomposition(Spectral decomposition)

  - 임의의 n*n Matrix $A = PDP^{-1}$

    - 가능한 조건: A가 n개의 linear independent한 eigenvector를 가져야 함

  - Eigenvalue 정의할 때 $Ax = \lambda x$

  - A의 eigenvector들을 column vector로 하는 matrix P, eigenvalue들을 대각성분으로 하는 대각행렬 D 정의

      - $AP = PD$ -> $A = PDP^{-1}$ 와 같이 표현 가능

 

  - 어떻게 구하나

    - Eigenvalue, eigenvector 구하기

    - 위 가능한 조건 만족하는지 체크

    - Eigenvectors 가지고 P, eigenvalues 가지고 D 만들기

 

 

Singular value Decomposition(SVD)

참고하면 (매우)좋은 블로그: 다크 프로그래머

  - Eigendecomposition(ED)가 일부 n*n matrix에 대해서만 가능했다면, SVD는 모든 matrix에 대해 가능

    - 임의의 matrix $A = U\Sigma V^{T}$ 로 분해 가능

      - U: $AA^{T}$의 eigenvector set

      - V: $A^{T}A$의 eigenvector set

      - $\Sigma$: A의 singular value를 대각성분으로 하는 대각행렬

        - Singular value: $AA^{T}, A^{T}A$의 eigenvalue의 square root

        - $AA^{T}, A^{T}A$는 모두 symmetric, positive semidefinite 보장(MML Theorem 4.14) -> eigenvalue는 모두 0 이상

          - Spectral theorem: Symmetric matrix A에 대해 A의 eigenvector를 포함하는 orthonormal basis 존재

            - 각 eigenvector에 해당하는 eigenvalue는 모두 실수

 

  -  Geometrical intuition

    - Linear mapping 관점에서, orthogonal matrix는 회전변환, diagonal matrix는 scale 변환

    - $V^{T}$에 의해 회전 변환 -> $\Sigma$에 의한 scale 변환 -> $U$에 의해 회전 변환

      - Singluar value는, 얼마나 scale 변환이 일어나는 지 의미

 

  - 어떻게 구하나?

    - $A^{T}A$의 eigenvector normalize해서 V 구하기

    - 그 과정에서 얻은 $A^{T}A$의 eigenvalue 통해 $\Sigma$ 구하기

    - $AV = U\Sigma$ 이용해서 U의 normalized column vector($u_{i} = \frac{1}{\sigma_{i}} Av_{i}$) 구하기

 

  - ED($A=PDP^{-1}$) vs SVD($B=U\Sigma V^{T}$) 비교

    - ED는 적용 가능한 matrix가 한정됨, SVD는 모든 matrix에 적용 가능

    - P는 orthogonal할 필요 없지만, U, V는 orthogonal해야 함 -> 그래야 회전 변환

    - 둘 다 basis change -> sacling -> basis change

      - SVD는 domain - codomain vector space의 dimension이 다를 수 있음