7.129 가우스-뉴턴법의 유도와 구현

1. 유도

비선형 최소 제곱 문제 $\min_{\mathbf{x}} \frac{1}{2}\lVert \mathbf{r}(\mathbf{x}) \rVert^2$ 에서 잔차 벡터를 현재 점 $\mathbf{x}_k$ 주위에서 1차 테일러 전개한다.

$\mathbf{r}(\mathbf{x}_k + \mathbf{d}) \approx \mathbf{r}(\mathbf{x}_k) + \mathbf{J}(\mathbf{x}_k)\mathbf{d}$

이 선형화된 잔차를 목적 함수에 대입하면 $\mathbf{d}$ 에 대한 선형 최소 제곱 하위 문제를 얻는다.

$\min_{\mathbf{d}} \quad \frac{1}{2}\lVert \mathbf{r}(\mathbf{x}_k) + \mathbf{J}(\mathbf{x}_k)\mathbf{d} \rVert^2$

이 하위 문제의 최적 조건은 정규 방정식(normal equation)이다.

$\mathbf{J}_k^T\mathbf{J}_k \mathbf{d}_k = -\mathbf{J}_k^T\mathbf{r}_k$

여기서 $\mathbf{J}_k = \mathbf{J}(\mathbf{x}_k)$ , $\mathbf{r}_k = \mathbf{r}(\mathbf{x}_k)$ 이다. 가우스-뉴턴 방향 $\mathbf{d}_k$ 는 이 선형 시스템의 해이다.

2. 알고리즘

초기점 $\mathbf{x}_0$ 를 설정한다.
$k = 0, 1, 2, \ldots$ 에 대해:
$\quad$ 잔차 $\mathbf{r}_k = \mathbf{r}(\mathbf{x}_k)$ 와 야코비안 $\mathbf{J}_k$ 를 계산한다.
$\quad$ 정규 방정식 $\mathbf{J}_k^T\mathbf{J}_k\mathbf{d}_k = -\mathbf{J}_k^T\mathbf{r}_k$ 를 풀어 가우스-뉴턴 방향을 구한다.
$\quad$ 직선 탐색: $\alpha_k$ 를 결정한다 (순수 가우스-뉴턴에서는 $\alpha_k = 1$ ).
$\quad$ $\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_k$
$\quad$ 수렴 판정

3. 정규 방정식의 해법

3.1 촐레스키 분해

$\mathbf{J}_k^T\mathbf{J}_k$ 가 양정치이면 촐레스키 분해 $\mathbf{J}_k^T\mathbf{J}_k = \mathbf{L}\mathbf{L}^T$ 를 수행하고 전방/후방 대입으로 $\mathbf{d}_k$ 를 구한다. 비용은 $O(n^3/3)$ 이다.

3.2 QR 분해

야코비안의 QR 분해 $\mathbf{J}_k = \mathbf{Q}\mathbf{R}$ 을 이용하면 정규 방정식을 형성하지 않고 직접 해를 구할 수 있다.

$\mathbf{R}\mathbf{d}_k = -\mathbf{Q}^T\mathbf{r}_k$

QR 분해는 $\mathbf{J}_k^T\mathbf{J}_k$ 의 조건수가 $\mathbf{J}_k$ 조건수의 제곱이 되는 정규 방정식의 수치적 불안정을 피할 수 있으므로, 수치적으로 더 안정적이다.

3.3 희소 구조의 활용

SLAM이나 번들 조정에서 야코비안이 희소한 경우, 희소 촐레스키 분해(CHOLMOD 등)나 슈어 보수를 이용한 축소 시스템 해법이 사용된다. 번들 조정에서의 야코비안은 카메라 파라미터와 3차원 점에 대한 블록 구조를 가지며, 3차원 점 변수를 슈어 보수로 소거하면 카메라 변수만의 축소 시스템(reduced camera system)을 얻어 효율적으로 풀 수 있다.

4. 수렴 성질

가우스-뉴턴법의 수렴은 잔차의 크기에 의존한다.

영잔차 문제( $\mathbf{r}(\mathbf{x}^*) = \mathbf{0}$ ): 정확한 적합이 가능한 경우, 가우스-뉴턴법은 최적해 근방에서 이차 수렴을 달성한다. 이는 가우스-뉴턴 근사 헤시안이 정확한 헤시안에 수렴하기 때문이다.

소잔차 문제( $\lVert \mathbf{r}(\mathbf{x}^*) \rVert$ 작음): 초선형 또는 빠른 선형 수렴이 기대된다. 무시된 2차 항 $\sum r_i \nabla^2 r_i$ 의 크기가 작으므로 근사가 정확하다.

대잔차 문제( $\lVert \mathbf{r}(\mathbf{x}^*) \rVert$ 큼): 수렴이 느리거나 실패할 수 있다. 2차 항의 영향이 크므로 가우스-뉴턴 근사가 부정확하다. 이 경우 레벤버그-마쿼트 알고리즘이나 완전 뉴턴법으로 대체해야 한다.

5. 가우스-뉴턴법의 한계와 개선

$\mathbf{J}_k^T\mathbf{J}_k$ 의 특이성: 야코비안의 계수가 부족하면(rank-deficient) 정규 방정식의 해가 유일하지 않다. 이는 모델의 과매개변수화(overparameterization)나 관측의 부족에 기인한다.

수렴 영역의 제한: 순수 가우스-뉴턴( $\alpha_k = 1$ )은 초기점이 최적해에서 멀면 발산할 수 있다. 직선 탐색이나 신뢰 영역과의 결합이 필요하다.

이러한 한계를 모두 해결하는 것이 레벤버그-마쿼트 알고리즘이다.

6. 로봇 공학에서의 구현 사례

g2o: 그래프 기반 SLAM의 표준 해법기로, 가우스-뉴턴법과 레벤버그-마쿼트 알고리즘을 제공한다. 희소 촐레스키 분해를 이용하여 수만 개의 포즈 변수를 갖는 문제를 효율적으로 풀어낸다.

Ceres Solver: 구글이 개발한 비선형 최소 제곱 해법기로, 자동 미분, 다양한 강건 비용 함수, 희소 해법을 통합적으로 지원한다. 로봇 캘리브레이션, 번들 조정, SLAM 등에 널리 사용된다.

7. 참고 문헌

Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
Björck, Å. (1996). Numerical Methods for Least Squares Problems. SIAM.
Kümmerle, R., Grisetti, G., Strasdat, H., Konolige, K., & Burgard, W. (2011). “g2o: A General Framework for Graph Optimization.” Proceedings of ICRA, 3607–3613.
Agarwal, S., Mierle, K., et al. (2022). Ceres Solver. http://ceres-solver.org.

version: 1.0