30.26 멱승법(Power Method)을 이용한 최대 고유값의 수치적 근사

1. 멱승법의 기본 아이디어

**멱승법(power method, power iteration)**은 행렬의 지배 고유값(dominant eigenvalue), 즉 절댓값이 가장 큰 고유값과 그에 대응하는 고유벡터를 반복적으로 근사하는 알고리즘이다. 그 원리는 임의의 초기 벡터에 행렬을 반복적으로 곱하면, 지배 고유값에 대응하는 고유벡터 방향으로 수렴한다는 관찰에 기초한다.

$n \times n$ 행렬 $A$ 의 고유값이 $\lvert \lambda_1 \rvert > \lvert \lambda_2 \rvert \geq \cdots \geq \lvert \lambda_n \rvert$ 을 만족한다고 하자 (즉, $\lambda_1$ 이 유일한 지배 고유값). 대응하는 고유벡터를 $v_1, v_2, \ldots, v_n$ 이라 하고 이들이 $\mathbb{R}^n$ (또는 $\mathbb{C}^n$ )의 기저를 이룬다고 가정하면, 임의의 초기 벡터 $x_0$ 를

$x_0 = c_1 v_1 + c_2 v_2 + \cdots + c_n v_n$

으로 전개할 수 있다. $A$ 를 $k$ 번 곱하면

$A^k x_0 = c_1 \lambda_1^k v_1 + c_2 \lambda_2^k v_2 + \cdots + c_n \lambda_n^k v_n$

$\lambda_1^k$ 로 나누면

$\frac{A^k x_0}{\lambda_1^k} = c_1 v_1 + c_2 \left(\frac{\lambda_2}{\lambda_1}\right)^k v_2 + \cdots + c_n \left(\frac{\lambda_n}{\lambda_1}\right)^k v_n$

$\lvert \lambda_i / \lambda_1 \rvert < 1$ ( $i \geq 2$ )이므로, $k \to \infty$ 일 때 $(\lambda_i / \lambda_1)^k \to 0$ 이다. 따라서

$\frac{A^k x_0}{\lambda_1^k} \to c_1 v_1$

$c_1 \neq 0$ 이면, 반복 벡터의 방향이 $v_1$ 에 수렴한다.

2. 정규화를 포함한 알고리즘

실제 계산에서는 $A^k x_0$ 의 크기가 $\lvert \lambda_1 \rvert^k$ 에 비례하여 발산하거나 수렴하므로, 매 반복에서 정규화를 수행하여야 한다.

알고리즘 (정규화된 멱승법):

임의의 초기 벡터 $q_0$ ( $\lVert q_0 \rVert = 1$ )을 선택한다. $k = 0, 1, 2, \ldots$ 에 대하여:

$z_{k+1} = A q_k$

$q_{k+1} = \frac{z_{k+1}}{\lVert z_{k+1} \rVert}$

$\mu_{k+1} = q_{k+1}^T A q_{k+1}$

수렴 시 $q_k \to \pm v_1 / \lVert v_1 \rVert$ (지배 고유벡터의 단위 벡터)이고, $\mu_k \to \lambda_1$ (지배 고유값)이다.

고유값의 근사에는 레일리 몫(Rayleigh quotient) $\mu_k = q_k^T A q_k / (q_k^T q_k)$ 를 사용한다. $q_k$ 가 단위 벡터이면 $\mu_k = q_k^T A q_k$ 이다.

3. 수렴 조건

멱승법의 수렴을 위한 조건은 다음과 같다.

조건 1: 지배 고유값의 유일성. $\lvert \lambda_1 \rvert > \lvert \lambda_2 \rvert$ 이어야 한다. 즉, 절댓값이 최대인 고유값이 유일하여야 한다. $\lvert \lambda_1 \rvert = \lvert \lambda_2 \rvert$ 이면 수렴이 보장되지 않는다. 예를 들어, 실수 행렬이 $\lambda_1 = a$ , $\lambda_2 = -a$ 인 고유값을 가지면, 반복 벡터는 두 고유벡터 사이에서 진동할 수 있다.

조건 2: 초기 벡터의 비직교성. 초기 벡터 $x_0$ 의 $v_1$ 방향 성분 $c_1$ 이 0이 아니어야 한다. 즉, $x_0$ 이 지배 고유벡터와 직교하지 않아야 한다. 실제로는 초기 벡터를 무작위로 선택하면 $c_1 = 0$ 이 될 확률은 0이며, 유한 정밀도 산술에서의 반올림 오차가 $v_1$ 방향 성분을 자연스럽게 생성하므로 이 조건은 실용적으로 거의 항상 만족된다.

4. 수렴 속도

멱승법의 수렴 속도는 지배 고유값과 차지배 고유값(subdominant eigenvalue)의 비율에 의하여 결정된다.

정리. 멱승법의 수렴 속도는 선형(linear)이며, 수렴 비율(convergence ratio)은

$r = \frac{\lvert \lambda_2 \rvert}{\lvert \lambda_1 \rvert} < 1$

이다. $k$ 번째 반복 후 오차는

$\lVert q_k - v_1 \rVert = O(r^k)$

로 감소한다.

$r$ 이 1에 가까우면 ( $\lvert \lambda_1 \rvert \approx \lvert \lambda_2 \rvert$ ) 수렴이 매우 느리다. $r$ 이 0에 가까우면 ( $\lvert \lambda_1 \rvert \gg \lvert \lambda_2 \rvert$ ) 수렴이 빠르다.

레일리 몫을 통한 고유값 근사 $\mu_k$ 의 수렴 속도는 고유벡터보다 빠르다. 대칭 행렬의 경우 $\lvert \mu_k - \lambda_1 \rvert = O(r^{2k})$ 로서, 2차(quadratic) 수렴을 보인다.

5. 각 반복의 계산 비용

멱승법의 매 반복은 다음 연산으로 구성된다:

행렬-벡터 곱 $z_{k+1} = Aq_k$ : $O(n^2)$ (밀집 행렬), $O(\text{nnz})$ (희소 행렬, nnz는 비영 원소의 수)
벡터 정규화: $O(n)$
레일리 몫 계산: $O(n)$ (행렬-벡터 곱 결과를 재활용)

따라서 반복당 비용은 $O(n^2)$ 이며, 행렬의 분해나 역행렬 계산이 불필요하다. 이 저비용 구조가 대규모 희소 행렬에서 멱승법의 실용성을 뒷받침한다.

6. 수치 예시

$A = \begin{pmatrix} 2 & 1 \\ 1 & 3 \end{pmatrix}$

고유값: $\lambda_1 = \frac{5 + \sqrt{5}}{2} \approx 3.618$ , $\lambda_2 = \frac{5 - \sqrt{5}}{2} \approx 1.382$ 이다. 수렴 비율 $r = \lambda_2 / \lambda_1 \approx 0.382$ 이다.

초기 벡터 $q_0 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$ 로 시작한다.

반복 1: $z_1 = A q_0 = \begin{pmatrix} 2 \\ 1 \end{pmatrix}$ , $\lVert z_1 \rVert = \sqrt{5}$ , $q_1 = \frac{1}{\sqrt{5}}\begin{pmatrix} 2 \\ 1 \end{pmatrix}$ , $\mu_1 = q_1^T A q_1 = \frac{1}{5}(2, 1)\begin{pmatrix} 5 \\ 5 \end{pmatrix} = \frac{15}{5} = 3.0$

반복 2: $z_2 = A q_1 = \frac{1}{\sqrt{5}}\begin{pmatrix} 5 \\ 5 \end{pmatrix} = \frac{5}{\sqrt{5}}\begin{pmatrix} 1 \\ 1 \end{pmatrix}$ , $q_2 = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 1 \end{pmatrix}$ , $\mu_2 = q_2^T A q_2 = \frac{1}{2}(1, 1)\begin{pmatrix} 3 \\ 4 \end{pmatrix} = 3.5$

반복 3: $z_3 = A q_2 = \frac{1}{\sqrt{2}}\begin{pmatrix} 3 \\ 4 \end{pmatrix}$ , $q_3 = \frac{1}{5}\begin{pmatrix} 3 \\ 4 \end{pmatrix}$ , $\mu_3 = q_3^T A q_3 = \frac{1}{25}(3, 4)\begin{pmatrix} 10 \\ 15 \end{pmatrix} = \frac{90}{25} = 3.6$

반복이 진행됨에 따라 $\mu_k$ 는 $\lambda_1 \approx 3.618$ 에 수렴한다.

7. 멱승법의 실패 사례와 대응

7.1 지배 고유값이 유일하지 않은 경우

$\lvert \lambda_1 \rvert = \lvert \lambda_2 \rvert$ 이면 멱승법은 수렴하지 않는다.

부호 반대의 경우 ( $\lambda_1 = -\lambda_2$ ): $A^k x_0$ 이 매 반복마다 부호가 교대하여 진동한다. 이 경우 에이트킨 가속(Aitken acceleration) 또는 $A^2$ 에 대한 멱승법을 적용하여 해결할 수 있다. $A^2$ 의 지배 고유값은 $\lambda_1^2 = \lambda_2^2$ 이므로 여전히 문제가 있으나, $\lambda_1^2$ 이 유일한 최대 고유값인 경우가 많다.

복소 켤레 쌍의 경우 ( $\lambda_1 = \overline{\lambda_2}$ , $\lvert \lambda_1 \rvert = \lvert \lambda_2 \rvert$ ): 반복 벡터가 두 고유벡터가 이루는 2차원 부분 공간에서 회전하며 특정 방향으로 수렴하지 않는다.

7.2 초기 벡터가 지배 고유벡터에 직교한 경우

이론적으로 $c_1 = 0$ 이면 멱승법은 차지배 고유값에 수렴한다. 실용적으로는 유한 정밀도 산술의 반올림 오차가 $c_1$ 에 미소한 비영 성분을 도입하므로, 충분한 반복 후에 지배 고유벡터 방향으로 수렴한다. 다만 초기 수렴이 지연될 수 있다.

8. 멱승법의 변형

8.1 정규화 전략의 선택

상기 알고리즘에서는 유클리드 노름으로 정규화하였으나, 무한대 노름( $\lVert \cdot \rVert_\infty$ , 절댓값 최대 성분)으로 정규화하는 변형도 사용된다. 이 경우 레일리 몫 대신 정규화 계수 자체가 고유값의 근사가 된다:

$z_{k+1} = A q_k, \quad \mu_{k+1} = (z_{k+1})_{j^*} \quad (\text{절댓값 최대 성분}), \quad q_{k+1} = z_{k+1} / \mu_{k+1}$

8.2 디플레이션(Deflation)

지배 고유값 $\lambda_1$ 과 대응 고유벡터 $v_1$ 이 구해지면, 디플레이션(deflation) 기법을 적용하여 차지배 고유값을 구할 수 있다.

호텔링 디플레이션(Hotelling deflation). 대칭 행렬 $A$ 에 대하여

$A_2 = A - \lambda_1 q_1 q_1^T$

로 정의하면, $A_2$ 의 고유값은 $0, \lambda_2, \lambda_3, \ldots, \lambda_n$ 이다. $A_2$ 에 멱승법을 적용하면 $\lambda_2$ 를 근사할 수 있다. 이 과정을 반복하여 순차적으로 고유값을 구한다.

그러나 디플레이션은 $\lambda_1$ 과 $q_1$ 의 근사 오차가 후속 고유값의 계산에 전파되는 문제가 있다. 따라서 많은 수의 고유값을 구하여야 하는 경우에는 멱승법보다 QR 알고리즘 등의 전역적 방법이 선호된다.

9. 멱승법과 스펙트럼 반지름

행렬 $A$ 의 **스펙트럼 반지름(spectral radius)**은

$\rho(A) = \max_{1 \leq i \leq n} \lvert \lambda_i \rvert = \lvert \lambda_1 \rvert$

이다. 멱승법이 수렴하면 $\mu_k \to \lambda_1$ 이고 $\lvert \lambda_1 \rvert = \rho(A)$ 이므로, 멱승법은 스펙트럼 반지름의 계산에 직접 사용된다.

스펙트럼 반지름은 선형 동역학계 $x_{k+1} = Ax_k$ 의 안정성 판별에 핵심적이다: $\rho(A) < 1$ 이면 원점이 점근 안정(asymptotically stable)이고, $\rho(A) > 1$ 이면 불안정이다.

10. 희소 행렬과 대규모 문제에서의 멱승법

멱승법의 가장 큰 장점은 행렬을 “블랙 박스(black box)“로 취급할 수 있다는 것이다. 알고리즘이 요구하는 것은 주어진 벡터 $q$ 에 대한 행렬-벡터 곱 $Aq$ 뿐이며, 행렬의 원소에 대한 직접 접근이나 분해가 불필요하다. 이는 다음의 상황에서 특히 유리하다:

대규모 희소 행렬: $n$ 이 매우 크지만 비영 원소의 수가 $O(n)$ 수준인 경우, 반복당 비용이 $O(n)$ 이다.
암묵적 행렬(implicit matrix): 행렬이 명시적으로 저장되지 않고 행렬-벡터 곱만 계산 가능한 경우.
행렬이 수정 불가능한 경우: 행렬이 외부 시뮬레이터나 물리 시스템의 선형 응답으로 정의되는 경우.

11. 딥러닝에서의 멱승법 활용

스펙트럼 정규화(Spectral Normalization). 생성적 적대 신경망(GAN)의 판별자(discriminator) 학습에서, 가중치 행렬 $W$ 의 스펙트럼 노름 $\sigma_1(W) = \lVert W \rVert_2$ (최대 특이값)을 추정하기 위하여 멱승법이 사용된다. $W^T W$ 에 멱승법을 적용하면 $\sigma_1(W)^2$ 을 추정할 수 있으며, 이를 이용하여 $W \leftarrow W / \sigma_1(W)$ 로 정규화함으로써 판별자의 Lipschitz 상수를 제어한다. 이 기법은 Miyato et al. (2018)의 “Spectral Normalization for Generative Adversarial Networks“에서 제안되었다.

PageRank 알고리즘. Google의 PageRank는 본질적으로 확률 전이 행렬(stochastic transition matrix)에 대한 멱승법이다. 웹의 하이퍼링크 그래프에서 정의된 확률 행렬의 지배 고유벡터(정상 분포, stationary distribution)를 멱승법으로 근사한다. 이 행렬의 지배 고유값은 항상 1이며, 수렴 속도는 감쇠 인자(damping factor)에 의하여 제어된다.

주성분 분석에서의 최대 분산 방향. 공분산 행렬의 최대 고유값과 대응하는 고유벡터(제1주성분)를 멱승법으로 근사할 수 있다. 대규모 데이터에서 공분산 행렬을 명시적으로 구성하지 않고, 데이터 행렬과의 곱만으로 멱승법을 수행하는 것이 가능하다.