27.36 행렬 분해(Matrix Factorization)의 개요와 분류

1. 행렬 분해의 개념

행렬 분해(matrix factorization 또는 matrix decomposition)는 주어진 행렬을 특정 구조를 가진 두 개 이상의 행렬의 곱으로 표현하는 것이다. 행렬 \mathbf{A}를 \mathbf{A} = \mathbf{B}\mathbf{C} 또는 \mathbf{A} = \mathbf{B}\mathbf{C}\mathbf{D} 등의 형태로 분해한다.

행렬 분해의 목적은 크게 세 가지이다.

첫째, 연산 효율성이다. 원래 행렬에 대한 연산이 복잡한 경우, 구조가 단순한 인자 행렬들을 통해 더 효율적으로 수행할 수 있다. 예를 들어, LU 분해를 통해 연립방정식 풀이를 삼각 행렬 시스템으로 환원하면 반복적 풀이가 효율적이다.

둘째, 구조 분석이다. 분해를 통해 행렬의 본질적 구조, 즉 계수, 고유값, 특이값 등을 파악할 수 있다. 이는 데이터의 잠재적 패턴이나 차원 구조를 이해하는 데 핵심적이다.

셋째, 수치적 안정성이다. 직접적 계산보다 분해를 거친 계산이 반올림 오차에 더 강건한 경우가 많다.

2. 주요 행렬 분해의 분류

행렬 분해는 대상 행렬의 종류와 분해의 목적에 따라 다양하게 분류된다.

2.1 삼각 분해 계열

LU 분해: 일반 정사각 행렬 \mathbf{A}를 하삼각 행렬 \mathbf{L}과 상삼각 행렬 \mathbf{U}의 곱으로 분해한다.

\mathbf{A} = \mathbf{L}\mathbf{U} \quad \text{또는} \quad \mathbf{P}\mathbf{A} = \mathbf{L}\mathbf{U} \quad (\text{피벗팅 포함})

주요 용도는 연립방정식 풀이와 행렬식 계산이다. 복잡도는 O(n^3/3)이다.

촐레스키 분해(Cholesky Decomposition): 대칭 양의 정부호 행렬 \mathbf{A}에 대하여 \mathbf{A} = \mathbf{L}\mathbf{L}^\top으로 분해한다. \mathbf{L}은 양의 대각 원소를 가지는 하삼각 행렬이다. LU 분해의 약 절반인 O(n^3/6)의 연산량을 가지며, 수치적으로도 더 안정적이다.

LDL 분해: 대칭 행렬을 \mathbf{A} = \mathbf{L}\mathbf{D}\mathbf{L}^\top으로 분해한다. \mathbf{D}는 대각 행렬이고, \mathbf{L}은 단위 하삼각 행렬이다. 양의 정부호 조건 없이 대칭 행렬에 적용 가능하며, 제곱근 연산이 불필요하다.

2.2 직교 분해 계열

QR 분해: 임의의 m \times n 행렬 (m \geq n)을 직교 행렬 \mathbf{Q} \in \mathbb{R}^{m \times n}과 상삼각 행렬 \mathbf{R} \in \mathbb{R}^{n \times n}의 곱으로 분해한다.

\mathbf{A} = \mathbf{Q}\mathbf{R}

여기서 \mathbf{Q}^\top\mathbf{Q} = \mathbf{I}_n이다. QR 분해는 최소 제곱 문제, QR 알고리즘(고유값 계산), 직교 정규화 등에 사용된다. 계산 방법으로는 그람-슈미트 과정, 하우스홀더 반사(Householder reflection), 기븐스 회전(Givens rotation) 등이 있으며, 하우스홀더 방법이 O(2mn^2 - 2n^3/3)의 복잡도로 가장 널리 사용된다.

슈어 분해(Schur Decomposition): 정사각 행렬 \mathbf{A}를 유니타리 행렬 \mathbf{Q}와 상삼각 행렬 \mathbf{T}를 사용하여 \mathbf{A} = \mathbf{Q}\mathbf{T}\mathbf{Q}^*로 분해한다. 모든 정사각 행렬은 슈어 분해를 가지며, \mathbf{T}의 대각 원소가 고유값이다. 실수 행렬의 경우 실수 슈어 형식(real Schur form)으로 분해할 수 있다.

2.3 스펙트럼 분해 계열

고유값 분해(Eigendecomposition): 대각화 가능한 정사각 행렬 \mathbf{A}를 \mathbf{A} = \mathbf{P}\boldsymbol{\Lambda}\mathbf{P}^{-1}로 분해한다. 대칭 행렬의 경우 \mathbf{A} = \mathbf{Q}\boldsymbol{\Lambda}\mathbf{Q}^\top으로, \mathbf{Q}가 직교 행렬이 되어 더 안정적이다.

특이값 분해(SVD, Singular Value Decomposition): 임의의 m \times n 행렬 \mathbf{A}를 다음과 같이 분해한다.

\mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^\top

여기서 \mathbf{U} \in \mathbb{R}^{m \times m}과 \mathbf{V} \in \mathbb{R}^{n \times n}은 직교 행렬이고, \boldsymbol{\Sigma} \in \mathbb{R}^{m \times n}은 비음수 대각 원소(특이값)를 가지는 대각 행렬이다. SVD는 모든 행렬에 대해 존재하며, 행렬의 가장 보편적이고 강력한 분해이다.

3. 분해 방법 비교

4. 근사적 행렬 분해

정확한 분해가 아닌, 주어진 행렬을 근사적으로 분해하는 기법도 중요하다.

절단된 SVD(Truncated SVD): r개의 최대 특이값만 유지하여 \mathbf{A} \approx \mathbf{U}_r\boldsymbol{\Sigma}_r\mathbf{V}_r^\top으로 근사한다. 에크하르트-영 정리에 의하여 이것이 프로베니우스 노름과 스펙트럼 노름 모두에서 최적의 순위 r 근사이다.

비음수 행렬 분해(NMF, Non-negative Matrix Factorization): 비음수 행렬 \mathbf{A} \in \mathbb{R}_{\geq 0}^{m \times n}을 두 비음수 행렬의 곱 \mathbf{A} \approx \mathbf{W}\mathbf{H}로 근사한다 (\mathbf{W} \in \mathbb{R}_{\geq 0}^{m \times r}, \mathbf{H} \in \mathbb{R}_{\geq 0}^{r \times n}). 비음수 제약으로 인해 부분 기반(part-based) 표현이 가능하며, 문서 주제 추출이나 이미지 분석에 활용된다.

무작위화 행렬 분해(Randomized Matrix Decomposition): 대규모 행렬에 대하여, 무작위 사영(random projection)을 통해 차원을 줄인 후 분해를 수행하는 기법이다. Halko, Martinsson, and Tropp (2011)의 논문 “Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions“에서 체계화된 이 접근법은, O(mnr) 복잡도로 순위 r 근사를 수행하여 대규모 데이터에 적합하다.

5. 딥러닝에서의 행렬 분해

행렬 분해는 딥러닝의 모델 설계, 학습, 압축 전반에 걸쳐 활용된다.

가중치 분해(Weight Factorization): 대규모 가중치 행렬 \mathbf{W} \in \mathbb{R}^{m \times n}을 \mathbf{W} \approx \mathbf{W}_1\mathbf{W}_2 (\mathbf{W}_1 \in \mathbb{R}^{m \times r}, \mathbf{W}_2 \in \mathbb{R}^{r \times n}, r \ll \min(m,n))로 분해하면, 매개변수 수가 mn에서 (m+n)r로 감소하고, 행렬-벡터 곱의 복잡도도 O(mn)에서 O((m+n)r)로 줄어든다.

추천 시스템: 사용자-아이템 상호작용 행렬 \mathbf{R} \in \mathbb{R}^{U \times I}을 사용자 잠재 인자 행렬 \mathbf{P} \in \mathbb{R}^{U \times k}와 아이템 잠재 인자 행렬 \mathbf{Q} \in \mathbb{R}^{I \times k}의 곱 \mathbf{R} \approx \mathbf{P}\mathbf{Q}^\top으로 분해하는 것은 행렬 분해 기반 협업 필터링의 기본 원리이다. 이 접근법은 Netflix Prize 등에서 우수한 성능을 보였다.

어텐션의 저순위 근사: 트랜스포머의 어텐션 행렬 \text{softmax}(\mathbf{Q}\mathbf{K}^\top/\sqrt{d})을 저순위로 근사하여 시퀀스 길이에 대한 복잡도를 줄이는 연구들이 있다. 커널 기반 접근에서 \text{softmax}(\mathbf{Q}\mathbf{K}^\top) \approx \phi(\mathbf{Q})\phi(\mathbf{K})^\top으로 근사하면, 어텐션 계산이 O(L^2d)에서 O(Ld^2) 또는 O(Lrd)로 감소한다.

사전 학습 모델의 분석: 학습된 가중치 행렬의 SVD를 수행하여 특이값 분포를 분석하면 모델의 유효 차원과 표현 능력을 파악할 수 있다. 특이값이 빠르게 감소하는 가중치 행렬은 저순위 근사에 적합하며, 이를 통해 모델 압축의 여지를 정량적으로 평가할 수 있다.