📂행렬대수

최소제곱법에서 LU, QR, SVD의 속도 비교

요약 ¹

행렬 $A \in \mathbb{R}^{m \times n}$ 에 대해, $m \ge n$ 이라고 하자. LU 분해와 QR 분해 그리고 특이값 분해로 최소제곱법을 수행할 때 시간복잡도는 모두 동일하게 $O \left( mn^{2} \right)$ 이지만, 실제로 필요한 flop 수는 대략 다음과 같다.

• LU 분해²: $$ mn^{2} + {\frac{ 2 }{ 3 }} n^{3} $$
• QR 분해³: $$ 2mn^{2} - {\frac{ 2 }{ 3 }} n^{3} $$
• 특이값 분해⁴: $$ 4mn^{2} - {\frac{ 4 }{ 3 }} n^{3} $$

단 이 요약에는 ‘의도적으로 틀린 부분’이 포함되어 있으니 맹신하지 말고, 반드시 본문의 내용을 읽어보길 권한다.

설명

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

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

실제로 flops의 비교에서 가장 중요하고 지배적인 항은 $m n^{2}$ 으로써 LU에서 QR, SVD로 갈수록 계산량은 거의 2배씩 늘어나는 것을 볼 수 있다. 다만 이러한 요약은 받아들이기 쉽게 정리한 것이지 구체적인 공식 자체는 flop이나 구현방식에 따라 달라질 수도 있다.

LU 분해

사실 LU 분해는 $2n^{3}/3$ 만큼의 flops만 필요하지만 최소제곱법을 위해서는 $A \mathbf{x} = \mathbf{b}$ 에서 $A^{\top} A \mathbf{x} = A^{\top} \mathbf{b}$ 로 바꾸어야 하므로, $A^{\top} A$ 을 계산할 때 $mn^{2}$ 만큼의 flops가 추가로 필요하다.

당연하지만 $m = n$ 인 경우에는 $A^{\top} A$ 을 계산할 필요가 없으므로 앞의 항이 사라져서 $2/3 n^{3}$ 이 되고 QR 분해에 비해 두 배 빠르다. 반대로 $m \gg n$ 인 경우에도 $n^{3}$ 의 비중은 줄어들어서 결국 QR 분해에 비해 두 배 정도 빨라진다. 정말 좋은 조건의 행렬을 가지고 속도를 우선시해야 한다면 LU 분해를 쓰는 게 나을 때도 있는 것이다.

QR 분해

LU 분해에 비해 두 배 느리고 SVD에 비해 두 배 빠르다. 어떻게 보면 어중간하다고 볼 수도 있겠지만, SVD가 너무 느려서 최소제곱법의 구현에 기본적으로 쓰이는 경우가 드물다는 걸 생각해보면 가장 무난하고 좋은 방법이라 볼 수 있다. 현실적으로 이 세상에서 대부분의 최소제곱문제가 QR 분해를 통해 해결되고 있을 것이다.

SVD

정리된 SVD의 flops는 고룹-카한 이분대각화^{Golub-Kahan bidiagonalization}을 사용할 때 $4mn^{2}$ 이 앞서 나오지만, 행렬 분해만 하는 게 아니라 특이값 분해에 초점을 맞추면 행렬분해와 별개의 계산이 늘어나거나 줄어들어서 다음과 같다. $$ 2 mn^{2} + 11 n^{3} $$ 이것이 앞서 언급한 ‘의도적으로 틀린 부분’이다. 어찌됐든 QR에 비해 느린 건 사실이고, 말 그대로 최소제곱법 한 번을 위해서라면 이 방법을 쓸 이유가 딱히 없기 때문에 더 간결한 비교를 한 것이다.

안정성과의 트레이드 오프

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

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