6.54 QR 분해의 최소 제곱 응용

1. 도입

선형 최소 제곱 문제는 과결정 연립 방정식의 가장 좋은 근사 해를 구하는 핵심적인 수치 계산 문제이다. 정규 방정식을 직접 푸는 방식은 조건수의 제곱화 문제로 인해 수치적 안정성이 저하되는 한계가 있는 반면, QR 분해를 이용한 접근은 이러한 문제를 회피하고 더욱 높은 정확도를 제공한다. 로봇공학에서는 자코비안 기반의 운동 계획, 매개변수 식별, 점 구름 정합, 경로 추정 등 다양한 영역에서 최소 제곱 문제가 등장하며, QR 분해는 이러한 문제의 표준적인 해법으로 자리잡고 있다.

2. 선형 최소 제곱 문제

행렬 A \in \mathbb{R}^{m \times n} (m \ge n)와 벡터 \mathbf{b} \in \mathbb{R}^m 에 대하여, 선형 최소 제곱 문제는 다음을 만족하는 \mathbf{x} \in \mathbb{R}^n 을 찾는 문제이다.

\min_{\mathbf{x} \in \mathbb{R}^n} \Vert A\mathbf{x} - \mathbf{b} \Vert_2^2

이 문제의 해는 잔차 벡터 \mathbf{r} = \mathbf{b} - A\mathbf{x} 가 A 의 열 공간 \mathcal{R}(A) 에 직교할 때 얻어지며, 이는 정규 방정식 A^{\top} A \mathbf{x} = A^{\top} \mathbf{b} 와 동치이다. A 가 완전 열 랭크일 때 해는 유일하게 존재한다.

3. 정규 방정식 접근의 한계

정규 방정식 A^{\top} A \mathbf{x} = A^{\top} \mathbf{b} 를 직접 푸는 방식은 두 가지 단점이 있다. 첫째, A^{\top} A 의 조건수는 \kappa(A^{\top} A) = \kappa(A)^2 의 관계를 가지므로, 원래 문제가 약하게 불량 조건일 경우 정규 방정식은 매우 불량 조건이 된다. 둘째, A^{\top} A 의 명시적 계산 과정에서 정보 손실이 발생할 수 있다. 이러한 한계를 극복하기 위해 QR 분해 기반의 접근이 사용된다.

4. QR 분해를 이용한 최소 제곱 해

행렬 A \in \mathbb{R}^{m \times n} 의 축소 QR 분해 A = QR 을 고려한다. 여기서 Q \in \mathbb{R}^{m \times n} 의 열은 정규 직교이며, R \in \mathbb{R}^{n \times n} 은 상삼각 행렬이다. Q 의 직교성에 의해 잔차의 노름은 다음과 같이 변형된다.

\Vert A\mathbf{x} - \mathbf{b} \Vert_2^2 = \Vert QR\mathbf{x} - \mathbf{b} \Vert_2^2

전체 QR 분해 A = \tilde{Q} \tilde{R} (\tilde{Q} \in \mathbb{R}^{m \times m}, \tilde{R} \in \mathbb{R}^{m \times n})을 사용하여 직교 변환을 적용하면 다음과 같이 정리된다.

\Vert \tilde{Q}^{\top}(A\mathbf{x} - \mathbf{b}) \Vert_2^2 = \left\Vert \begin{pmatrix} R \\ 0 \end{pmatrix} \mathbf{x} - \begin{pmatrix} \mathbf{c}_1 \\ \mathbf{c}_2 \end{pmatrix} \right\Vert_2^2 = \Vert R\mathbf{x} - \mathbf{c}_1 \Vert_2^2 + \Vert \mathbf{c}_2 \Vert_2^2

여기서 \mathbf{c}_1 \in \mathbb{R}^n 과 \mathbf{c}_2 \in \mathbb{R}^{m-n} 은 \tilde{Q}^{\top} \mathbf{b} 의 분할이다. 두 번째 항 \Vert \mathbf{c}_2 \Vert_2^2 은 \mathbf{x} 와 무관하므로, 잔차 노름의 최솟값은 첫 번째 항이 0 이 될 때 달성된다. 따라서 최소 제곱 해는 다음 상삼각 시스템의 해이다.

R \mathbf{x} = \mathbf{c}_1

또한 잔차의 노름은 정확히 \Vert \mathbf{c}_2 \Vert_2 와 같다.

5. 알고리즘 절차

QR 분해 기반 최소 제곱 해법은 다음 절차로 수행된다.

1. A 의 QR 분해 A = QR 을 계산한다(하우스홀더 변환 또는 기븐스 회전 사용).
2. \mathbf{c}_1 = Q^{\top} \mathbf{b} 를 계산한다.
3. 상삼각 시스템 R\mathbf{x} = \mathbf{c}_1 을 후방 대입으로 해결한다.
4. 잔차 노름 \Vert \mathbf{c}_2 \Vert_2 가 필요한 경우 함께 산출한다.

전체 연산량은 하우스홀더 QR 분해의 경우 약 2mn^2 - \frac{2}{3} n^3 부동소수점 연산에 해당한다.

6. 수치적 안정성

QR 분해 기반 최소 제곱 해법은 정규 방정식 접근보다 수치적으로 우월하다. 윌킨슨의 후방 오차 분석에 의하면, 하우스홀더 QR 분해를 사용한 최소 제곱 해법은 A 와 \mathbf{b} 의 미세한 섭동에 대한 정확한 해와 일치한다. 구체적으로 계산된 해 \hat{\mathbf{x}} 는 다음을 만족하는 섭동 \delta A 와 \delta \mathbf{b} 가 존재한다.

(A + \delta A) \hat{\mathbf{x}} = \mathbf{b} + \delta \mathbf{b}, \quad \frac{\Vert \delta A \Vert_2}{\Vert A \Vert_2} \le c_{m,n} \epsilon_{\text{mach}}

여기서 c_{m,n} 은 행렬 차원에 대한 작은 다항식이며, \epsilon_{\text{mach}} 는 기계 정밀도이다. 상대 오차의 한계는 \kappa(A) 에 비례하며, 정규 방정식 접근의 \kappa(A)^2 의존성과 비교하여 매우 우월하다.

7. 랭크 결손 문제와 피벗팅 QR

A 가 랭크 결손이거나 수치적으로 거의 결손인 경우, R 의 일부 대각 원소가 매우 작아져 후방 대입이 불안정해진다. 이러한 상황을 처리하기 위해 열 피벗팅이 적용된 QR 분해가 사용된다. 이 분해는 다음 형태이다.

A \Pi = QR

여기서 \Pi 는 열 순열 행렬이며, R 의 대각 원소는 절댓값이 비증가 순서로 배열된다. 즉 \vert r_{11} \vert \ge \vert r_{22} \vert \ge \cdots \ge \vert r_{nn} \vert 이 성립한다. 이러한 정렬은 작은 대각 원소를 식별하여 수치적 랭크를 결정하는 것을 가능하게 한다.

8. 정규화된 최소 제곱 문제

랭크 결손 문제를 다루는 또 다른 방법은 티호노프 정규화를 사용하는 것이다. 이 방식은 다음의 수정된 최소 제곱 문제를 해결한다.

\min_{\mathbf{x}} \left( \Vert A\mathbf{x} - \mathbf{b} \Vert_2^2 + \lambda^2 \Vert \mathbf{x} \Vert_2^2 \right)

이 문제는 다음의 확장된 최소 제곱 문제와 동치이다.

\min_{\mathbf{x}} \left\Vert \begin{pmatrix} A \\ \lambda I \end{pmatrix} \mathbf{x} - \begin{pmatrix} \mathbf{b} \\ \mathbf{0} \end{pmatrix} \right\Vert_2^2

확장된 행렬 \begin{pmatrix} A^{\top} & \lambda I \end{pmatrix}^{\top} 은 \lambda > 0 일 때 항상 완전 열 랭크이므로, QR 분해 기반 해법이 안정적으로 적용된다.

9. 갱신과 하향 갱신

QR 분해는 행 또는 열의 추가 및 제거에 대한 효율적인 갱신 알고리즘을 갖는다. 새로운 관측 \mathbf{a}_{m+1}^{\top} 과 b_{m+1} 이 추가될 때, 기븐스 회전을 사용하여 기존 QR 분해를 O(n^2) 의 연산으로 갱신할 수 있다. 이는 매번 처음부터 분해를 다시 수행하는 O(mn^2) 의 비용보다 훨씬 효율적이다. 이러한 점진적 갱신 능력은 실시간 데이터 처리가 요구되는 적응 제어와 온라인 매개변수 식별에서 핵심적이다.

10. 가중 최소 제곱과 일반 최소 제곱

각 잔차에 가중치가 부여된 가중 최소 제곱 문제는 다음과 같이 정의된다.

\min_{\mathbf{x}} \Vert W^{1/2}(A\mathbf{x} - \mathbf{b}) \Vert_2^2

여기서 W 는 양정치 가중 행렬이다. 이 문제는 변수 변환 A' = W^{1/2} A, \mathbf{b}' = W^{1/2} \mathbf{b} 를 통해 표준 최소 제곱 문제로 환원되며, A' 의 QR 분해를 통해 해결된다. 가중치는 측정 잡음의 분산에 반비례하여 설정되며, 이는 통계적으로 최우 추정치에 해당한다.

11. 로봇공학에서의 응용

11.1 동역학 매개변수 식별

로봇 동역학 모델 \tau = Y(q, \dot{q}, \ddot{q}) \boldsymbol{\theta} 의 매개변수 \boldsymbol{\theta} 를 식별하기 위해 다양한 자세에서 측정한 토크 데이터로부터 회귀자 행렬 Y 를 구성한다. 측정 데이터 수가 매개변수 수보다 훨씬 많은 과결정 시스템이 형성되며, QR 분해 기반 최소 제곱 해법을 통해 안정적인 매개변수 추정이 가능하다. 정규 방정식 접근에 비해 수치 정확도가 높아 식별 정밀도가 향상된다.

11.2 자코비안 기반 역기구학

여유 자유도 매니퓰레이터의 자코비안 J \in \mathbb{R}^{m \times n} (n > m)에 대한 미분 역기구학에서는 다음의 최소 노름 해를 구해야 한다.

\min_{\Delta q} \Vert \Delta q \Vert_2^2 \quad \text{subject to} \quad J \Delta q = \dot{\mathbf{x}}

이 문제는 J^{\top} 의 QR 분해를 통해 효율적이고 안정적으로 해결된다. 특이점 근방에서는 정규화된 형태가 사용되며, 이 경우에도 QR 분해 기반 접근이 표준이다.

11.3 점 구름 정합과 ICP 알고리즘

반복 최근점(ICP) 알고리즘의 각 반복에서 두 점 구름 사이의 강체 변환을 구해야 한다. 점 대 평면 ICP의 경우 다음과 같은 선형 최소 제곱 문제로 환원된다.

\min_{\boldsymbol{\xi}} \sum_{i} \left( \mathbf{n}_i^{\top}(\mathbf{R}\mathbf{p}_i + \mathbf{t} - \mathbf{q}_i) \right)^2

작은 회전 가정 하에서 이 문제는 6 개 매개변수에 대한 선형 최소 제곱 문제로 선형화되며, QR 분해를 통해 효율적으로 해결된다. 이는 라이다 SLAM과 모바일 로봇 위치 추정의 핵심 알고리즘이다.

11.4 카메라 보정과 호모그래피 추정

카메라 보정 과정에서 직접 선형 변환(DLT) 방법은 호모그래피 행렬을 얻기 위해 과결정 선형 시스템을 풀어야 한다. 마찬가지로 카메라 내부 매개변수 행렬 K 를 구하기 위한 자흐 보정에서도 다수의 평면 자세로부터 얻은 제약 조건들이 과결정 시스템을 형성한다. 이러한 문제들은 QR 분해 기반 최소 제곱 해법을 통해 안정적으로 해결된다.

11.5 경로 평활화와 스플라인 피팅

로봇 궤적 계획에서 잡음이 포함된 경유점들을 매끄러운 곡선으로 근사할 때 B-스플라인 또는 다항식 기저 함수를 사용한 최소 제곱 피팅이 적용된다. 기저 함수 행렬은 일반적으로 잘 조건화된 띠 구조를 가지며, QR 분해를 통해 효율적으로 해결된다. 이는 부드러운 가속도 프로파일과 가가속도 제한을 만족하는 궤적 생성에 활용된다.

11.6 적응 제어의 점진적 식별

적응 제어 알고리즘에서 매개변수 추정치는 새로운 측정이 들어올 때마다 갱신되어야 한다. 점진적 QR 분해 갱신 알고리즘은 매 시간 단계에서 O(n^2) 의 연산만으로 새로운 추정치를 산출할 수 있어, 실시간 적응 제어에 적합하다. 이 방식은 재귀 최소 제곱(RLS) 알고리즘의 수치적으로 안정한 구현으로 활용된다.

11.7 시각 관성 주행거리계의 상태 추정

시각 관성 주행거리계(VIO)에서는 카메라 측정과 관성 측정이 결합되어 거대한 비선형 최소 제곱 문제가 형성된다. 이 문제는 가우스-뉴턴 또는 레벤버그-마쿼트 알고리즘을 통해 반복적으로 선형화되며, 각 반복에서 발생하는 선형 최소 제곱 문제는 희소 QR 분해를 통해 효율적으로 해결된다. 이는 무인 항공기와 자율 주행 로봇의 위치 추정 정확도를 좌우하는 핵심 계산이다.

참고문헌

• Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations (4th ed.). Johns Hopkins University Press.
• Trefethen, L. N., & Bau, D. (1997). Numerical Linear Algebra. SIAM.
• Björck, Å. (1996). Numerical Methods for Least Squares Problems. SIAM.
• Lawson, C. L., & Hanson, R. J. (1995). Solving Least Squares Problems. SIAM.
• Hartley, R., & Zisserman, A. (2004). Multiple View Geometry in Computer Vision (2nd ed.). Cambridge University Press.
• Siciliano, B., Sciavicco, L., Villani, L., & Oriolo, G. (2009). Robotics: Modelling, Planning and Control. Springer.

Version: 1.0