Lecture 3 | Linear Algebra Review 2

형태

Math

수강 일자

2022/09/12

Gram Matrix

G=A^TA = \begin{bmatrix} a_1^Ta_1 & a_1^Ta_2 & \dots & a_1^Ta_n \\ a_2^Ta_1 & a_2^Ta_2 & \dots & a_2^Ta_n \\ \vdots & \vdots & \ddots & \vdots \\ a_n^Ta_1 & a_n^Ta_2 & \dots & a_n^Ta_n \\ \end{bmatrix}

•

Gram Matrix 가 identity 면 AAA 는 orthonormal

Skew Symmetric Matrix

A^T = -A

•

Transpose 가 negative 과 같은 matrix

•

Symmetric 은 AT=AA^T =AAT=A

•

Cross product 는 skew symmetric matrix 로 표현될 수 있음

a\times b =[a]_{\times}b= \begin{bmatrix} 0 & -a_3 & a_2 \\ a_3 & 0& -a_1 \\ -a_2 & a_1 & 0 \\ \end{bmatrix} \begin{pmatrix} b_1 \\ b_2 \\ b_3 \\ \end{pmatrix} = \begin{pmatrix} a_2b_3 - a_3b_2 \\ a_3b_1 - a_1b_3 \\ a_1b_2 - a_2b_1 \\ \end{pmatrix}

◦

이런 식의 표현이 중요한 이유는 모든 것을 matrix multiplication 으로 통합하여 표현할 수 있도록 해주기 때문

Null Space

{\mathcal N} (A) = \{ x\in \mathbb R^n : Ax =0\}

•

Matrix A∈Rm×nA \in \mathbb R^{m\times n}A∈Rm×n 의 nullspace 는 해당 matrix 와 right multiplication 을 했을 때 0 이 나오는 모든 벡터의 set

•

중요한 이유는 많은 AI 문제에서 AAA 가 주어졌을 때 optimal 한 xxx 를 구하는 경우가 많기 때문

•

SVD 를 이용해서 null space 를 찾을 수 있음!

•

Rank-Nullity Theorem

{\rm Rank}(A) + {\rm Nullity}(A) = n

Determinant

|A| = \sum_{i=1}^n (-1)^{i+j}a_{ij} |A_{\backslash i, \backslash j}|

•

∣A∣=∣AT∣|A| =|A^T|∣A∣=∣AT∣

•

∣AB∣=∣A∣∣B∣|AB| =|A||B|∣AB∣=∣A∣∣B∣

•

A∈Rn×nA \in \mathbb R^{n\times n}A∈Rn×n 에 대해서 ∣A∣=0|A|=0 ∣A∣=0 은 AAA 가 singular 인 것이랑 동치임

•

A∈Rn×nA \in \mathbb R^{n\times n}A∈Rn×n 에 대해서 AAA 가 non-singular 이면 ∣A−1∣=1/∣A∣|A^{-1}| = 1/|A|∣A−1∣=1/∣A∣ 

Quadratic Forms

x^TAx = \sum_{i=1}^n x_I(Ax)_i = \sum_{i=1}^n (\sum_{j=1}^n A_{ij}x_j) = \sum_{i=1}^n\sum_{j=1}^n A_{ij}x_ix_j

•

Quadratic Forms 로 표현되는 matrix 는 symmetric 임 

•

Conic 의 quadratic form 표현

ax^2 + bxy +cy^2 + dx+ ey+ f =0

x^TCx = 0 \\ x = (x,y,1)^T \\ C = \begin{bmatrix} a & b/2 & d/2 \\ b/2 & c & e/2 \\ d/2 & e/2 & f\\ \end{bmatrix}

Positive Semidefinite

•

Positive Definite (PD)

x^TAx > 0, \forall x \ne 0\in \mathbb R^n

•

Positive Semidefinite (PSD)

x^TAx \ge 0, \forall x \in \mathbb R^n

•

Negative Definite (ND)

x^TAx < 0, \forall x \ne 0\in \mathbb R^n

•

Negative Semidefinite (NSD)

x^TAx \le 0, \forall x \in \mathbb R^n

•

Indefinite

PSD 도, NSD 도 아닌 경우

Eigenvalues and Eigenvectors

Av = \lambda v

•

Square matrix AAA 에 대해서 위 식을 만족하는 nonzero vector vvv 와 λ\lambdaλ 쌍이 존재하면 vvv 를 eigenvector, λ\lambdaλ 를 해당 eigenvector 의 eigenvalue 라고 함

•

vvv 가 eigenvector 면 svsvsv 도 eigenvector 이기 때문에 보통은 ∥v∥2=1\|v \|_2 = 1∥v∥2​=1 을 가정하고 eigenvector 를 정의함

•

Characteristic polynomial

◦

(λI−A)v=0(\lambda I-A)v = 0(λI−A)v=0 의 non-zero solution vvv 가 존재하려면 det(λI−A)=0{\rm det}(\lambda I-A)=0det(λI−A)=0 이어야 함

P_A(\lambda)={\rm det}(\lambda I -A) = 1 \times \lambda^n + c_{n-1} \times \lambda^{n-1} + \dots + c_0

◦

위 식을 characteristic polynomial of AAA 라고 함

•

tr(A)=∑i=1nλi{\rm tr}(A) = \sum_{i=1}^n \lambda_itr(A)=∑i=1n​λi​

•

∣A∣=∏i=1nλi|A| = \prod_{i=1}^n \lambda_i∣A∣=∏i=1n​λi​

•

rank of AA A 는 non-zero eigenvalues of AAA 의 개수와 같음

•

AAA 가 non-singular 하고 λ\lambdaλ 라는 eigenvalue 를 가지면 A−1A^{-1}A−1 은 1/λ1/\lambda1/λ 라는 eigenvalue 를 가짐

•

Diagonal matrix DDD 의 eigen value 는 그냥 diagonal term 들임

Eigen Value Decomposition

•

A∈Rn×nA \in \mathbb R^{n\times n}A∈Rn×n 이고 VVV 를 AAA 의 n 개의 eigenvector 를 column 에 모아둔 matrix 라 하자

•

Eigenvector, eigenvalue 의 정의 때문에 다음이 성립함

AV = V{\rm diag}(\lambda)

•

최종적으로 AAA 는 다시 다음과 같이 표현할 수 있음

◦

가정에 의해 VVV 는 invertible 함 (linearly independent 한 nnn 개의 column)

A = V{\rm diag}(\lambda)V^{-1}

•

모든 symmetric matrix 는 nnn 개의 orthonormal 한 eigenvector 를 가지고, eigenvalue 는 모두 real 임 → real valued eigenvector 및 eigenvalue 로 Eigen Value Decomposition 가능!

◦

AAA 는 unit space 를 v(i)v^{(i)}v(i) 방향으로 λi\lambda_iλi​ 만큼 scaling 한 것과 같음

•

Convention 에 따라서 diagonal matrix 는 descending order 로 정렬됨

•

0 인 eigenvalue 가 존재하면 해당 matrix 는 singular 함. (Av=0v=0Av=0v=0Av=0v=0 인 nonzero vvv 가 존재하는 것이기 때문)

•

Positive Definite Revisited

◦

AAA 가 positive definite 하면, 모든 eigenvalue 는 positive 함

◦

AAA 가 positive semidefininte 하면, 모든 eigenvalue 는 non-negative 함

Bx=\lambda x \rarr x^TBx = x^T\lambda x = \lambda \|x\|_2^2 \ge 0

Singular Value Decomposition

A = U\Sigma V^T

•

UUU: m×mm\times m m×m orthonormal matrix

•

VTV^TVT: n×nn\times nn×n orthonormal matrix

•

Σ\SigmaΣ: m×nm\times nm×n diagnoal matrix

•

AAA 가 non-square 이면 Eigen Value Decomposition 이 정의되지 않음

•

SVD non-square 에도 적용될 수 있는 A=UDVTA = UDV^T
A=UDVT 형태의 decompostion

Reduced SVD

•

A∈Rm×nA \in \mathbb R ^{m\times n}A∈Rm×n 

•

m>nm > nm>n

A = U_R\Sigma_R V^T

◦

UUU 가 VVV 보다 크기가 크고 Σ\SigmaΣ 는 아래쪽 영역이 모두 0이 됨

◦

Reconstruction 만 생각한다면 UU U 의 좌측, Σ\SigmaΣ 의 위만 잘라서 사용가능

•

n>mn > mn>m

A = U\Sigma_R V_R^T

◦

UUU 가 VVV 보다 크기가 작고 Σ\SigmaΣ 는 우측 영역이 모두 0이 됨

◦

Reconstruction 만 생각한다면 VV V 의 위, Σ\SigmaΣ 의 좌측만 잘라서 사용가능

Relation between SVD and Eigen Value Decomposition

\begin{align*} A^TA &= (U\Sigma V^T)^T(U\Sigma V^T) \\ &= (V\Sigma^T U^T)(U\Sigma V^T) \\ &= V\Sigma^T \Sigma V^T \\ &= V\Sigma^2 V^T \end{align*}

•

A=UΣVTA = U\Sigma V^TA=UΣVT 로 SVD 가 이루어졌다고 가정하자

•

VVV 의 column 은 ATAA^T AATA 의 eigenvector 들임

•

Σ2\Sigma^2Σ2 의 diagonal term 은 ATAA^T AATA 의 eigenvalue 들임

•

마찬가지로, UUU 의 column 은 AATAA^TAAT 의 eigenvector 들임

•

Singular value 는 항상 nonnegative

◦

ATAA^TA ATA 의 eigenvalue 의 square root 로 볼 수 있는데 ATAA^TAATA 가 positive semidefinite 이기 때문에 eigenvalue 가 0 이상임!

Understanding Transformation via SVD

Applications of SVD

•

Matrix 의 rank 를 판단할 수 있음

◦

nonzero singular value 의 개수가 rank

◦

zero singular value 가 없으면 k=min⁡(m,n)k=\min(m,n)k=min(m,n) 의 full rank 를 가짐

•

Pseudo-inverse (left inverse of AAA) 를 쉽게 나타낼 수 있음

A^{\dagger} = (A^TA)^{-1}A^T

◦

AAA 가 square 라면 A−1A^{-1}A−1 로 표현할 여지도 있음

◦

A=UΣVTA = U\Sigma V^TA=UΣVT라고 하면 A†A^{\dagger}A† 는 다음과 같이 표현됨

\begin{align*} A^{\dagger} &= (V\Sigma^T U^T U\Sigma V^T)^{-1} (U\Sigma V^T)^T \\ &= (V\Sigma^T\Sigma V^T)^{-1} V\Sigma^T U^T \\ &= V\Sigma^T \Sigma V^T V\Sigma^T U^T \\ &= V\Sigma^T \Sigma \Sigma^T U^T \\ &= V\Sigma^{\dagger}U^T \end{align*}

•

Low-Rank Approximation

\min_{A_k} \|A-A_k\| \thickspace\thickspace\thickspace {\rm such\ that} \thickspace\thickspace\thickspace {\rm rank}(A_k) \le k

◦

k≤min⁡(m,n)k \le \min(m,n)k≤min(m,n)

◦

Rank 를 줄이면서 비슷한 matrix 를 만드는 과정

◦

가장 좋은 approximation 은 kkk 미만의 크기를 가지는 index 의 singular vector 및 singular value 를 버리는 것

A_k = \sigma_1 u_1 v_1^T + \sigma_2 u_2 v_2^T + \dots + \sigma_k u_k v_k^T

▪

σ1≥σ2≥σ3⋯≥0\sigma_1 \ge \sigma_2 \ge \sigma_3 \cdots \ge 0σ1​≥σ2​≥σ3​⋯≥0

▪

∥A−Ak∥2=∥σk+1uk+1vk+1T+σk+2uk+2vk+2T+⋯+σnunvnT∥2=σk+1\|A-A_k\|_2 = \| \sigma_{k+1}u_{k+1}v_{k+1}^T + \sigma_{k+2}u_{k+2}v_{k+2}^T + \dots 
+ \sigma_{n}u_{n}v_{n}^T\|_2 = \sigma_{k+1}∥A−Ak​∥2​=∥σk+1​uk+1​vk+1T​+σk+2​uk+2​vk+2T​+⋯+σn​un​vnT​∥2​=σk+1​

◦

Image Compression 등에 사용

Polynomial Fitting

\hat f(x)=\theta_1 + \theta_2x +\dots + \theta_p x^{p-1}

•

Sample 을 polynomial model 로 설명하려는 경우를 생각해볼 수 있음

•

AAA 를 Vandermonde Matrix 라고 부름

A = \begin{bmatrix} 1 & x^{(1)} & \dots & (x^{(1)})^{p-1} \\ 1 & x^{(2)} & \dots & (x^{(2)})^{p-1} \\ \vdots & \vdots & & \vdots \\ 1 & x^{(N)} & \dots & (x^{(N)})^{p-1} \\ \end{bmatrix}

•

θ\thetaθ 를 구함에 있어 데이터로 구성된 AAA matrix 를 활용함!