[스터디 노트] 15번째 선형대수 (241002), 제로베이스 데이터 분석 스쿨 내용

제로베이스 데이터 분석 스쿨 내용에 대한 기록이다.

15번째는 선형대수 강의이다.

 

[LU 분해]

• 분해
  • factorization, decomposition
  • 하나의 행렬을 2개 이상의 행렬 곱으로 표현한 식
  • A = BC
• LU decomposition
  • 방정식을 푸는 방법 중 하나
  • 행 줄임 (row reduction)으로 A를 LU 분해하여 방정식을 푼다.
  • L: a unit lower triangular matrix, 하삼각행렬
  • U: echelon form, 사다리꼴행렬
  • LU 분해 방법은 역행렬 방법보다 3배 빠르다.
• LU 디컴포지션으로 해 찾기
  • Ax=b
  • A=LU 이므로, LUx=b
  • Ux=y 로 치환하면, Ly=b
  • LUx=Ly=b 이다.
  • Ux에서 값을 구하면 y의 해가 나온다.
  • Ly에서 값을 구하면 x의 해 b를 찾을 수 있다.
  • L과 U는 변수를 0으로 만드는 쉬운 형태이므로, 빠르게 문제를 푸는 원리.
  • 차원 개념
    • x에 U를 곱해서 y로 옮기고 L을 곱해서 b로 옮긴다.
  • 요약
    • Ax=b
    • LUx=b, Ux로 y 구하기
    • L(y)=b, Ly로 b 구하기
• LU 구하는 방법
  • A가 row replacement만 이용해서 U가 될 수 있다고 가정하자.
  • U가 되기 위해서 많은 row operation을 하는데 이것들은 기본행렬의 집합 E들 이다.
  • 이 기본행렬 E들의 역행렬이 L이다.
  • 노가다 혹은 공식을 사용한다.
• LU의 형태
  • A = LU 인데, A의 형태가 (m x n)이면,
  • L의 형태는 (m x m)으로 정방이며 하삼각행렬 이다.
  • U의 형태는 (m x n)으로 사다리꼴행렬 이다.
• LU 분해 구하기 노가다
  • L은 하삼각행렬이 되어야 한다.
  • L의 단위행렬 요소에 1을 넣고, 오른쪽 위는 0을 채운다.
  • L의 나머지 부분은 상수 l_ab를 넣는다.
  • U는 사다리꼴 행렬이 되어야 한다.
  • U의 단위행렬 요소와 오른쪽 위에 상수 u_ab를 넣는다.
  • U의 나머지 부분을 0으로 채운다.
  • A = LU 로 두고 LU의 행렬곱을 연산한다.
  • 나온 방정식들을 연립방정식으로 풀어 모든 상수를 구한다.
• LU 분해 구하기 공식
  • 형태: A = (4 x 5)이면, L = (4 x 4), U = (4 x 5) 이다.
  • U 구하기
  • A에서 출발해서 사다리꼴행렬으로 만드는 과정
  • 1번째 컬럼 x_1에 대하여 2~4번째 행의 계수를 0으로 만든다.
  • 2번째 컬럼 x_2에 대하여 3~4번째 행의 계수를 0으로 만든다.
  • 4번째 컬럼 x_4에 대하여 4번째 행의 계수를 0으로 만든다.
  • 결과가 사다리꼴행렬으로 U를 구했다.
  • L 구하기
  • A의 요소를 가져와서 하삼각행렬으로 만드는 과정
  • A의 1번째 컬럼 요소만 가져온다.
  • 4개 요소를 가져왔으며, 1번째 행의 계수가 1이 되게 나눈다.
  • L의 1번째 컬럼으로 작성한다.
  • U를 만드는 과정에 2~4번째 행의 x_1 계수가 0이된 중간과정을 사용한다.
  • x_1의 계수가 0인 3개 행의 2번째 컬럼의 요소만 가져온다.
  • 3개 요소를 가져왔으며, 2번째 행의 계수가 1이 되게 나눈다.
  • L의 2번째 컬럼으로 작성한다.
  • U를 만드는 과정에 3~4번째 행의 x_2 계수가 0이된 중간과정을 사용한다.
  • x_2의 계수가 0인 2개 행의 3번째 컬럼의 요소만 가져온다.
  • 2개 요소를 가져왔으며, 3번째 행의 계수가 1이 되게 나눈다.
  • L의 3번째 컬럼으로 작성한다.
  • U를 만드는 과정에 4번째 행의 x_4 계수가 0이된 중간과정을 사용한다.
  • x_4의 계수가 0인 1개 행의 5번째 컬럼의 요소만 가져온다.
  • 1개 요소를 가져왔으며, 4번째 행의 계수가 1이 되게 나눈다.
  • L의 4번째 컬럼으로 작성한다.
  • 결과가 하삼각행렬으로 L을 구했다.
    
    

[행렬식]

• determinant, 역행렬이 있는지 결정
• det != 0 일때 역행렬이 존재 한다.
• 역행렬이 존재하는 것은 곧 해가 존재한다는 말이다.
• 추가 개념
  • rank: 행렬 A의 피벗 컬럼 개수 (=차원 수, dim 수)
  • pivot col: 피벗 컬럼, row reduction 후 x 계수가 살아있는 컬럼
  • null space: 피벗 컬럼이 아닌 컬럼
  • 전체 dim 수 = pivot col 수 + null space 수
  • rank 수 = pivot col 수
• 3x3 에서 det
  • 전자기학
  • det A = a_11 det A_11 - a_12 det A_12 + a_13 det A_13
• 여인수
  • cofactor, C_ij
  • 코팩터를 이용하면 det을 여러가지 형태로 표현할 수 있다.
  • 이것을 여인수 전개(cofactor expansion)이라고 한다.
  • C_ij = (-1)^(i+j) det A_ij 이다.
  • cofactor의 부호는 (-1)^(i+j)로 나타낸다.
  • (플러스와 마이너스가 격자형태로 진행되는 부호에 대한 행렬)
  • 따라서 det A = a_11 C_11 + ... + a_1n C_1n 이다.
  • 코팩터를 이용하면 임의의 row와 col으로 det을 표현할 수 있다.
  • 따라서 0이 많은 row나 col을 선택해서 det을 계산하면 된다.
• det과 곱셈
  • det AB = (det A)(det B)
  • 곱셈을 풀어서 det을 구한것과 값이 같다.
  • 덧셈은 보통 안된다.
  • det EA = (det E)(det A)
  • 기본행렬은 분해해서 빼낼 수 있다.
• 삼각행렬의 det
  • det A = a_11 a_22 a_33
  • 삼각행렬에서는 det A를 구할 때 A의 대각 텀을 곱하면 끝난다.
• 전치행렬의 det
  • A^(T) 전치행렬의 det은 det A와 동일하다.
    
    

[고유벡터와 고유값]

• Eigenvector, Eigenvalue
• 행렬과 어떤 벡터의 곱셈 결과 벡터가 동일한 선상에 존재하는 경우가 있더라.
• Ax = λx 를 만족하는 0이 아닌 벡터를 고유벡터 Eigenvector 라고 한다.
• x가 nontrivial solution을 가지고 있으면 (det != 0 이면) λ를 고유값 Eigenvalue라고 한다.
• 반대로 계산하면 (A - λI) = 0 이다.
• 아이겐벡터들은 모두 직교한다.
• 고유공간 Eigenspace
  • λ가 아이겐벨류 이면, (A-λI)=0은 solution을 가진다.
  • 고유공간 Eigenspace는 (A-λI)의 null space를 의미한다.
• 삼각행렬의 아이겐벨류
  • 삼각행렬의 아이겐벨류는 대각 텀의 값이다.
• 전치행렬의 아이겐벨류
  • A^(T) 전치행렬의 아이겐벨류는 A와 동일한 값이다.
    
    

[특성 방정식]

• characteristic equation
• det(A-λI)=0 을 특성방정식이라고 한다.
• λ가 특성방정식을 만족하면 λ는 행렬 A의 아이겐벨류 이다.
• 유사도 similarity
  • n차 방정식에서 아이겐벨류를 찾을때 사용한다.
  • A = PBP^(-1) 일때, A는 B에 similar 하다.
  • similarity transformation, A = P^(-1)BP로 변환하는 작업.
  • A와 B가 similar 이고, 동일한 특성을 가지면 같은 아이겐벨류를 가진다.
  • similar 한 경우에 아이겐벨류는 같지만 아이겐벡터 스페이스가 다르다.
  • det(A-λI) = det(B-λI)
    
    

[대각화]

• diagonalization
• 정사각행렬 A가 대각행렬 D와 similar 하면, A를 대각화 가능하다.
• A = P^(-1)DP 일 때, A를 diagonalizable 이라고 한다.
• D는 대각 텀만 가지고 있는 정사각형이다.
• A를 D로 만드는 과정을 대각화 diagonalization 이라고 한다.
• P는 아이겐벡터로 구할 수 있는 아이겐 매트릭스 이다.
• A는 n개의 아이겐벡터를 가지고 있고 이 컬럼들을 이어 붙인게 P 이다.
• D는 주대각선에 A의 아이겐벨류들을 하나씩 적은 것이다.
• A = PDP^(-1) 이므로 AP=PD 로 나타낼 수 있다.
• 이 형태는 Ax=λx 와 관련이 있다.
  
  

[대칭 행렬의 대각화]

• 대칭 행렬
  • symmetric matrix
  • A^(T) = A
  • 정사각행렬이고 전치 행렬이 자기 자신과 같은 행렬이다.
  • 주대각선을 기준으로 요소가 거울상으로 같다.
• 대칭 행렬 대각화
  • 대칭행렬에서 아이겐벡터들은 모두 직교한다.
  • 대칭행렬에서 아이겐벡터들은 선형 독립 집합이다.
  • 과정
    • 아이겐벡터를 정규화하고 직교 벡터로 표현한다. (그람-슈미트)
    • 아이겐벡터를 이어 붙여서 P를 만든다.
    • D는 주대각선에 A의 아이겐벨류들을 하나씩 적은 것이다.
    • 이때 P는 모든 컬럼이 직교하므로 P^(T) = P^(-1) 이다.
    • 따라서 A를 대각화 할 때 A=PDP^(T) 로 나타내도 된다.
• 스펙트럼 정리
  • A의 아이겐벨류 집합 D를 A의 스펙트럼이라고 한다.
  • A가 대칭행렬일 경우에 다음 4개 정리를 따른다.
  • A가 n개의 아이겐벨류를 가지고 있으면 multiplicity를 계산할 수 있다.
  • 아이겐 스페이스의 차원은 아이겐벨류의 multiplicity와 동일하다.
  • 아이겐 스페이스는 서로 직교하고, 아이겐벡터도 직교한다.
  • A는 orthogonally 대각화 가능 하다.
• 스펙트럼 분해
  • spectral decomposition
  • 스펙트럼은 곧 D이고 이건 아이겐벨류 이다.
  • A를 아이겐벨류로 표현되는 조각들로 분해하는 것이다.
  • 과정
    • A = P^(-1)DP 이므로, A=PDP^(T)로 나타낼 수 있다.
    • A를 PD와 P^(T) 의 곱으로 표현한 것을 스펙트럼 분해라고 한다.
      
      

[특이값 분해]

• SVD, singular value decomposition
• 대칭 행렬의 대각화는 대칭에서만 가능하고 정사각행렬만 가능하다.
• SVD는 행렬의 크기와 상관없이 가능하다.
• (m,n) 크기의 행렬 A의 특이값 singular values 구하는 방법
  • A^(T)A은 (n,n) 크기의 대칭행렬이 된다.
  • 대칭행렬은 전치를 해도 원래 행렬이 되는 특징이 있다.
  • A^(T)A 행렬을 대각화 -> 아이겐벨류 λ 구하기 -> 루트 씌우기
  • 이 결과가 A행렬의 특이값 이다.
• A = U Σ V^(T) 로 표시한다. (PDP^(T)와 같은 형태)
• Σ
  • 시그마 행렬
  • (m,n) 크기
  • (r,r) 크기의 대각 요소가 곧 특이값(루트 λ)
  • 각 특이값을 σ_1, ..., σ_n 로 나타낸다.
• U
  • left singular 벡터
  • Av_1, ..., Av_r 을 정규화한 벡터들로 이루어진 행렬
  • 구성은 u_1, ..., u_m 이다.
• V
  • right singular 벡터
  • A^(T)A의 정규 직교 아이겐벡터로 이루어진 행렬
  • 구성은 v_1, ..., v_n 이다.
• 예시
  • A = (2, 3) 크기
  • A^(T)A 계산하면 (3,3) 크기
  • 이걸 대각화하면 아이겐벨류와 아이겐벡터를 구할 수 있다.
  • 아이겐벨류에 루트를 씌우고 A행렬 크기에 맞추면 Σ 이다.
  • 아이겐벡터는 그대로 V 이고 전치행렬 V^(T)를 구한다.
  • Av_1에 특이값 σ_1을 나눠 정규화 하면 그게 u_1이 된다.
  • m번 반복해서 U를 완성한다.
  • A = U Σ V^(T) 이다.
    
    

[정성적 의미]

• 고유값 분해
  • eigenvalue decomposition
  • 행렬을 아이겐벨류와 아이겐벡터로 분해한다.
  • 변환에서 주 축을 찾는다.
  • PCA에서 차원 축소에 사용한다.
  • 데이터에서 중요한 정보만 남기고 압축한다.
• LU 분해
  • LU decomposition
  • 행렬을 두개의 구조(L, U)로 분해한다.
  • 대규모 데이터를 효율적으로 계산한다.
  • 선형 회귀에서 계산을 최적화한다.
• SVD
  • singular value decomposition
  • 모든 행렬에 대하여 가능하며 3개의 행렬(U, Σ, V)로 분해한다.
  • 데이터의 차원을 축소할 수 있다.
  • 데이터에 노이즈를 제거하고 중요한 패턴을 찾을 수 있다.
  • 추천 시스템에서 숨겨진 특징을 찾아낼 수 있다.
  • 고차원 이미지를 품질을 유지한 채로 낮은 차원으로 축소할 수 있다.

 

 

깃허브 링크

 

깃허브 선형대수 공부 부분 링크