6.42 행렬의 랭크 근사와 저랭크 근사

1. 도입

대규모 행렬을 다루는 문제에서 원래 행렬의 모든 정보를 그대로 유지하는 것은 종종 비효율적이거나 불필요하다. 많은 경우 행렬의 본질적인 정보는 그 형식적인 차원보다 훨씬 낮은 유효 차원에 집중되어 있으며, 적절한 저랭크 근사(low-rank approximation)를 통하여 본질을 보존하면서 계산량과 저장 공간을 크게 절감할 수 있다. 저랭크 근사는 데이터 압축, 잡음 제거, 차원 축소, 그리고 모델 차수 축약의 수학적 토대를 이루며, 그 이론의 핵심에는 특이값 분해와 에크하르트-영 정리가 있다.

2. 행렬의 랭크와 유효 랭크

행렬의 랭크는 일차 독립인 열(또는 행)의 최대 개수로 정의된다. 그러나 실제 응용에서는 측정 잡음, 부동 소수점 오차, 그리고 모델링의 불완전성으로 인하여 명목적으로는 만랭크인 행렬이 본질적으로는 저차원의 정보만을 담고 있는 경우가 흔하다. 이러한 상황을 정량화하기 위하여 유효 랭크(effective rank) 또는 수치적 랭크(numerical rank)의 개념이 도입된다.

행렬 $A$ 의 특이값을 $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_{\min(m,n)}$ 라 하자. 임계값 $\epsilon > 0$ 에 대한 유효 랭크는 다음과 같이 정의된다.

$r_\epsilon(A) = \#\{ i : \sigma_i > \epsilon \}$

이는 임계값보다 큰 특이값의 개수와 같다. 임계값은 보통 가장 큰 특이값에 비례하는 형태( $\epsilon = \tau \sigma_1$ )로 선택되거나, 측정 잡음의 표준 편차를 기반으로 결정된다.

3. 랭크 $k$ 근사 문제

행렬 $A \in \mathbb{R}^{m \times n}$ 에 대한 랭크 $k$ 근사 문제는 다음과 같이 정식화된다.

$\min_{\mathrm{rank}(B) \leq k} \|A - B\|$

여기서 노름은 일반적으로 스펙트럼 노름 $\|\cdot\|_2$ 또는 프로베니우스 노름 $\|\cdot\|_F$ 가 사용된다. 이 최적화 문제는 행렬 $A$ 를 랭크 $k$ 이하의 행렬들 중에서 가장 가까운 것으로 근사하는 문제이며, 그 해는 특이값 분해를 통하여 명시적으로 주어진다.

4. 에크하르트-영 정리

랭크 $k$ 근사 문제의 해는 다음의 핵심 정리에 의하여 주어진다.

정리 (에크하르트-영-미르스키 정리, Eckart-Young-Mirsky theorem). 행렬 $A \in \mathbb{R}^{m \times n}$ 의 특이값 분해를 $A = U\Sigma V^\top = \sum_{i=1}^{r} \sigma_i \mathbf{u}_i \mathbf{v}_i^\top$ 이라 하고, $k < r$ 이라 하자. 그러면

$A_k = \sum_{i=1}^{k} \sigma_i \mathbf{u}_i \mathbf{v}_i^\top$

는 다음의 의미에서 $A$ 의 최적 랭크 $k$ 근사이다.

(1) 스펙트럼 노름에 대하여:

$\min_{\mathrm{rank}(B) \leq k} \|A - B\|_2 = \|A - A_k\|_2 = \sigma_{k+1}$

(2) 프로베니우스 노름에 대하여:

$\min_{\mathrm{rank}(B) \leq k} \|A - B\|_F = \|A - A_k\|_F = \sqrt{\sum_{i=k+1}^{r} \sigma_i^2}$

이 정리는 절단 SVD가 두 가지 가장 자연스러운 행렬 노름에 대하여 동시에 최적의 저랭크 근사를 제공한다는 강력한 결과를 진술한다.

5. 정리의 증명 개요

스펙트럼 노름에 대한 부분의 증명을 개요한다. $B$ 를 임의의 랭크 $k$ 행렬이라 하자. 그러면 $B$ 의 영 공간은 적어도 $n - k$ 차원이다. 한편 $V$ 의 처음 $k+1$ 개 열 $\mathbf{v}_1, \ldots, \mathbf{v}_{k+1}$ 이 생성하는 부분 공간은 $k+1$ 차원이다. 차원 정리에 의하여 두 부분 공간은 적어도 일차원의 교집합을 가지므로, 비영의 단위 벡터 $\mathbf{x}$ 가 존재하여 $B\mathbf{x} = \mathbf{0}$ 이고 $\mathbf{x} = \sum_{i=1}^{k+1} c_i \mathbf{v}_i$ 로 표현될 수 있다.

이제

$\|(A - B)\mathbf{x}\|^2 = \|A\mathbf{x}\|^2 = \left\| \sum_{i=1}^{k+1} c_i \sigma_i \mathbf{u}_i \right\|^2 = \sum_{i=1}^{k+1} c_i^2 \sigma_i^2 \geq \sigma_{k+1}^2 \sum_{i=1}^{k+1} c_i^2 = \sigma_{k+1}^2$

이다. 따라서 $\|A - B\|_2 \geq \sigma_{k+1}$ 이다. 한편 $A_k$ 는 정확히 $\|A - A_k\|_2 = \sigma_{k+1}$ 을 달성하므로 최적이다. $\blacksquare$

프로베니우스 노름에 대한 증명도 유사한 방식으로 진행되며, 약간의 추가적인 계산이 요구된다.

6. 근사 오차의 정량적 해석

에크하르트-영 정리는 근사 오차에 대한 정량적인 해석을 제공한다.

스펙트럼 노름 오차: $\sigma_{k+1}$ 은 절단된 첫 번째 특이값과 일치한다. 즉, 절단 직후의 가장 큰 특이값이 그대로 오차의 노름이 된다.
프로베니우스 노름 오차: 절단된 모든 특이값의 제곱합의 제곱근이다. 이는 절단된 정보의 총 에너지를 측정하는 척도이다.
상대 오차: 정규화된 형태로 $\|A - A_k\|_F^2 / \|A\|_F^2 = \sum_{i>k} \sigma_i^2 / \sum_i \sigma_i^2$ 로 표현되며, 이는 절단된 정보의 비율을 나타낸다.

7. 적절한 절단 차수의 결정

저랭크 근사를 사용할 때 가장 중요한 결정은 절단 차수 $k$ 의 선택이다. 일반적으로 사용되는 기준은 다음과 같다.

고정 비율 기준: 누적 에너지 비율 $\sum_{i \leq k} \sigma_i^2 / \sum_i \sigma_i^2$ 이 미리 정한 임계값(예: 0.95 또는 0.99)을 초과하는 가장 작은 $k$ 를 선택한다.
고정 임계값 기준: $\sigma_k > \tau$ 인 가장 큰 $k$ 를 선택한다. 임계값 $\tau$ 는 측정 잡음의 추정량에 기반한다.
간격 검출 기준: 인접한 두 특이값 사이의 비 $\sigma_k / \sigma_{k+1}$ 이 특히 큰 위치를 선택한다. 이는 본질적인 신호 부분과 잡음 부분 사이의 자연스러운 경계를 의미한다.
교차 검증 기준: 데이터의 일부를 검증 집합으로 분리하여 근사 오차를 최소화하는 $k$ 를 선택한다.

각 기준은 적용 영역의 특성과 잡음 모델에 따라 적절히 선택되어야 한다.

8. 저장 공간의 절감

원래 $m \times n$ 행렬을 저장하기 위해서는 $mn$ 개의 실수가 필요하다. 반면 랭크 $k$ 근사를 외적 합 형식 $A_k = U_k \Sigma_k V_k^\top$ 로 저장하면 $U_k \in \mathbb{R}^{m \times k}$ , $\Sigma_k \in \mathbb{R}^{k \times k}$ (대각이므로 $k$ 개), $V_k \in \mathbb{R}^{n \times k}$ 로 총 $k(m + n + 1)$ 개의 실수가 필요하다.

$k(m + n) \ll mn$ 인 경우, 즉 $k \ll \min(m, n)$ 인 경우 저장 공간의 절감은 극적이다. 예컨대 $m = n = 10\,000$ , $k = 100$ 인 경우 원래는 $10^8$ 개의 원소가 필요하지만, 근사 저장에는 약 $2 \times 10^6$ 개의 원소만 필요하므로 저장 공간이 약 $50$ 배 절감된다.

9. 곱셈 연산의 효율화

저랭크 표현은 행렬-벡터 곱셈에서도 큰 이점을 제공한다. 일반적인 행렬-벡터 곱셈 $A \mathbf{x}$ 는 $O(mn)$ 의 연산을 요구하지만, 랭크 $k$ 근사를 활용하면

$A_k \mathbf{x} = U_k (\Sigma_k (V_k^\top \mathbf{x}))$

의 순서로 계산하여 $O(k(m + n))$ 의 연산으로 줄일 수 있다. 이는 반복적 알고리듬과 실시간 처리에서 결정적인 효율성 향상을 가져온다.

10. 행렬 완성과 저랭크 가정

행렬 완성(matrix completion) 문제는 행렬의 일부 원소만이 관찰된 상황에서 나머지 원소를 추론하는 문제이다. 이 문제는 일반적으로 잘 정의되지 않지만, 원래 행렬이 저랭크라는 가정 하에서 풀이가 가능해진다. 저랭크 가정은 데이터가 실제로 적은 수의 잠재 요인에 의하여 생성되었다는 모델 가정과 일치하며, 추천 시스템, 영상 복원, 그리고 센서 보정 등에서 광범위하게 활용된다.

11. 잡음 제거로서의 저랭크 근사

저랭크 근사는 잡음 제거의 자연스러운 도구이다. 데이터의 본질적인 신호가 저랭크 구조를 가진다고 가정하면, 측정 잡음은 일반적으로 모든 특이값에 분포한 형태로 나타난다. 큰 특이값에 대응하는 성분은 신호이고 작은 특이값에 대응하는 성분은 주로 잡음이라 가정하면, 절단 SVD는 간단하면서도 효과적인 잡음 제거 기법이 된다.

12. 다른 행렬 노름에 대한 일반화

에크하르트-영 정리는 스펙트럼 노름과 프로베니우스 노름뿐만 아니라 모든 유니타리 불변 노름(unitarily invariant norm)으로 일반화된다. 슈텐 $p$ 노름(Schatten $p$ -norm)은 다음과 같이 정의된다.

$\|A\|_{S_p} = \left( \sum_{i} \sigma_i^p \right)^{1/p}$

특히 $p = \infty$ 일 때 스펙트럼 노름이 되고, $p = 2$ 일 때 프로베니우스 노름이 된다. 미르스키 정리에 의하여 절단 SVD는 모든 유니타리 불변 노름에 대하여 최적의 랭크 $k$ 근사를 제공한다.

13. 무작위화 기법과 대규모 SVD

매우 큰 행렬에 대한 정확한 SVD는 계산 비용이 크다. 이를 해결하기 위하여 무작위화 SVD(randomized SVD) 기법이 개발되었다. 이 기법은 다음의 단계로 작동한다.

무작위 행렬 $\Omega \in \mathbb{R}^{n \times \ell}$ 를 생성한다 (여기서 $\ell$ 은 $k$ 보다 약간 큰 값).
$Y = A\Omega \in \mathbb{R}^{m \times \ell}$ 를 계산한다.
$Y$ 의 열을 직교화하여 $Q \in \mathbb{R}^{m \times \ell}$ 를 얻는다.
$B = Q^\top A \in \mathbb{R}^{\ell \times n}$ 의 SVD를 계산한다.
이 작은 행렬의 SVD로부터 원래 행렬의 저랭크 근사를 복원한다.

이 접근법은 매우 큰 행렬에 대한 저랭크 근사를 효율적으로 계산할 수 있게 하며, 통계학습과 빅데이터 처리에서 표준적인 도구로 자리 잡고 있다.

14. 로봇공학에서의 응용

14.1 자코비안의 댐핑 의사 역행렬

매니퓰레이터의 자코비안이 특이 형상에 가까울 때, 작은 특이값들은 의사 역행렬의 계산을 매우 불안정하게 만든다. 저랭크 근사는 특이 형상 부근에서 가장 작은 특이값들을 무시하여 안정적인 의사 역행렬을 계산하는 자연스러운 방법을 제공한다. 또한 절단된 특이값에 대응하는 운동 방향은 그 시점에서 사용 가능하지 않은 것으로 간주된다.

14.2 동작 캡쳐 데이터의 압축과 복원

인간이나 로봇의 동작 캡쳐 데이터는 시간에 따른 자세 벡터의 행렬로 표현되며, 일반적으로 매우 저랭크 구조를 가진다. 이는 인간이나 로봇의 동작이 본질적으로 적은 수의 자유도를 가지는 잠재 매니폴드 위에 분포하기 때문이다. 절단 SVD를 통하여 동작 데이터를 효과적으로 압축하고, 손상된 데이터를 복원할 수 있다.

14.3 시각 SLAM에서의 한켈 행렬 처리

시각 SLAM과 다중 뷰 기하학에서 사용되는 측정 행렬은 종종 큰 직사각 형태를 가지며, 본질적으로 저랭크 구조를 가진다. 절단 SVD는 측정 잡음을 제거하면서 카메라 자세와 점 좌표를 복원하는 데 활용된다.

14.4 모델 차수 축약과 균형 절단

선형 동역학 시스템의 균형 절단 차수 축약은 한켈 특이값의 절단을 통하여 수행된다. 작은 한켈 특이값에 대응하는 모드는 입력으로부터 출력으로의 에너지 전달이 미약하므로 안전하게 제거할 수 있으며, 이는 실시간 제어와 임베디드 구현에서 필수적이다.

14.5 점 구름의 평면 적합과 곡률 추정

점 구름의 국소 영역에서 형성되는 데이터 행렬에 대한 저랭크 근사는 평면 적합과 곡률 추정의 기초이다. 가장 작은 특이값에 대응하는 우특이벡터는 평면의 법선 방향을 제공하며, 특이값들의 분포는 영역의 평면성, 선형성, 또는 등방성을 정량화하는 척도이다.

14.6 센서 행렬의 잡음 제거

다중 센서 융합에서 수집된 측정 행렬에는 다양한 잡음이 포함되어 있다. 신호의 본질적인 저랭크 구조를 가정하고 절단 SVD를 적용하면 측정 잡음을 효과적으로 제거할 수 있으며, 이는 추정의 정밀도를 향상시킨다.

참고문헌

Eckart, C., & Young, G. (1936). The approximation of one matrix by another of lower rank. Psychometrika, 1(3), 211-218.
Mirsky, L. (1960). Symmetric gauge functions and unitarily invariant norms. The Quarterly Journal of Mathematics, 11(1), 50-59.
Trefethen, L. N., & Bau, D. (2022). Numerical Linear Algebra (25th Anniversary ed.). SIAM.
Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations (4th ed.). Johns Hopkins University Press.
Halko, N., Martinsson, P. G., & Tropp, J. A. (2011). Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Review, 53(2), 217-288.
Candès, E. J., & Recht, B. (2009). Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6), 717-772.

Version: 1.0