[개발자를 위한 실전 선형대수학] 8.1 직교 행렬, 8.2 그람-슈미트 과정

[chapter8] 직교 행렬과 QR 분해: 선형대수학의 핵심 분해법 1

1. 직교 행렬(orthogonal matrix)

직교 행렬은 아래 두 가지 속성을 가진다.

• 행렬의 모든 열은 직교한다.
• 각 열의 노름은 정확히 1이다.

이 속성을 아래 수식으로 나타낼 수 있다.

$$  \left< q_i, q_j\right> = \left\{\begin{matrix}
0, \textit{if}\;  i\neq j \\ 1, \textit{if}\;  i = j
\end{matrix}\right. $$

이 식은 모든 열은 자기자신과의 내적은 1이지만 다른 열과의 내적은 0이라는 뜻이다.

행렬의 왼쪽으로 그 행렬의 전치를 곱하면 열들 사이의 모든 내적을 구할 수 있다. 아래 수식이 성립한다.

$$ Q^TQ = I$$

즉, 직교 행렬의 역행렬은 그 행렬의 전치이다.

2. 그람-슈미트 과정

그람-슈미트 과정(GS, G-S)은 비직교 행렬을 직교 행렬로 변환하는 방법이다.

하지만 작은 숫자로 나눗셈과 곱셈을 많이 수행하면 수치적으로 불안정해지기 때문에 많이 사용되지는 않는다.

아래와 같은 알고리즘으로 구현된다.

• 행렬 V가 열 $v_1$부터 $v_n$까지로 구성되어 있을 때, 열 $q_k$를 갖는 직교 행렬 Q로 변환한다.
• V의 모든 열벡터는 첫 번째(가장 왼쪽)부터 시작해 마지막(가장 오른쪽)까지 차례로 이동한다.
• 알고리즘
  • (1) 직교벡터 분해를 사용해 $v_k$를 행렬 Q의 모든 이전 열과 직교화한다.
    • $q_{k-1}, q_{k-2}$에서 $q_1$까지의 모든 열과 수직인 $v_k$의 원소를 계산한다.
    • 이렇게 직교화된 벡터를 $v_k^*$라고 한다.
  • (2) $v_k^*$를 단위 길이로 정규화한다. 이것은 Q 행렬의 k번째 열인 $q_k$가 된다.

잘 이해가 안가서 다시 정리 😓

직교 행렬 Q를 만드는데, 먼저 V를 변형한다.

$v_1^*$는 $v_1$을 그대로 쓰고, $v_2^*$는 $ v_1^*$과 직교하게 만든다. 그리고  $v_3^*$는 $ v_2^*$, $ v_1^*$ 과 직교하게 만든다.

이제 이렇게 만들어진 $v_k^*$를 단위길이로 정규화하면 $q_k$가 된다.

3. QR 분해

GS는 행렬을 직교 행렬 Q로 변환한다. 이때 Q는 원래 행렬과 당연히 달라지므로, 원래 행렬에 대한 정보가 손실되었다고 할 수 있다.

이 손실된 정보는 Q에 곱하는 다른 행렬 R에 쉽게 복구해서 저장할 수 있다.

이 R을 생성하는 것은 QR분해의 정의에서 바로 알 수 있다.

$$ A = QR $$

$$ Q^TA = Q^TQR $$ 

$$ Q^TA = R $$

정방 행렬의 QR분해는파이썬에서 np.linalg.qr() 함수로 구현할 수 있다.

R 행렬은 항상 상삼각 행렬이다.

Q와 R의 크기 

Q와 R의 크기는 분해될 행렬 A의 크기와 QR 분해가 '경제형(축소)'인지 '완전형(전체)'인지에 따라 달라진다.

경제형인지 아니면 완성형인지는 높은 행렬의 QR 분해에서만 적용된다.

• 경제형(축소) : 높은 행렬(M>N)에서 열이 N개인 Q 행렬을 만든다. 높은 Q가 만들어진다.
• 완전형(전체) : 높은 행렬(M>N)에서 열이 M개인 Q 행렬을 만든다. 정방 Q가 만들어진다.

rank에 따른 Q, R의 형태 with ChatGPT

책을 보던 도중에 그림 8-2가 이해가 안되어서 GPT랑 같이 공부했다.

(확실하진 않지만) 책에 오류가 있는 것 같았다. 책에서는 높은 경제형일 때 원래 행렬 A가 MxN(M>N)형태이고 r=k일 때, 직교행렬 Q는 MxN, r=N이고, R은 MxN r=k라고 적혀있다. 그런데 Q와 R을 행렬곱하면 A가 되어야 하는데 MxN과 MxN 행렬은 곱할 수 없지 않나.. 싶었다.

아래는 GPT와 공부한 내용이다.

경제형 QR에서 Q는 독립적인 열벡터 수만큼 만든다.

Q는 A의 열 공간(column space)을 정규직교 기저로 바꾼 행렬로, rank가 k이면 Mxk 의 형태가 되는 것이다.

그리고 완전형 QR은 Q를 MxM의 전체 직교기저로 확장하고, R도 M×N으로 확장한 형태이다.

이 때 k개의 열은 선형 독립이며, 나머지 N−k개는 독립열들의 조합으로 표현되는 종속열이다.

정리하자면 아래와 같다.

형태	Q 크기	R 크기	만든 직교벡터	의미
경제형 QR	MxK	kxN	k	필요한 기저만
완전형 QR	MxM	MxN	M	전체 공간 기저까지 확장

파이썬에서는 np.linalg.qr()로 구할 수 있다.

두 번째 인수에 'complete'를 넣으면 전체 QR 분해가 되고, 'reduced'를 넣으면 경제형 QR 분해가 된다.(기본값)

다시 돌아가서..

직교화로 인한 Q와 A의 계수 차이는 A의 열공간이 $R^M$의 저차원 하위 공간일지라도 Q는 $R^M$ 전체를 생성한다는 것을 의미한다.

QR 분해는 모든 행렬의 크기와 계수에 대해 고유하지 않다. 즉, 같은 A에 대해 서로 다른 Q,R 조합이 얼마든지 나올 수 있다.

R이 상삼각 행렬인 이유

아래 세 가지 사실에서 도출된다.

• R은 $Q^TA = R$ 수식으로 부터 도출된다.
• 곱 행렬의 하삼각은 왼쪽 행렬의 아래쪽 행과 오른쪽 행렬의 위쪽 열 사이의 내적으로 이루어진다.
• $Q^T$의 행은 $Q$의 열이다.

종합하면 직교화는 왼쪽에서 오른쪽으로 열 단위로 처리되기 때문에 Q의 아래쪽 열은 A의 위쪽 열과 직교한다. 

따라서 R의 하삼각은 직교화된 벡터 쌍으로 이루어져 있다. 반대로 Q의 위쪽 열은 A의 아래쪽 열과 직교하지 않으므로 내적이 0이되지 않는다.

A의 열 i와 j가 이미 직교한 경우 R의 해당 (i,j)번째 원소는 0이 된다.

실제로 직교 행렬의 QR 분해를 계산하면 R은 대각선 원소가 A의 각 열의 노름인 대각 행렬이 된다.

즉, A = Q이면 R = I이다.

QR 분해와 역

QR 분해를 사용하면 역행렬을 수직적으로 더 안정적으로 계산할 수 있다.

$A = QR$ 수식을 $A^{-1} = R^{-1}Q^{-1}$로 반전시키면, A의 역행렬은 R의 역행렬에 Q의 역행렬, 즉 Q의 전치를 곱해서 구할 수 있다.

여기서 Q는 하우스홀더 변환 알고리즘 덕분에 수학적으로 안정적이고, R은 단순히 행렬 곱셈의 결과이기 때문에 역시 수치적으로 안정적이다.

QR 분해의 핵심은 그람-슈미트 과정의 알고리즘보다 수치적으로 더 안정적인 방법을 제공하는 것이다.