Matrix Decomposition(2): QR Decomposition

고영민·2021년 12월 30일
Mathematics
0

SLAM: 기초 컴퓨터 비전부터 visual&LiDAR SLAM까지

목록 보기
7/17
post-thumbnail

1. QR Decomposition

QR decomposition은 행렬 A\mathbf{A}의 column 벡터들이 서로 선형독립일 경우 다음과 같이 A=QR\mathbf{A}=\mathbf{Q}\mathbf{R}의 형태로 분해하는 방법을 의미한다.

A=QR\mathbf{A} = \mathbf{Q}\mathbf{R}
A=(a11⋯a1n⋮⋱⋮an1⋯ann),        a1=(a11⋮an1),⋯ ,an=(a1n⋮ann)\mathbf{A} = \begin{pmatrix} a_{11} & \cdots & a_{1n}\\ \vdots & \ddots & \vdots\\ a_{n1} & \cdots & a_{nn} \end{pmatrix}, \;\;\;\; \mathbf{a_1}= \begin{pmatrix} a_{11}\\ \vdots\\ a_{n1} \end{pmatrix}, \cdots, \mathbf{a_n}= \begin{pmatrix} a_{1n}\\ \vdots\\ a_{nn} \end{pmatrix}
Q=(q11⋯q1n⋮⋱⋮qn1⋯qnn),        q1=(q11⋮qn1),⋯ ,qn=(q1n⋮qnn)\mathbf{Q} = \begin{pmatrix} q_{11} & \cdots & q_{1n}\\ \vdots & \ddots & \vdots\\ q_{n1} & \cdots & q_{nn} \end{pmatrix}, \;\;\;\; \mathbf{q_1}= \begin{pmatrix} q_{11}\\ \vdots\\ q_{n1} \end{pmatrix}, \cdots, \mathbf{q_n}= \begin{pmatrix} q_{1n}\\ \vdots\\ q_{nn} \end{pmatrix}
R=(r11r12⋯r1n0r22⋯r2n⋮⋱⋱⋮0⋯0rnn)\mathbf{R} = \begin{pmatrix} r_{11} & r_{12} & \cdots & r_{1n}\\ 0 & r_{22} & \cdots & r_{2n}\\ \vdots & \ddots & \ddots & \vdots\\ 0 & \cdots & 0 & r_{nn} \end{pmatrix}

이때, Q\mathbf{Q}의 column 벡터들은 A\mathbf{A}의 column 벡터들로부터 생성된 정규직교기저(서로 orthogonal하며, 크기가 1인 기저 벡터들)이며, R\mathbf{R}은 상삼각행렬이다. 즉, QR decomposition은 column 벡터들이 서로 선형독립인 행렬 A\mathbf{A}를 그에 해당하는 정규직교기저 및 성분으로 분해한다.

2. 그람-슈미트(Gram-Schmidt) 방법을 통한 QR Decomposition

A\mathbf{A}의 column 벡터에 대한 정규직교기저를 생성하는 방법으로 다음과 같은 그람-슈미트(Gram-Schmidt) 방법을 사용할 수 있다. 그람-슈미트방법은 n개의 선형독립인 n차원 column 벡터 a1,⋯ ,an\mathbf{a_1}, \cdots, \mathbf{a_n}으로부터 정규직교기저 q1,⋯ ,qn\mathbf{q_1}, \cdots, \mathbf{q_n}을 얻는 방법이다.

  • Step 1: q1=p1/∣p1∣,      p1=a1\mathbf{q_1} = \mathbf{p_1} / \mid \mathbf{p_1} \mid, \;\;\; \mathbf{p_1}=\mathbf{a_1}
  • Step 2: q2=p2/∣p2∣,      p2=a2−(a2⋅q1)q1\mathbf{q_2} = \mathbf{p_2} / \mid \mathbf{p_2} \mid, \;\;\; \mathbf{p_2}=\mathbf{a_2}-(\mathbf{a_2} \cdot \mathbf{q_1})\mathbf{q_1}
  • Step 3: q3=p3/∣p3∣,      p3=a3−(a3⋅q1)q1−(a3⋅q2)q2\mathbf{q_3} = \mathbf{p_3} / \mid \mathbf{p_3} \mid, \;\;\; \mathbf{p_3}=\mathbf{a_3}-(\mathbf{a_3} \cdot \mathbf{q_1})\mathbf{q_1}-(\mathbf{a_3} \cdot \mathbf{q_2})\mathbf{q_2}
  •                                                 ⋮\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \vdots
  • Step n: qn=pn/∣pn∣,      pn=an−∑i=0n−1(an⋅qi)qi\mathbf{q_n} = \mathbf{p_n} / \mid \mathbf{p_n} \mid, \;\;\; \mathbf{p_n}=\mathbf{a_n}-\sum_{i=0}^{n-1}{(\mathbf{a_n} \cdot \mathbf{q_i})\mathbf{q_i}}

Step 1에서는 a1\mathbf{a_1}을 사용하여 크기가 1인 하나의 벡터를 생성하며, step 2부터는 이전에 생성되었던 벡터들을 사용하여 이전의 벡터들과 직교하는 벡터를 생성한다. Step 2를 예시로 들면, (a2⋅q1)(\mathbf{a_2} \cdot \mathbf{q_1})는 a2\mathbf{a_2}를 q1\mathbf{q_1}에 투영한 성분이고, 즉, (a2⋅q1)q1(\mathbf{a_2} \cdot \mathbf{q_1})\mathbf{q_1}는 a2\mathbf{a_2}가 가지고 있는 q1\mathbf{q_1} 방향의 성분이다. 따라서 최종적으로 p2=a2−(a2⋅q1)q1\mathbf{p_2}=\mathbf{a_2}-(\mathbf{a_2} \cdot \mathbf{q_1})\mathbf{q_1}처럼 a2\mathbf{a_2}에서 q1\mathbf{q_1} 방향의 성분을 빼줌으로써 q1\mathbf{q_1}과 직교하는 벡터를 생성할 수 있으며, q1,q2\mathbf{q_1}, \mathbf{q_2}는 a1,a2\mathbf{a_1}, \mathbf{a_2}가 생성(span)하는 공간을 모두 생성할 수 있으므로 q1,q2\mathbf{q_1}, \mathbf{q_2}를 기저(basis)라고 할 수 있다. 따라서 이러한 과정을 n번 반복하면 n개의 정규직교기저가 생성된다.

QR decomposition에서 Q\mathbf{Q}는 A\mathbf{A}에 대한 정규직교기저, 상삼각행렬 R\mathbf{R}는 각 정규직교기저에 대한 성분이다. 위의 그람-슈미트 방법을 통해 Q\mathbf{Q}의 원소가 되는 정규직교기저를 찾았으며, 그 과정에서 R\mathbf{R} 또한 구할 수 있다.

  • rii=∣p1∣      (1≤i≤n)r_{ii}=\mid \mathbf{p_1} \mid \;\;\;(1 \le i \le n)
  • rij=aj⋅pi      (1≤i<j≤n)r_{ij}=\mathbf{a_j} \cdot \mathbf{p_i} \;\;\;(1 \le i \lt j \le n)

이라고 두면 그람-슈미트 방법을 다음과 같이 쓸 수 있다.

  • q1=1r11a1\mathbf{q_1} = \frac{1}{r_{11}} \mathbf{a_1}
  • q2=1r22(a2−r12q1)\mathbf{q_2} = \frac{1}{r_{22}} (\mathbf{a_2}-r_{12}\mathbf{q_1})
  •                               ⋮\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \vdots
  • qn=1rnn(an−∑i=0n−1rinqi)\mathbf{q_n} = \frac{1}{r_{nn}} (\mathbf{a_n}-\sum_{i=0}^{n-1}{r_{in}\mathbf{q_i}})

이를 ai\mathbf{a_i}에 대한 식으로 고치면 다음과 같이 나타나며, 행렬을 사용하여 A=QR\mathbf{A}=\mathbf{Q}\mathbf{R}의 형태로 쓸 수 있다.

  • a1=r11q1\mathbf{a_1} = r_{11} \mathbf{q_1}
  • a2=r12q1+r22q2\mathbf{a_2} = r_{12} \mathbf{q_1} + r_{22} \mathbf{q_2}
  •                               ⋮\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \vdots
  • qn=r1nq1+r2nq2+⋯+rnnqn\mathbf{q_n} = r_{1n} \mathbf{q_1} + r_{2n} \mathbf{q_2} + \cdots + r_{nn} \mathbf{q_n}
(a11a12⋯a1na21a22⋯a2n⋮⋮⋱⋮an1an2⋯ann)=(q11q12⋯q1nq21q22⋯q2n⋮⋮⋱⋮qn1qn2⋯qnn)(r11r12⋯r1n0r22⋯r2n⋮⋱⋱⋮0⋯0rnn)\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{pmatrix} = \begin{pmatrix} q_{11} & q_{12} & \cdots & q_{1n}\\ q_{21} & q_{22} & \cdots & q_{2n}\\ \vdots & \vdots & \ddots & \vdots \\ q_{n1} & q_{n2} & \cdots & q_{nn} \end{pmatrix} \begin{pmatrix} r_{11} & r_{12} & \cdots & r_{1n}\\ 0 & r_{22} & \cdots & r_{2n}\\ \vdots & \ddots & \ddots & \vdots\\ 0 & \cdots & 0 & r_{nn} \end{pmatrix}

이때 Q\mathbf{Q}의 column들은 모두 정규직교하므로 QQT=I\mathbf{Q}\mathbf{Q^T}=\mathbf{I}인 직교행렬이다.

3. 하우스홀더(Householder) 법

위에서 그람-슈미트 방법을 이용한 QR decomposition 과정을 살펴보았지만, 여기에는 한가지 문제점이 존재한다. 실제 취득된 데이터에는 여러가지 noise가 섞여 있으며, 컴퓨터를 활용한 계산 때때로 약간의 오차를 발생시킨다. 하지만 그람-슈미트 방법의 경우 이전 step에서 계산된 값이 이후에도 계속 사용되기 때문에(예를 들면, q1\mathbf{q_1}의 경우 이후 a2,⋯ ,an\mathbf{a_2}, \cdots, \mathbf{a_n}의 계산에도 계속 사용됨) 데이터에 섞인 오차가 지속적으로 누적된다. 따라서 실제 구현에서는 그람-슈미트 방법 보다는 반복법 기반의 다른 방법을 사용하여 QR decomposition을 수행하는데 그 중 한가지가 하우스홀더(Householder) 방법이다.

하우스홀더 방법은 대칭변환을 활용하는 방법으로 다음과 같이 원점을 지나는 평면을 기준으로 어떤 점의 반대편을 찾아낸다.


Figure1. 대칭변환

위 그림에서 u\mathbf{u}가 평면의 단위법선벡터라면, x\mathbf{x}의 u\mathbf{u}방향 성분은 uTx\mathbf{u^T}\mathbf{x}이다. 따라서 x\mathbf{x}를 평면의 반대편으로 옮기기 위하여 x−(uTx)u∗2\mathbf{x} - (\mathbf{u^T}\mathbf{x})\mathbf{u} * 2를 수행해야 한다. uTx\mathbf{u^T}\mathbf{x}는 스칼라 값이므로 (uTx)u=uuTx(\mathbf{u^T}\mathbf{x})\mathbf{u} = \mathbf{u}\mathbf{u^T}\mathbf{x}로 쓸 수 있으므로, 결국 대칭변환된 점 x′=x−2uuTx=(I−2uuT)x\mathbf{x'} = \mathbf{x} - 2\mathbf{u}\mathbf{u^T}\mathbf{x}=(\mathbf{I}-2\mathbf{u}\mathbf{u^T})\mathbf{x}이다. 따라서 이러한 대칭이동을 나타내는 선형변환 행렬은 H=I−2uuT\mathbf{H} = \mathbf{I}-2\mathbf{u}\mathbf{u^T}로 표현할 수 있다.

이때 I,uuT\mathbf{I}, \mathbf{u}\mathbf{u^T}가 둘 다 대칭행렬이므로 H=HT\mathbf{H}=\mathbf{H^T} 또한 대칭행렬이며, 해당 변환을 두번 적용하면 다시 제자리로 돌아오므로 H2=I→H−1=H\mathbf{H^2}=\mathbf{I} \rightarrow \mathbf{H^{-1}}=\mathbf{H}이다. 따라서 H=HT,H−1=H\mathbf{H}=\mathbf{H^T}, \mathbf{H^{-1}}=\mathbf{H}이므로 H\mathbf{H}는 직교행렬이다.

∣x∣=∣y∣\mid \mathbf{x} \mid = \mid \mathbf{y} \mid일 경우, x−y\mathbf{x}-\mathbf{y}를 법선벡터로 하는 평면을 기준으로 대칭이동을 할 수 있으며 (이등변 삼각형을 생각해보면 알 수 있다), 어떤 벡터 x\mathbf{x}를 y\mathbf{y}의 위치로 옮기는 변환 행렬 H\mathbf{H}를 찾을 수 있다.

H=I−2uuT,        u=x−y∣x−y∣\mathbf{H} = \mathbf{I}-2\mathbf{u}\mathbf{u^T}, \;\;\;\; \mathbf{u}=\frac{\mathbf{x}-\mathbf{y}}{\mid \mathbf{x}-\mathbf{y} \mid}

이제 위 변환을 이용하여 QR decomposition을 수행할 수 있다. 3×33 \times 3 행렬을 예로 들면, 어떤 벡터 x=(x,y,z,w)T\mathbf{x}=(x,y,z,w)^T를 y=(∣x∣,0,0,0)T\mathbf{y}=(\mid x \mid,0,0,0)^T로 변환하는 H\mathbf{H}를 생각해보자. 이 행렬 H\mathbf{H}는 다음과 같다(이때, y=(−∣x∣,0,0,0)T\mathbf{y}=(-\mid x \mid,0,0,0)^T를 사용해도 괜찮으며, 보통 계산시 발생하는 수치오차를 줄이기 위해 x\mathbf{x}의 첫번째 성분과 반대 부호를 취한다).

H=I−2uuT,        u=(x−x2+y2+z2+w2,y,z,w)T∣(x−x2+y2+z2+w2,y,z,w)T∣\mathbf{H} = \mathbf{I}-2\mathbf{u}\mathbf{u^T}, \;\;\;\; \mathbf{u}=\frac{(x-\sqrt{x^2+y^2+z^2+w^2}, y, z,w)^T}{\mid (x-\sqrt{x^2+y^2+z^2+w^2}, y, z,w)^T \mid}

이러한 H\mathbf{H}를 적용하면 다음과 같이 4×44 \times 4 행렬 A\mathbf{A}를 변환할 수 있다.

H1A=H1(x■■■y■■■z■■■w■■■)=(∣x∣■■■0■■■0■■■0■■■)\mathbf{H_1}\mathbf{A}= \mathbf{H_1} \begin{pmatrix} x & \blacksquare & \blacksquare & \blacksquare\\ y & \blacksquare & \blacksquare & \blacksquare\\ z & \blacksquare & \blacksquare & \blacksquare\\ w & \blacksquare & \blacksquare & \blacksquare \end{pmatrix}= \begin{pmatrix} \mid x \mid & \blacksquare & \blacksquare & \blacksquare\\ 0 & \blacksquare & \blacksquare & \blacksquare\\ 0 & \blacksquare & \blacksquare & \blacksquare\\ 0 & \blacksquare & \blacksquare & \blacksquare \end{pmatrix}

다음으로는 위 결과 행렬의 2번째 열을 (■,■,■,0)T(\blacksquare, \blacksquare, \blacksquare, 0)^T의 형태로 만들 것이다. 앞의 과정과 비슷하게 어떤 벡터 x=(x,y,z)T\mathbf{x}=(x,y,z)^T를 y=(∣x∣,0,0)T\mathbf{y}=(\mid x \mid,0,0)^T로 변환하는 H\mathbf{H}를 생각해보자. 이 행렬 H\mathbf{H}는 다음과 같다.

H=I−2uuT,        u=(x−x2+y2+z2,y,z)T∣(x−x2+y2+z2,y,z)T∣\mathbf{H} = \mathbf{I}-2\mathbf{u}\mathbf{u^T}, \;\;\;\; \mathbf{u}=\frac{(x-\sqrt{x^2+y^2+z^2}, y, z)^T}{\mid (x-\sqrt{x^2+y^2+z^2}, y, z)^T \mid}

이를 이용하여 행렬을 변환하면 다음과 같다.

H2A=(100000H0)(■■■■0x■■0y■■0z■■)이전step결과=(■■■■0∣x∣■■00■■00■■)\mathbf{H_2}\mathbf{A}= \left( \begin{array}{c|c} 1 & 0 & 0 & 0\\ \hline 0 & & & \\ 0 & & \mathbf{H} & \\ 0 & & & \\ \end{array} \right) \begin{pmatrix} \blacksquare & \blacksquare & \blacksquare & \blacksquare\\ 0 & x & \blacksquare & \blacksquare\\ 0 & y & \blacksquare & \blacksquare\\ 0 & z & \blacksquare & \blacksquare \end{pmatrix}_{이전step결과}= \begin{pmatrix} \blacksquare & \blacksquare & \blacksquare & \blacksquare\\ 0 & \mid x \mid & \blacksquare & \blacksquare\\ 0 & 0 & \blacksquare & \blacksquare\\ 0 & 0 & \blacksquare & \blacksquare \end{pmatrix}

마찬가지로 다음 열에 대해서도 반복하면 다음과 같다.

H3A=(100001000000H)(■■■■0■■■00x■00y■)이전step결과=(■■■■0■■■00∣x∣■000■)\mathbf{H_3}\mathbf{A}= \left( \begin{array}{cc|c} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ \hline 0 & 0 & & \\ 0 & 0 & & \mathbf{H}\\ \end{array} \right) \begin{pmatrix} \blacksquare & \blacksquare & \blacksquare & \blacksquare\\ 0 & \blacksquare & \blacksquare & \blacksquare\\ 0 & 0 & x & \blacksquare\\ 0 & 0 & y & \blacksquare \end{pmatrix}_{이전step결과}= \begin{pmatrix} \blacksquare & \blacksquare & \blacksquare & \blacksquare\\ 0 & \blacksquare & \blacksquare & \blacksquare\\ 0 & 0 & \mid x \mid & \blacksquare\\ 0 & 0 & 0 & \blacksquare \end{pmatrix}

이제 행렬은 우상삼각행렬로 변환되었으며, H3H2H1A=R\mathbf{H_3}\mathbf{H_2}\mathbf{H_1}\mathbf{A}=\mathbf{R}이며, A=(H3H2H1)−1R=QR\mathbf{A}=(\mathbf{H_3}\mathbf{H_2}\mathbf{H_1})^{-1}\mathbf{R}=\mathbf{Q}\mathbf{R}으로 QR decomposition이 수행되었다. 다만, (H3H2H1)−1=Q(\mathbf{H_3}\mathbf{H_2}\mathbf{H_1})^{-1}=\mathbf{Q}가 되기 위하여 (H3H2H1)−1(\mathbf{H_3}\mathbf{H_2}\mathbf{H_1})^{-1}가 정규 직교 기저 행렬인가 하는 의문이 남는다. 우선 위에서 H\mathbf{H}가 직교행렬임을 보였으며, 이에 따라 H1,H2,H3\mathbf{H_1}, \mathbf{H_2}, \mathbf{H_3} 또한 직교행렬이다. 그리고 각 H1,H2,H3\mathbf{H_1}, \mathbf{H_2}, \mathbf{H_3}의 정의를 보면 알 수 있듯이 각 행렬의 column의 길이는 1이며, 따라서 H1,H2,H3\mathbf{H_1}, \mathbf{H_2}, \mathbf{H_3}는 정규직교행렬이다. 앞선글에서 직교행렬 변환은 벡터의 길이를 보존함을 보였으며, 따라서 정규직교행렬 끼리의 곱도 정규직교행렬이 된다. 그리고 n×nn \times n 정규직교행렬의 rank는 nn이 되어 각 column들은 기저라고 볼 수 있다.

이러한 householder 방법 외에 기븐스 회전(Givens rotation) 등의 비슷한 느낌의 방법들도 존재한다. 또한 HA\mathbf{H}\mathbf{A}에 H−1\mathbf{H}^{-1}를 곱하여도 HAH−1\mathbf{H}\mathbf{A}\mathbf{H}^{-1} 또한 HA\mathbf{H}\mathbf{A}의 형태(하나의 열에서 ∣x∣\mid x \mid밑의 원소들은 0인 형태)가 유지되는 것을 알 수 있는데(H−1=H\mathbf{H}^{-1}=\mathbf{H}를 생각) 닮음 변환은 고윳값을 유지하므로 householder 방법을 통해 A\mathbf{A}를 고윳값을 구하기 쉬운 형태(삼각행렬이나 헤센버그(Hessenberg)행렬로의 변환을 통한 QR 반복법)로 변환할 수 있다.

4. QR Decomposition을 통한 최소제곱문제 계산

최소제곱 문제는 Ax=b\mathbf{A}\mathbf{x}=\mathbf{b}와 같은 시스템을 풀기위하여 ∣Ax−b∣\mid \mathbf{A}\mathbf{x}-\mathbf{b} \mid가 최소가 되는 x\mathbf{x}를 찾는 문제이다. A\mathbf{A}의 역행렬을 구하여 x=A−1b\mathbf{x}=\mathbf{A}^{-1}\mathbf{b}와 같이 해결하면 되지 않느냐는 의문이 생길 수 있지만, 실제 실험환경에서는 행렬 A\mathbf{A}를 구성하는 데이터에 여러가지 noise나 error가 포함되어 있어 역행렬이 존재하지 않는 경우가 빈번하게 발생한다. 따라서 최선의 해를 찾기 위해     ∣Ax−b∣\;\; \mid \mathbf{A}\mathbf{x}-\mathbf{b} \mid가 최소가 되는 x\mathbf{x}를 찾게되며, 이를 위해 QR docomposition이 활용될 수 있다.

우선 A\mathbf{A}의 column space를 VV라고 할때(A\mathbf{A}에 의한 변환 결과는 A\mathbf{A}의 column space 안에 있으므로), b\mathbf{b}는 b=b⊥V+b∥V\mathbf{b}=\mathbf{b}^{\perp V}+\mathbf{b}^{\parallel V}로 생각할 수 있다. 이때, b⊥V\mathbf{b}^{\perp V}는 b\mathbf{b}가 VV에 수직인 성분, b∥V\mathbf{b}^{\parallel V}는 b\mathbf{b}가 VV에 투영된 성분이다. ∣Ax−b∣\mid \mathbf{A}\mathbf{x}-\mathbf{b} \mid가 최소가 되는 경우는 Ax=b∥V\mathbf{A}\mathbf{x}=\mathbf{b}^{\parallel V}가 되는 경우이다.

  • 증명
    ∣Ax−b∣\mid \mathbf{A}\mathbf{x}-\mathbf{b} \mid가 최소가 되는 경우는 Ax\mathbf{A}\mathbf{x}가 b\mathbf{b}와 가장 가까워지는 지점을 찾는 것이며, 이 지점은 b∥V\mathbf{b}^{\parallel V}이고, 여기서 b\mathbf{b}까지의 거리는 b⊥V\mathbf{b}^{\perp V}이다. 공간 VV 내의 임의의 점 p\mathbf{p}를 생각하자. 이때 b−p=(b−b∥V)+(b∥V−p)=b⊥V+(b∥V−p)\mathbf{b}-\mathbf{p}=(\mathbf{b}-\mathbf{b}^{\parallel V})+(\mathbf{b}^{\parallel V}-\mathbf{p})=\mathbf{b}^{\perp V}+(\mathbf{b}^{\parallel V}-\mathbf{p})이며, b⊥V\mathbf{b}^{\perp V}는 b∥V\mathbf{b}^{\parallel V}에 수직이므로 피타고라스 정리를 적용하면, ∣b−p∣2=(b⊥V)2+(b∥V−p)2\mid \mathbf{b}-\mathbf{p} \mid^2 = (\mathbf{b}^{\perp V})^2 + (\mathbf{b}^{\parallel V}-\mathbf{p})^2이므로 공간 VV 내의 임의의 점 p\mathbf{p}에서 b\mathbf{b}까지의 거리는 b⊥V\mathbf{b}^{\perp V}보다 같거나 멀다.

그리고 A\mathbf{A}를 QR docomposition하여 A=QR\mathbf{A}=\mathbf{Q}\mathbf{R}라고 하면, Q\mathbf{Q}는 A\mathbf{A}의 정규기저벡터(Q\mathbf{Q}의 column 벡터들) q1,q2,⋯ ,qn\mathbf{q_1}, \mathbf{q_2}, \cdots, \mathbf{q_n}을 포함하고 있다. b∥V\mathbf{b}^{\parallel V}는 공간 VV 내에 있으므로 b∥V=α1q1+⋯+αnqn\mathbf{b}^{\parallel V} = \alpha_1 \mathbf{q_1} + \cdots + \alpha_n \mathbf{q_n}으로 둘 수 있다. 이때 qi⋅b=qi⋅(b⊥V+b∥V)=qi⋅b∥V=α1qi⋅q1+⋯+αnqi⋅qn=αi\mathbf{q_i} \cdot \mathbf{b} = \mathbf{q_i} \cdot (\mathbf{b}^{\perp V}+\mathbf{b}^{\parallel V})=\mathbf{q_i} \cdot \mathbf{b}^{\parallel V} = \alpha_1 \mathbf{q_i} \cdot \mathbf{q_1} + \cdots + \alpha_n \mathbf{q_i} \cdot \mathbf{q_n} = \alpha_i이다. 따라서 QTb\mathbf{Q}^T\mathbf{b}는 정규기저백터 q1,q2,⋯ ,qn\mathbf{q_1}, \mathbf{q_2}, \cdots, \mathbf{q_n}에 대한 b∥V\mathbf{b}^{\parallel V}의 계수들이며, QQTb=b∥V\mathbf{Q}\mathbf{Q}^T\mathbf{b}=\mathbf{b}^{\parallel V}가 된다. 이는 정규기저벡터로 이루어진 행렬 Q\mathbf{Q}의 column space에 투영된다고 볼 수도 있다(b∥V=b∥Col(Q)\mathbf{b}^{\parallel V}=\mathbf{b}^{ \parallel Col(\mathbf{Q})}).

이제 QR docomposition를 최소제곱문제에 적용해보자

Ax=b\mathbf{A}\mathbf{x}=\mathbf{b}

위의 식에 A=QR\mathbf{A}=\mathbf{Q}\mathbf{R}를 대입하면 다음과 같다.

QRx=b\mathbf{Q}\mathbf{R}\mathbf{x}=\mathbf{b}

Q\mathbf{Q}는 정규직교행렬이므로 양변에 QT=Q−1\mathbf{Q}^T=\mathbf{Q}^{-1}를 곱하면 다음과 같다.

QTQRx=QTb\mathbf{Q}^T\mathbf{Q}\mathbf{R}\mathbf{x}=\mathbf{Q}^T\mathbf{b}
Rx=QTb\mathbf{R}\mathbf{x}=\mathbf{Q}^T\mathbf{b}

이때 QTb\mathbf{Q}^T\mathbf{b}는 공간 VV의 정규기저백터 q1,q2,⋯ ,qn\mathbf{q_1}, \mathbf{q_2}, \cdots, \mathbf{q_n}에 대한 b∥V\mathbf{b}^{\parallel V}의 계수들이므로 위를 만족하는 x\mathbf{x}를 찾으면 최소제곱문제를 해결할 수 있음을 알 수 있다.

profile
고영민
이전 포스트

Matrix Decomposition(1) LU Decomposition

다음 포스트

Matrix Decomposition(3): SVD

0개의 댓글

관련 채용 정보