[알고리즘 구현으로 배우는 선형대수] #12. 대각화

 

대각..공격..!

1. 대각화의 개념 

• 행렬의 대각화 : 행렬을 대각 행렬로 만드는 것 
• 정사각 행렬 A에 대해, P-1AP가 대각 행렬이 되는 가역 행렬 P가 존재한다면 행렬 A은 대각화 가능 이라고 함 
• 행렬의 대각화 가능 여부 : 해당 행렬의 고유값 개수가 nxn 행렬에서 n개의 서로 다른 고윳값을 가져야 함 

2. 직교 대각화의 개념 

D = P-1AP = PtAP (D:대각행렬) 

• 행렬 A에 선형 변환(P,P-1)을 취한 결과 대각 원소만 남는 대각 행렬이 됨 
• 위 식을 만족하는 직교 행렬 P가 존재할 경우 
• A는 직교대각화 가능하며 직교 행렬 P가 A를 직교대각화하는 것임 
  • 조건1. 행렬A의 고유벡터는 n개의 정규 직교 벡터를 만족해야 함 
  • 조건2. A는 반드시 대칭 행렬이어야 함 
    • 대칭행렬이란 At=A인 행렬을 의미함 (ex. 공분산 행렬)

 

3. 고윳값 분해

• 고윳값 분해는 A = PDPt의 형태로 ,행렬을 고유 벡터, 고윳값의 곱으로 분해하는 것을 의미 (직교대각화의 한 종류) 
  • P : A의 고유 벡터로 이뤄진 직교행렬 (각각 고윳값에 해당하는 고유벡터들) 
  • 대각 행렬의 원소(람다) : 고윳값 

https://losskatsu.github.io/linear-algebra/svd/#4-%EA%B3%A0%EC%9C%A0%EA%B0%92-%EB%B6%84%ED%95%B4-%EB%B3%B5%EC%8A%B5

 

 

4. 특이값 분해 

• mxn 행렬도 고윳값 분해를 할 수 있도록 일반화 시킨 것. 주성분 분석(PCA) 같은 차원 축소에 많이 사용됨 
• 특이값 : 행렬의 고윳값에 루트를 씌운 것을 특이값이라 함

 

• 원리
  • p차원에서 차원 축소를 수행하여 d차원이라는 부분공간으로 변환시킨다고 할 때 
  • 데이터 - 부분공간의 수직 거리를 최소화시켜야 함 → 제곱합 통해 최소화 진행 
  • 제곱합 : At x A , A x At 를 수행하게 되면 원소간 제곱합이 진행됨 
  • 그러므로 특이값 분해에서는 이와 같은 제곱합을 다룸
    • A x At : nxp행렬 * pxn 행렬 → 행의 내적 
    • At x A : pxn * nxp → 열의 내적 

• 임의의 n×p 행렬 A를 A = UΣVT 로 분해하는 것
• U 는 n×n 직교 행렬 (A x At 의 고유벡터를 열로 구성)
• Σ 는 n×p 행렬로 처음 r개의 값이 특이값 σ1 ≥ σ2 ≥ … ≥ σr ≥ 0인 대각행렬
• V는 p×p 직교 행렬 (At x A 의 고유벡터를 행으로 구성)

https://losskatsu.github.io/linear-algebra/svd/#9-%ED%8A%B9%EC%9D%B4%EA%B0%92-%EB%B6%84%ED%95%B4%EB%9E%80

 

파이썬 실습 

# 고윳값 분해 실습 

#1. 넘파이 

import numpy as np 

A = np.array([[~~]])
E,V = np.linalg.eig(A) 

#E : 고윳값, V : 고유 벡터 


#2. QR분해로 고윳값 분해 

def eig_qr(A):
"""A가 대칭행렬일 때만 사용 가능"""

n = lean(A)
E = deepcopy(A)
V = identity(n) #단위행렬로 초기화. 추후 고유벡터로 업데이트됨 

for i in range(0,30): #임의의 수
	Q,R = qr_gram(E)  #E를 QR분해해서 할당 
    E = matmul(R,Q)   #E는 RQ행렬곱으로 업데이트 > 고유값 
    V = matmul(V,Q)   #V는 VQ행렬곱으로 업데이트 
    
return E,V


# 특이값 분해 실습 

#1. 넘파이 

B = [[~~]]

U,S,Vt = np.linalg.svd(B) 

#2. 파이썬 

def svd(A):
'''U=고유벡터, S = 특이값, Vt= AtA의 고유벡터'''

    At = transpose(A)
    AtA = matmul(At,A) 
    E,V = eig_qr(AtA)
    n = len(AtA)

    for i in range(0,n):        #고윳값 행렬 E를 이용해서 특이값 구하기(대각원소에 루트 취하기)
        E[i][i] = E[i][i]**0.5 
	s = diag(E)                 #행렬 E를 대각 행렬로 변환 
    Vt = transpose(V)           #고유벡터 행렬 V의 전치 행렬 구하기
    AV = matmul(A,V)            
    AVt = transpose(AV)
    UT = []                     #행렬 U구하기 위해 먼저 전치행렬 구하기 
    for vector in AVt:
    	Ut.append(normalize(vector))   #길이 1로 만들어서 정규화 
    U= transpose(Ut)
    return U,S,V