경제적 QR 분해 (경제적 형태)

경제적 QR 분해는 전통적인 QR 분해에서 필요 없는 부분을 제거하여 효율성을 높인 형태로, 특히 데이터가 크거나 계산 리소스가 제한된 상황에서 유용하게 사용된다. 이 방법은 행렬의 일부 열에 대해 QR 분해를 수행하거나, 전통적인 QR 분해에서 사용되지 않는 부분을 제거하여 메모리와 계산 시간 측면에서 절약할 수 있도록 설계되었다.

정의

경제적 QR 분해는 $m \times n$ 행렬 $\mathbf{A}$ 에 대해 $m \geq n$ 인 경우, $\mathbf{A} = \mathbf{Q}\mathbf{R}$ 형태로 분해되지만, 이때 $\mathbf{Q}$ 는 $m \times n$ 크기의 직교 행렬이고, $\mathbf{R}$ 은 $n \times n$ 크기의 상삼각 행렬이다. 여기서 $\mathbf{Q}$ 는 원래 $m \times m$ 크기의 정사각 행렬이 아니라, 열의 개수를 줄여 $m \times n$ 크기의 직교 행렬로 만들어지며, 이로 인해 계산의 효율성이 크게 향상된다.

경제적 QR 분해의 절차

행렬의 크기 줄이기: 주어진 행렬 $\mathbf{A}$ 가 $m \times n$ 크기일 때, 전통적인 QR 분해는 $\mathbf{Q}$ 를 $m \times m$ 크기의 직교 행렬로, $\mathbf{R}$ 을 $m \times n$ 크기의 상삼각 행렬로 분해한다. 그러나 경제적 QR 분해는 이 과정에서 $\mathbf{Q}$ 의 열 개수를 $n$ 개로 줄여, $m \times n$ 크기의 행렬로 만든다.
직교 행렬 $\mathbf{Q}$ 의 구성: 경제적 QR 분해에서 $\mathbf{Q}$ 는 원래의 $m \times m$ 행렬에서 열의 개수를 줄인 $m \times n$ 행렬이다. 이 과정에서 $\mathbf{Q}$ 의 열 벡터는 원래의 QR 분해에서 첫 $n$ 개의 열 벡터와 동일하게 유지된다.
상삼각 행렬 $\mathbf{R}$ 의 구성: $\mathbf{R}$ 은 전통적인 QR 분해에서와 같이 $n \times n$ 크기의 상삼각 행렬이다. 이 행렬은 그대로 유지되며, $\mathbf{A}$ 의 상위 $n$ 개 열에 대한 정보를 담고 있다.

수학적 표현

주어진 행렬 $\mathbf{A}$ 를 QR 분해하는 경우,

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

로 나타낼 수 있다. 여기서 전통적인 QR 분해에서 $\mathbf{Q}$ 는 $m \times m$ 크기의 직교 행렬이고, $\mathbf{R}$ 은 $m \times n$ 크기의 상삼각 행렬이다. 그러나 경제적 QR 분해에서는 $\mathbf{Q}$ 를 $m \times n$ 크기의 직교 행렬로 축소시켜,

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

형태로 표현된다. 여기서 $\mathbf{Q}_1$ 은 $m \times n$ 크기의 직교 행렬이고, $\mathbf{R}$ 은 $n \times n$ 크기의 상삼각 행렬이다.

장점과 활용

경제적 QR 분해는 다음과 같은 여러 장점을 가지고 있어 특정 상황에서 매우 유용하게 사용된다.

메모리 절약

전통적인 QR 분해에서 생성되는 직교 행렬 $\mathbf{Q}$ 는 $m \times m$ 크기이며, 이는 큰 행렬일수록 상당한 메모리를 필요로 한다. 그러나 경제적 QR 분해에서는 $\mathbf{Q}_1$ 이 $m \times n$ 크기이므로, 메모리 사용량을 크게 줄일 수 있다. 특히, $m$ 이 $n$ 보다 훨씬 클 때 그 효과는 더욱 두드러진다.

계산 비용 절감

경제적 QR 분해는 행렬의 크기를 줄임으로써 계산 비용을 절감할 수 있다. 전통적인 QR 분해에서는 $m \times m$ 행렬을 다루어야 하기 때문에 계산 복잡도가 높지만, 경제적 형태에서는 $m \times n$ 크기의 행렬로 계산하기 때문에 연산량이 줄어든다. 따라서, 대규모 데이터를 다룰 때 경제적 QR 분해는 더 빠른 계산을 가능하게 한다.

선형 회귀와 최소 제곱 문제에서의 응용

경제적 QR 분해는 선형 회귀 분석과 최소 제곱 문제에서 자주 사용된다. 특히, 독립 변수의 개수가 종속 변수의 개수보다 적을 때, 즉 $n \leq m$ 인 경우에 경제적 QR 분해는 유용하다. 이때 경제적 QR 분해를 통해 불필요한 계산을 줄이고, 보다 효율적인 해를 구할 수 있다.

예제: 경제적 QR 분해를 이용한 행렬 분해

예를 들어, $\mathbf{A}$ 가 다음과 같은 $4 \times 3$ 행렬이라고 가정하자.

$\mathbf{A} = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12 \end{pmatrix}$

전통적인 QR 분해에서는 $\mathbf{Q}$ 가 $4 \times 4$ 크기의 행렬로 생성되지만, 경제적 QR 분해에서는 $\mathbf{Q}_1$ 이 $4 \times 3$ 크기의 행렬로 생성된다.

그람-슈미트 정규화 방법을 사용한 계산:
- 첫 번째 열 벡터는 그대로 사용하고, 두 번째 열 벡터는 첫 번째 열 벡터에 대해 직교화한 후 정규화한다.
- 세 번째 열 벡터는 앞선 두 벡터에 대해 직교화한 후 정규화한다.
하우스홀더 변환 또는 기븐스 회전 사용:
- 하우스홀더 변환을 사용하여 행렬의 각 열을 단계적으로 삼각 행렬 $\mathbf{R}$ 로 변환한다.
- 기븐스 회전을 사용하여 비대각 요소를 제거하고 상삼각 행렬을 얻는다.

이 방법으로 구한 $\mathbf{Q}_1$ 과 $\mathbf{R}$ 은 다음과 같다:

$\mathbf{Q}_1 = \begin{pmatrix} -0.0776 & 0.8729 & 0.4805 \\ -0.3106 & 0.2185 & -0.9255 \\ -0.5436 & -0.4369 & 0.1303 \\ -0.7765 & -0.6544 & 0.3147 \end{pmatrix} ,\quad \mathbf{R} = \begin{pmatrix} -12.8841 & -14.6611 & -16.4380 \\ 0 & 1.0911 & 2.1822 \\ 0 & 0 & 0.5436 \end{pmatrix}$

이제, 행렬 $\mathbf{A}$ 는 경제적 QR 분해로 다음과 같이 표현된다.

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

이와 같은 경제적 QR 분해를 통해, $\mathbf{Q}$ 의 크기를 줄이고, $\mathbf{R}$ 행렬을 계산하는 과정에서 불필요한 연산을 제거하여 효율성을 높일 수 있다.

구현 및 예제 코드

여기서는 Python의 NumPy 라이브러리를 사용하여 경제적 QR 분해를 구현하는 간단한 예제를 소개한다. 다음과 같은 코드를 통해, 경제적 QR 분해를 손쉽게 수행할 수 있다.

import numpy as np

A = np.array([[1, 2, 3],
              [4, 5, 6],
              [7, 8, 9],
              [10, 11, 12]])

Q1, R = np.linalg.qr(A, mode='reduced')

print("Q1:\n", Q1)
print("R:\n", R)

이 코드는 numpy.linalg.qr 함수의 mode='reduced' 옵션을 사용하여 경제적 QR 분해를 수행한다. 이 옵션은 $\mathbf{Q}_1$ 행렬의 크기를 $m \times n$ 으로 줄여주고, 계산 효율성을 높이는 데 도움을 준다.

경제적 QR 분해의 한계

경제적 QR 분해는 메모리 사용량과 계산 복잡도를 줄이는 데 큰 장점이 있지만, 일부 경우에서는 전통적인 QR 분해에 비해 한계가 있을 수 있다. 예를 들어, 행렬의 모든 열이 필요한 경우나, 직교 행렬 $\mathbf{Q}$ 의 모든 열이 특정 분석에 필요할 경우에는 경제적 QR 분해가 적합하지 않을 수 있다.