📂행렬대수

최소제곱법에서 LU, QR, SVD의 안정성 비교

요약

행렬 $A \in \mathbb{R}^{m \times n}$ 에 대해, $m \ge n$ 이라고 하자. LU 분해와 QR 분해 그리고 특이값 분해로 최소제곱법을 수행할 때 세 방법 모두 후방안정적이다. 다만, 후방안정성을 만족하는 조건이 다르다. 행렬이 풀랭크라는 것은 $A$ 의 랭크 $r$ 이 $\min (m, n)$ 과 같다는 의미다.

• LU 분해¹: $A$ 가 풀랭크일지라도 불안정적이다.
• QR 분해²: $A$ 가 풀랭크면 후방안정적이다.
• 특이값 분해³: $A$ 가 풀랭크가 아니라도 후방안정적이다.

설명

최소제곱법의 실질적인 구현으로써 행렬분해를 사용하는 방법은 여러가지가 있으나, 흔히 LU 분해(콜레스키 분해)를 통한 방법과 QR 분해를 통한 방법 그리고 SVD 분해를 통한 방법 세가지가 특히 널리 쓰인다. 참고로 LU 분해든 콜레스키 분해든 가우스 소거법이든 본질적으로 전진대입과 후진대입을 통해 선형시스템을 푸는 방법이므로 최소제곱법의 구현이라는 측면에서는 모두 같은 것이라고 보아도 무방하다. 실제로 콜레스키 분해의 flops는 $mn^{2} + {\frac{ 1 }{ 3 }} n^{3}$ 으로 LU 분해보다 조금 더 좋지만, 현실적으로는 안정성을 위해 피버팅^pivoting이 포함된 PLU 분해을 쓰게 된다.

줄리아⁴나 매트랩⁵의 구현을 보면 사실상 $A$ 에서 $m \ne n$ 일 때는 QR 분해, $m = n$ 일 때는 LU 분해를 쓴다고 보면 된다.

LU 분해

행렬의 조건수 $\kappa = \kappa(A)$ 를 생각해보면 알고리즘의 상대오차의 상한은 $\kappa$ 에 달려있는데, LU 분해든 콜레스키 분해든 표준방정식 $A^{\top} A \mathbf{x} = A^{\top} \mathbf{b}$ 을 세우는 시점에서 이미 $\kappa \left( A^{\top} A \right) = \kappa^{2}$ 가 되어 가뜩이나 안 좋을 수 있는 조건수가 더 악화된다.

$A = LU$ 에 대해 $\rho = {\frac{ \max \left| U_{ij} \right| }{ \max \left| A_{ij} \right| }}$ 를 $A$ 의 성장요인^{growth factor}라 하는데, 그나마 피버팅 LU에서 $\rho = O (1)$ 이고 $A$ 의 상대오차가 $\rho$ 와 머신입실론 $\epsilon$ 에 대해 $O \left( \rho \epsilon \right)$ 이라고 할 때 후방안정성을 가진다.

딱 봐도 느껴지겠지만 끝끝내 후방안정적이긴한데 구구절절하게 필요한 조건들이 많아서 사실상 불안정적이다. 이는 가우스 소거법의 기본 행 연산을 수행할 때 수를 곱하고 더하면서 생기는 오차가 점점 더 커질 가능성이 있기 때문이다.

QR 분해

QR 분해의 과정:

• Step 2-4. 다음을 계산한다. $$ \mathbf{q}_{j} = {{ \mathbf{v}_{j} } \over {r_{jj} }} $$

QR 분해도 구현하는 방식이 여러가지가 있기 때문에 꼭 이 이러한 이유로 안정성을 잃는다고 할 수는 없지만, 적어도 이와 같이 그램-슈미트 직교화를 사용하는 경우에는 벡터를 $r_{jj}$ 로 나누는 등의 과정에서 문제가 발생할 수 있다. 그야말로 $A$ 가 악조건인가 아닌가, 다시 말해 이러한 특이성^singularity이 문제 속에 도사리고 있는지에 달렸다고 할 수 있다.

그러나 LU에 비할바는 아니며, 가장 범용적으로 쓰이는만큼 안정성을 지나치게 걱정할 필요는 없다. 참고로 QR 분해에서도 어지간하면 피버팅이 기본적으로 들어간다.

SVD

랭크 결핍^{rank-deficiency}이 있는 상황에서도 안정적인 알고리즘은 SVD 뿐이다. 수식적으로 $A = U \Sigma V^{\top}$ 에서 $\Sigma$ 의 역행렬 $\Sigma^{-1}$ 을 구할 때는 $A$ 의 특이값 중 $0$ 에 가까운 부분들을 아예 제거한 축소 특이값 분해^{reduced SVD}를 시도할 수 있다. 이는 피버팅에 의존해야 하는 다른 분해법과 달리 충분히 작은 임계치를 명시적으로 설정하여 수치적인 문제를 원천적으로 봉쇄하는 것이나 마찬가지다. 기본적인 코스트가 높기 때문에 최소제곱법을 구현하기 위해서 잘 쓰이는 것은 아니지만, 그만큼 안정성에서는 절대로 밀리지 않는 것이다.

속도와의 트레이드 오프

세 방법의 속도를 비교해보고 안정성을 비교해보면 다음과 같이 아주 명확하게 트레이드 오프를 확인할 수 있다.

방법	속도	안정성
LU	빠름	불안정
QR	보통	안정적
SVD	느림	매우 안정적