[ZB] 선형대수 - chap3. 선형대수학

• 선형대수학을 통해 어떻게 데이터의 해를 찾아 나가는지
• ★★★ LU분해, 고유벡터, 대각화, 특이값 분해(SVD)

1. 선형 방정식

• 선형방정식(Linear Equation)
  $a_1x_1 + a_2x_2 + \cdots + a_nx_n = b$
  
• 비선형 방정식 (Nonlinear Equation)
  • 딥러닝, 알고리즘, 트리
    $4x_1 - 5x_2 = x_1x_2$
    $x_2 = 2\sqrt{x_2} -6$

1. 선형 방정식 계 (A system of linear equation)
   : 같은 변수들을 포함한 선형방정식이 1개 또는 그 이상의 집합
   → 계수와 변수 나누어서 행렬로 표현 가능

2. 해의 집합 (Solution set)
   : 선형시스템에서 모든 가능한 해의 집합

   • 같은 solution set을 갖는 선형방정식 간의 관계 = 행 상등(equivalent)
   • 해가 없다 ( Inconsistent) ↔ 해가 있다 ( consistent)

   <행 의 관점>

   1. no solution - 평행
   2. exactly one solution
   3. infinitely many solution - 일치
   • 2개의 해가 존개하는 경우 : 비선형인 경우

3. 행렬표기법 ( Matrix Notation )
   $x_1 - 2x_2 + x_3 = 0$
   $2x_2 - 8x_3 = 8$
   $5x_1 - 5x_3 = 10$
   → 행렬
   $\begin{bmatrix} 1&-2&1\\0&2&-8\\5&0&-5 \end{bmatrix} \begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix} = \begin{bmatrix} 0\\8\\10 \end{bmatrix}$
   = 계수행렬

   • 계수행렬(coefficient matrix) : b를 제외하고 a(등호 왼쪽)만을 행렬로 나타낸 것
   • 첨가행렬(augmented matrix) : b까지 포함한 행렬
     $\begin{bmatrix} 1&-2&1&0\\0&2&-8&8\\5&0&-5 &10\end{bmatrix}$
     

2. 해를 찾기

1. 소거법(Elimination)

   1. 행 관점과 열 관점의 이해

      1. n=2
         $\begin{cases} 2x - y = 1\\x + y = 5 \end{cases}$

         1. 행 관점
            $\begin{bmatrix} 2&-1 \\1&1 \end{bmatrix} \begin{bmatrix} x\\y \end{bmatrix} = \begin{bmatrix} 1\\5 \end{bmatrix}$

         2. 열 관점
            $x\begin{bmatrix} 2\\1 \end{bmatrix} + y\begin{bmatrix} -1\\1\end{bmatrix} = \begin{bmatrix} 1\\5 \end{bmatrix}$

            첫번째 벡터 $\vec{a}= (2, 1)$
            두번째 벡터 $\vec{b} = (-1, 1)$
            해 $\vec{c} = (1, 5)$

            → $2(2, 1) + 3(-1, 1) = (1, 5)$
            → $2\vec{a} + 3\vec{b} = \vec{c}$
            → $x = 2, y = 3$

      2. n=3

         1. 행 관점 row picture : 평면들의 교차점(intersection of plans)
         2. 열 관점 column picture : 열들의 결합(combination of columns)

   2. 소거법(Elimination)
      : 행 연산(row operation)을 통해 소거법 → 선형방정식의 해를 구함

      • 가우스 소거법
        • 행 상등 일 때
        • 기본 행 연산
          • scaling - 0이 아닌 상수를 행에 곱할 수 있다
          • interchange - 두 행을 교환할 수 있다
          • replacement - 한 행을 상수배 하여 다른 행에 더할 수 있다
        • 상하 삼각행렬 만들어 해를 찾아 삼각행렬 = $\begin{bmatrix} 1&1&1\\0&1&1\\0&0&1\end{bmatrix}$와 같이 0이 이루는 삼각형 존재, 대각행렬=1
          

        1. 선형 방정식 계를 행렬로 표현

           $\begin{cases} x_1-2x_2+x_3=0\\2x_2-8x_3=8\\5x_1-5x_3=10\end{cases}$ → $\begin{bmatrix} 1&-2&1&0\\0&2&-8&8\\5&0&-5&10\end{bmatrix}$(첨가행렬)

        2. 마지막 행의 $x_1$ 계수를 0으로 만듦 ( 삼각행렬 만들어주기 위함)

           $-5\times equation1 + equation3 = new equation3$

           $\begin{cases} x_1-2x_2+x_3=0\\x_2-4x_3=4\\10x_2-10x_3=10\end{cases}$ → $\begin{bmatrix} 1&-2&1&0\\0&1&-4&4\\0&10&-10&10\end{bmatrix}$

        3. 마지막 행의 $x_2$ 계수를 0으로 만듦

           $-10\times equation2 + equation3 = new equation3$

           $\begin{cases} x_1-2x_2+x_3=0\\x_2-4x_3=4\\30x_3=-30\end{cases}$ → $\begin{bmatrix} 1&-2&1&0\\0&1&-4&4\\0&0&30&-30\end{bmatrix}$

        4. 마지막 행의 $x_3$ 계수를 1로 만듦

           $\begin{cases} x_1-2x_2+x_3=0\\x_2-4x_3=4\\x_3=-1\end{cases}$ → $\begin{bmatrix} 1&-2&1&0\\0&1&-4&4\\0&0&1&-1\end{bmatrix}$

           → 상삼각행렬 만들어짐

        5. $x_3$을 알았으므로 대입을 통해 $x_1, x_2$ 구함

           $x_1=1, x_2=0, x_3=-1$

           $\begin{bmatrix} 1&-2&1&0\\0&2&-8&8\\5&0&-5&10\end{bmatrix} \rightarrow \begin{bmatrix} 1&0&0&1\\0&1&0&0\\0&0&1&-1\end{bmatrix}$

        • 변수가 엄청 많아질 때 → 어떤 행을 먼저 소거해나갈지
          • Pivot을 어떻게 할 것인지. optimization(최적화)
2. 특이 경우 The Singular Case
   1. row picture
   1. 해가 없는 경우
   - two parallel planes
   - 세 개의 평면이 평행하지 않는 경우 - no intersection
   - 세 개의 평면이 평행한 경우 all planes parallel
   2. 해가 무수히 많은 경우
   - line of intersection
   2. 시스템이 특이할 때 - column picture에서
   - 해 X - 세 개의 column이 동일한 평면에 놓이고 b는 다른 평면에 위치할 때
   - 무수한 해 - b가 세 개의 column과 동일한 평면에 놓여져 있을 때
   
   

3. 역행렬

1. 역행렬이 존재하는 행렬(Invertible Matrix)

   $AA^{-1}=I\quad and \quad A^{-1}A=I$

   • 조건 :
     • Row와 Column의 size 동일
     • $AC=I$인 $C$행렬이 유일하게 존재해야.
   • 역행렬이 존재하지 않으면 해가 존재하지 않는 행렬임
     (not invertible matrix = singular matrix)

2. 결정자(Determinant) - 2×2 행렬의 결정자( det=ad-bc )

   • determinant=0이면 not invertible
   • $A$가 2×2 행렬일 때 ad-bc≠0 이면 $A$는 invertible (ad-bc=0이면 not invertible)
     
   • $A$ = invertible [n×n] matrix이면 b에 대하여 $R^n$의 $Ax=b$는 유일한 해를 갖는다
     $x = A^{-1}b$ : 역행렬을 구하는 이유 (해를 빠르게 구하기 때문)
     $\big( Ax=b \Leftrightarrow A^{-1}Ax=A^{-1}b \Leftrightarrow Ix=A^{-1}b \Leftrightarrow x=A^{-1}b \big)$
     
   • $A$=invertible matrix이면, $A^{-1}$=invertible matrix
     $(A^{-1})^{-1}=A$
     $(AB)^{-1}=B^{-1}A^{-1}$
     
   • $A$=invertible matrix이면, $A^{T}$=invertible matrix
     $(A^T)^{-1}=(A^{-1})^T$
     

3. 기본행렬 (Elementary Matrix) = $E$

   : 항등행렬(identity matrix)($I$)에 단일 기본 행 연산(row operation)을 적용한 것

   • 기본 행 연산 : replacement, interchange, scaling
   • 특징
     $A = \begin{bmatrix}a&b&c\\d&e&f\\g&h&i\end{bmatrix}\qquad E_1 = \begin{bmatrix}1&0&0\\0&1&0\\-4&0&1\end{bmatrix}$
     $E_2 = \begin{bmatrix}0&10\\1&0&0\\0&0&1\end{bmatrix}\qquad E_3 = \begin{bmatrix}1&0&0\\0&1&0\\0&0&5\end{bmatrix}$
     $E_1$ = replacement 적용
     $E_1A$는 $A$에 replacement 적용한 것과 동일 값
     $E_2$ = interchange 적용
     $E_3$ = scaling 적용
     $E_3A$는 는 $A$에 scaling 적용한 것과 동일 값
     
     
     • [m×n]행렬 $A$에 elementary row operation 수행 = $EA$ = [m×m] elementary matrix $E$ 존재 $A$에 적용한 row operation을 [m×m] 행렬 $I$에 적용 → $E$
       
     • $E$ = invertible matrix이면, $E^{-1}$ = invertible matrix

4. $A^{-1}$를 찾는 알고리즘 (Algorithm for finding $A^{-1}$) - [3×3] 행렬에서 사용

   [m×n]행렬 $A$가 invertible → $I$를 이용해 $A^{-1}$ 구함

   $[A\quad I]$에 row operation을 적용하면서 $A$를 $I$로 만들어 줌
   → $I$ 자리의 행렬 = $A^{-1}$가 됨 $[I \quad A^{-1}]$의 형태로

5. 역행렬의 특징

   • 역선형 변환( Invertible Linear Transfmation) 선형 변환(Linear Transformation) $T$는 항상 표준행렬 $A$가 존재
     • $T$ = invertible → $A$ = invertible
     • 선형변환 함수 : $S(x) = A^{-1}x$

4. ★★★ LU decomposition

• 분해(Factorization, Decomposition) : 하나의 행렬을 2개 or 3개 이상의 행렬 곱으로 표현한 식
  $A=BC$
  
• 방정식을 푸는 방법
  1. $A$의 역행렬을 이용 ($x=A^{-1}b$) - 비효율적
  2. 행 줄임(row reduction)으로 A를 LU분해
     $A=LU$ 형태로 분해
• L : a unit lower triangular matrix(하삼각행렬)
  U : echelon form(사다리꼴 행렬)
  

1. LU분해

   : $L$과 $U$는 pivot을 사용해서 나머지 entry를 0으로 만들 수 있는 쉬운 형태이므로 빠르게 문제 풀 수 있음

   $A=LU, \quad Ax=b\quad \Leftrightarrow \quad LUx=b$
   → $Ux=y$ 치환
   $Ly=b, \quad Ux=y \quad \rightarrow \quad$ L을 통해 y 구함 → x 구함

   ★ $Ly=b$ 에서 $y$ 구하는 것
   $[L\quad b]$ 를 통해 $y$ 구함 ( $L$ : 삼각행렬이므로 쉽게 구할 수 O)

2. LU 구하는 방법 (LUdecomposition Algorithm)

   1. A가 row replacement만을 통해 사다리꼴 형태($U$)로 변환될 수 있다고 가정

   2. U로 변환하기 위한 행 줄임(row operation) 기본행렬 $E_1, \cdots, E_p$ 존재

      $E_p\cdots E_1A=U$
      $A=(E_p\cdots E_1)^{-1}U=LU$

   3. $E$의 역행렬 = $L$

      $L=(E_p\cdots E_1)^{-1}$

   $A$ = [m×n] → $L$ = [m×m], $U$ = [m×n]

   • 예시 (2×2) - 가우스 elimination
     $\begin{bmatrix}4&3\\6&3\end{bmatrix} = \begin{bmatrix}1&0\\l_{21}&1\end{bmatrix} \begin{bmatrix}u_{11}&u_{12}\\0&u_{22}\end{bmatrix}$ → 미지수 : $l_{21}, u_{11}, u_{12}, u_{22}$
     
     $\begin{cases} u_{11} = 4 \\ u_{12}=3\\l_{21}u_{11}=6\\l_{21}u_{12}+u_{22}=3 \end{cases}$ $\begin{cases} l_{21}=1.5\\u_{11} = 4 \\ u_{12}=3\\u_{22}=-1.5 \end{cases}$
     

• 예시 (4×4) - LU분해
  $A=\begin{bmatrix}2&4&-1&5&-2\\-4&-5&3&-8&1\\2&-5&-4&1&8\\-6&0&7&-3&1\end{bmatrix}$ → L = [4×4] ,U= [4×5]
  1. A를 row replacement 통해 U
     <replacement 과정>
     $A_1=\begin{bmatrix}2&4&-1&5&-2\\0&3&1&2&-3\\0&-9&-3&-4&10\\0&12&4&12&-5\end{bmatrix}$
     $A_2=\begin{bmatrix}2&4&-1&5&-2\\0&3&1&2&-3\\0&0&0&2&1\\0&0&0&4&7\end{bmatrix}$
     $U=\begin{bmatrix}2&4&-1&5&-2\\0&3&1&2&-3\\0&0&0&2&1\\0&0&0&0&5\end{bmatrix}$ (사다리꼴 형태)
     

2. L = A 각각의 pivot column에서 pivot 아래의 entry를 pivot으로 나눠줌pivot column = $\begin{bmatrix}2\\-4\\2\\-6\end{bmatrix} \begin{bmatrix}3\\-9\\12\end{bmatrix} \begin{bmatrix}2\\4\end{bmatrix} \begin{bmatrix} 5\end{bmatrix}$$L=\begin{bmatrix} 1&0&0&0\\-2&1&0&0\\1&-3&1&0\\-3&4&2&1\end{bmatrix}$
   
3. $A=LU$ 완성
4. $Ly=b$로 $y$값 O ($Ux=y$)
5. $Ux=y$로 $x$값 O
   • $A$=sparse( 0값이 많음 ) → $L, U$ =sparse & $A^{-1}$=dense

5. 행렬식 개요

행렬식 = determinent

• Rank : A의 column space의 dimension(차수) A → row reduction → 사다리꼴 행렬 E → pivot column 찾음 *pivot column : 대각행렬에 값이 들어있는 것
  
• Pivot 개수 = Rank
• Null space 개수 = 전체 dimension - Rank = free variable 개수와 같음

1. 행렬식

   1. 2×2

      $A=\begin{bmatrix}a&b\\c&d\end{bmatrix}\qquad detA=ad-bd$

   2. 3×3이상

      • det ≠ 0 : 모든 row에 pivot 존재 row reduction 진행 후 모든 pivot이 nonzero임 을 확인
        
      • $detA = a_{11}\cdot detA_{11} - a_{12}\cdot detA_{12} + a_{13}\cdot detA_{13} \cdots$ $A_{11}$ : $A$에서 row1과 column1을 제외한 행렬 → $A$가 sparse 하면 보통 이 방법을 사용
        

2. 여인수 (Cofactor)

   Cofactor을 이용해 determinant를 여러가지 형태로 표현 = 여인수전개(cofactor expansion)

   $A=[a_{ij}], \quad (i, j):cofactor$

   $C_{ij} = (-1)^{i+j}\cdot detA_{ij}$

   < $detA = a_{11}C_{11}+a_{12}C_{12}+\cdots+a_{1n}C_{1n}$ >

   • 임의의 row와 column으로 표현 → 0이 많은 row|column 선택 → 계산 빨라짐

3. det EA = (det E)(det A)

4. A=삼각행렬 → det A = A의 대각행렬 곱한 것

5. 특징

   1. row operation

      1. $A$에 row replacement 하여 $B$가 되었을 경우 $det A =detB$

      2. $A$의 두 row가 interchange되어 $B$가 되었을 경우 $det A =-detB$

      3. $A$의 하나의 row에 k가 곱해져 $B$가 되었을 경우(scaling) $detB=k\cdot detA$

      4. $B$= $A$에 row reduction하여 만들어진 사다리꼴 행렬 → $B=EA$

         $detEA= \alpha \cdot detA (\alpha=1, -1, k)$

   2. cofactor expansion → n!의 연산 필요

      row operation + cofactor expansion → 삼각행렬 대각행렬 곱해보면 행렬의 해 존재유무 알 수 O

   3. $detA≠0 \quad \rightarrow \quad A=invertible$

   4. $detA^T=detA$

   5. $detAB=(detA)(detB)$ - 역선형변환

6. 고유벡터(eigenvector)와 고유값(eigenvalue)

어려워 . .

$A=\begin{bmatrix} 3&-2\\1&0\end{bmatrix}, v=\begin{bmatrix}2\\1\end{bmatrix}$

$Av=\begin{bmatrix}4\\2\end{bmatrix}=2\begin{bmatrix}2\\1\end{bmatrix}$

2 = 고유값, $\begin{bmatrix}2\\1\end{bmatrix}$= 고유벡터

1. 고유벡터 Eigenvector

   $Ax=\lambda x$ 를 만족하는 nonzero vector $x$=eigenvector

   • $Ax=\lambda x$에서 $x$가 비자명해(nontrivial solution)가 존재할 때 - $\lambda$=eigenvalue, $x$ = 이에 상응하는 eigenvector
   • 비 자명해 ( nontrivial solution) : free variable을 가질 때 ( =’det=0’일 때 ) 비자명해를 가짐
     • free variable X → unique solution → eigenvalue = 1, eigenvecor = 자신
     • free variable O → infinitely many solution = 같은 line에 존재한다 = 이에 따른 eigenvalue, eigenvector
       

   1. 행렬 $u, v$가 $A$의 eigenvector인지 판단

      $Ax=\lambda x$를 만족하는지 확인

   2. 7이 eigenvalue인지 판단

      $Ax=7x\Leftrightarrow Ax-7x=0\Leftrightarrow(A-7I)x=0$

      • $x$=nonzero vector여야 + 식이 nontrivial solution이 존재하는지 파악
      • 좌변 → row reduction → free variable 존재하는지 파악

2. 고유공간 Eigenspace

   $\lambda$가 $A$의 eigenvalue이면, $(A-\lambda I)x=0$은 nontrivial solution 가짐

   $\lambda$에 해당하는 $A$의 eigenspace = $A-\lambda I$ 행렬의 null space

   • eigenspace = zero vector + $\lambda$에 해당하는 eigenvectors
   • basis :
   • 예시- 행렬 $A$에 대하여 $\lambda=2$에 해당하는 eigenspace, basis 찾기
     $A=\begin{bmatrix}4&-1&4\\2&1&6\\2&-1&8\end{bmatrix}$
     $A=2I =\begin{bmatrix}2&-1&6\\2&-1&6\\2&-1&6\end{bmatrix}$ $\begin{bmatrix}2&-1&6&0\\2&-1&6&0\\2&-1&6&0\end{bmatrix}\sim\begin{bmatrix}2&-1&6&0\\0&0&0&0\\0&0&0&0\end{bmatrix}$
     $\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}=\begin{bmatrix}0.5x_2-3x_3\\x_2\\x_3\end{bmatrix}=x_2\begin{bmatrix}0.5\\1\\0\end{bmatrix}+x_3\begin{bmatrix}-3\\0\\1\end{bmatrix}$
     $\{\begin{bmatrix}0.5\\1\\0\end{bmatrix},\begin{bmatrix}-3\\0\\1\end{bmatrix}\}$ = basis ( 두 vector가 independent set), 두 개의 vector = eigenvector , independent vector
     

3. 행렬 $A$에 의한 곱셈

   $\lambda=2$인 eigenspace에 존재하는 임의의 vector 4개를 선택해서 행렬 $A$를 곱하면 크기가 2배가 됨

4. 특징

   • 삼각행렬의 eigenvalues는 대각형
     • $A$=상삼각행렬(upper triangular matrix)
       • $\lambda=a_{11} ~~or~~ a_{22}~~or~~ a_{33}$
     • $A$=하삼각행렬
       • $A$와 $A^T$가 동일한 eigenvalue 가짐 ($A$와 $A^T$의 diagonal term 같으므로)

5. 특성 방정식 characteristic equation

   $det(A-\lambda I)=0$

   $\lambda$가 특성방정식을 만족하면 $\lambda$는 $A$의 eigenvalue

   • 유사도 similarity : $A=PBP^{-1}$일 때, $A$는 $B$에 similar
     • n차방정식에서 eigenvalue를 찾기 어렵기 때문
     • similarity transformation : $A=PBP^{-1}$로 변환하는 것
   • eigenvalue 찾을 때 similar한 행렬(특수한 성질을 갖는)을 찾아서 eigenvalue 찾음
   • 보통 eigenvalue는 같고 eigenspace는 다름
   • $A$와 $B$가 similar 하고, 동일한 특성을 가지면 두 행렬은 동일한 eigenvalue
     $B=P−1AP$
     $B−λI=P^{−1}AP−λP^{−1}P=P^{−1}(AP−λP)=P^{−1}(A−λI)P$
     $det⁡(B−λI)=det⁡[P^{−1}(A−λI)P]$
     $\qquad =det⁡(P^{−1})⋅det⁡(A−λI)⋅det⁡(P)$
     $det⁡(P^{−1})⋅det⁡(P)=det⁡(P^{−1}P)=det⁡(I)=1$
     $det(B−λI)=det(A−λI)$
     

7. 대각화(Diagonalization)

• 대각화 가능하다 = 정사각행렬 $A$가 대각행렬과 유사(similar)하다 $A=P^{-1}DP$ 일 때
  
• 연산을 단순하게 해 줌
• 대각행렬의 제곱은 대각행렬 각 요소의 제곱과 같음
  $D=\begin{bmatrix}a&0\\0&b\end{bmatrix}\qquad D^k=\begin{bmatrix}a^k&0\\0&b^k\end{bmatrix}$
  
• $A$가 $D$와 유사하면 $A^k$ 구하기가 쉬움

1. 특징
   • $n\times n$행렬 $A$ : diagonalizable = $A$는 n개의 linearly independent eigenvector 가짐 $A=P^{-1}DP$ ( $D$:대각행렬) 이면,
     1. $P$의 column은 $A$의 n개의 eigenvector로 이루어짐
     2. $D$의 diagonal entries는 $P$를 구성하는 eigenvector 각각에 대한 $A$의 eigenvalues
2. 방법
   1. 행렬의 eigenvalues를 찾기
      • 특성 방정식($det(A-\lambda I)=0$)을 이용해서
   2. 행렬의 eigenvector 찾기
      • $\lambda$에 대한 basis
      • $(A-\lambda I)x=0$의 general solution → eigenvector → eigenspace→ basis
      • n개인지 확인( n개보다 작으면 대각화 불가)
   3. $A$의 eigenvector로 $P$를 구성
   4. $D$ = diagonal entries가 eigenvalues인 행렬
      • $P$의 eigenvector에 해당하는 eigenvalue를 diagonal entry로 ( 순서에 맞추어서)

---

1. 대칭행렬의 대각화

   1. 대칭행렬

      : 행렬 $A$가 정사각행렬 이고,

      $A^T=A$ 를 만족하는 행렬

      • 대각화
        • 고유벡터는 직교(orthogonal) & 선형 독립 집함
        • 3개의 벡터를 정규화(normalize) - 그람-슈미트 과정을 통해 → 직교vector로 표현
        • $P$:직교vector로 이루어진 행렬, $D$:대각이 eigenvalue로 이루어진 행렬
          • $P$의 column이 직교 vector이기 때문에 $P^T=P^{-1}$
        • $A$행렬 대각화 → $A=PDP^T$
      • $A$행렬이 대칭행렬이면, 고유벡터는 직교 $v_1\, v_2$가 각각 $\lambda_1, \lambda_2$에 대응하는 고유벡터일 때, $v_1*v_2=0$
        
      • 직교 대각화 가능
        • $A=PDP^T=PDP^{-1}$이면 $A$는 orthogonally diaonalizable
        • P : 정규직교벡터로 이루어진 직교 행렬, $P^T=P^{-1}$

   2. 스펙트럼 정리

      • $A$의 고유 값 집합 = $A$ 스펙트럼
      • 각 고유값에 대한 고유공간(eigenspace)의 차원 = 고유값의 multiplicity
      • 고유공간은 서로 직교

   3. 스펙트럼 분해(Spectral Decomposition)

      • 행렬 $A$를 eigenvalue로 표현되는 조각들로 분해하는 것
        $A=\lambda1u_1u^T_1 +\lambda_2u_2u^T_2 +\cdots+\lambda_nu_nu^T_n$
        $u_ku^T_k$는 Rank가 1인 n×n 행렬
        

8. 특이값 분해(SVD)(Singular Value Decomposition)

1. Σ 정의

   $\Sigma = \begin{bmatrix}D&0\\0&0\end{bmatrix}$

   • 크기가 m×n 행렬
   • r×r 크기의 대각요소 = 특이값인 대각행렬 D 포함 ( r < m,n )

2. SVD

   $A=U\Sigma V^{-1}$

   1. 행렬의 크기와 상관없이 대각화 가능 - m×n 행렬 대각화 가능

      m×n 행렬 $A$의 특이값( singular values) = $\sqrt{A^TA의 고유값}$ = σ

      • $A^TA$는 n×n 크기 대칭행렬(symmetric matrix), 직교 대각화 가능
      • σ = $Av_1, Av_2, Av_3, \cdots, Av_n$ 벡터의 길이($Ax=\lambda x$의 $\lambda$와 같아)

   2. $U$ = $\{Av_1, Av_2, Av_3, \cdots, Av_n\}$을 정규화한 $\{u_1, u_2, u_3, \cdots, u_r\}$벡터가 열로 이루어진 행렬

      = $A$의 left singular vector

      $u_i=\frac{1}{||Av_i||}Av_i=\frac{1}{\sigma_i}Av_i$

   3. $V$= $A^TA$의 정규직교 고유벡터가 열들로 이루어진 행렬

      = $A$의 right singular vector

   • 예시 $A=\begin{bmatrix}4&11&14\\8&6&-2\end{bmatrix}$

     1. $A^TA$를 직교대각화 → 고유값과 정규직교 고유벡터 찾음 → $A$의 특이값, 행렬 $V$

        $\sigma_1=6\sqrt{10}, \quad \sigma_2=3\sqrt{10}, \quad \sigma_3=0$

        $V=\begin{bmatrix}v_1&v_2&v_3\end{bmatrix}=\begin{bmatrix}1/3&-2/3&2/3\\2/3&-1/3&-2/3\\2/3&2/3&1/3\end{bmatrix}$

        $\Rightarrow D=\begin{bmatrix}6\sqrt{10}&0\\0&3\sqrt{10}\end{bmatrix}\qquad \Sigma=\begin{bmatrix}D&0\end{bmatrix}=\begin{bmatrix}6\sqrt{10}&0&0\\0&3\sqrt{10}&0\end{bmatrix}$

     2. $U$행렬

        $u_1=\frac{1}{\sigma_1}Av_1=\frac{1}{6\sqrt{10}}\begin{bmatrix}18\\6\end{bmatrix}=\begin{bmatrix}3/\sqrt{10}\\1/\sqrt{10}\end{bmatrix}$

        $u_2=\frac{1}{\sigma_2}Av_2=\frac{1}{3\sqrt{10}}\begin{bmatrix}3\\-9\end{bmatrix}=\begin{bmatrix}1/\sqrt{10}\\-3/\sqrt{10}\end{bmatrix}$

        $A=\begin{bmatrix}3/\sqrt{10}&1/\sqrt{10}\\1/\sqrt{10}&-3/\sqrt{10}\end{bmatrix} \begin{bmatrix}6\sqrt{10}&0&0\\0&3\sqrt{10}&0\end{bmatrix} \begin{bmatrix}1/3&2/3&2/3\\-2/3&-1/3&2/3\\2/3&-2/3&1/3\end{bmatrix} =U\Sigma V^T$

3. Reduced SVD

   = $U,V$ 행렬을 r까지만 표기한 것

   • $D$의 크기 = r×r
     • r+1행, r+1열부터는 값 = 0
     • r을 초과하는 인덱스는 0과 곱해져 0이 되므로
   • $A=\begin{bmatrix}U_r&U_{m-r}\end{bmatrix}\begin{bmatrix}D&0\\0&0\end{bmatrix}\begin{bmatrix}V^T_r\\V^T_{n-r}\end{bmatrix}=U_rDV^T_r$

4. 유사역행렬(Pseudo inverse)($A^+$)

   $A^+=V_rD^{-1}D^T_r$

   • reduced SVD가 Transpose 된 것
   • $\hat{x}$은 $Ax=b$의 최소제곱법 $\hat{x} =A^+b=V_rD^{-1}U^T_rb$ $A\hat{x}=U_rU^T_rb$
     • $U_r$ : b를column $A$에 projection한 것과 동일

<Gilbert - Linear Algebra>

https://youtu.be/ZK3O402wf1c?si=kNIgt_SUYheZqgey