Gauss-Newton

**가우스-뉴턴(Gauss-Newton)**은 비선형 최소제곱(nonlinear least squares) 문제의 근간이 되는 반복 알고리즘입니다 — 사실상 모든 SLAM 백엔드 계산(번들 조정, 포즈 그래프 최적화, PnP 정제, 직접 이미지 정합)이 귀결되는 문제 종류입니다. 비용의 특수한 제곱합 구조를 활용함으로써, 1차 도함수만 계산하면서도 2차에 가까운 수렴 속도를 얻어냅니다.

유도

상태 x∈Rn\mathbf{x} \in \mathbb{R}^n에 대한 잔차 벡터 e(x)∈Rm\mathbf{e}(\mathbf{x}) \in \mathbb{R}^m로 구성된 비용을 최소화합니다:

F(x)=12∥e(x)∥2F(\mathbf{x}) = \frac{1}{2} \|\mathbf{e}(\mathbf{x})\|^2

현재 추정값 xk\mathbf{x}_k에서 계산한 야코비안 Jk=∂e/∂xJ_k = \partial \mathbf{e} / \partial \mathbf{x}를 이용해 (비용이 아니라) 잔차를 선형화합니다:

e(xk+Δx)≈e(xk)+JkΔx\mathbf{e}(\mathbf{x}_k + \Delta\mathbf{x}) \approx \mathbf{e}(\mathbf{x}_k) + J_k \Delta\mathbf{x}

이를 대입하면 Δx\Delta\mathbf{x}에 대한 비용의 이차 모델이 얻어집니다:

F(xk+Δx)≈12∥ek∥2+ΔxTJkTek+12ΔxTJkTJkΔxF(\mathbf{x}_k + \Delta\mathbf{x}) \approx \frac{1}{2}\|\mathbf{e}_k\|^2 + \Delta\mathbf{x}^T J_k^T \mathbf{e}_k + \frac{1}{2} \Delta\mathbf{x}^T J_k^T J_k \Delta\mathbf{x}

Δx\Delta\mathbf{x}에 대한 도함수를 0으로 설정하면 **정규 방정식(normal equations)**이 얻어집니다:

(JkTJk) Δx=−JkTek(J_k^T J_k)\, \Delta\mathbf{x} = -J_k^T \mathbf{e}_k

Δx\Delta\mathbf{x}를 구합니다(실제로는 명시적인 역행렬 계산이 아니라 희소한 JTJJ^T J의 콜레스키 분해를 통해). 업데이트 xk+1=xk+Δx\mathbf{x}_{k+1} = \mathbf{x}_k + \Delta\mathbf{x}를 적용하고, 다시 선형화한 뒤, 업데이트나 비용 변화가 무시할 만한 수준이 될 때까지 반복합니다.

측정 공분산이 있는 경우, 잔차는 정보 행렬 Ω=Σ−1\Omega = \Sigma^{-1}로 가중되며 정규 방정식은 JTΩJ Δx=−JTΩ eJ^T \Omega J \,\Delta\mathbf{x} = -J^T \Omega\, \mathbf{e}가 됩니다 — 대수는 동일하며, 이는 정확히 가우스 노이즈 하에서의 MAP 추정에 해당합니다.

뉴턴 방법과의 관계

뉴턴 방법은 FF의 진짜 헤시안을 사용합니다:

∇2F=JTJ+∑iei ∇2ei\nabla^2 F = J^T J + \sum_i e_i \, \nabla^2 e_i

가우스-뉴턴은 두 번째 항을 버려서 H≈JTJH \approx J^T J로 근사합니다. 이는 (2차 도함수가 필요 없어) 저렴하며, 최적해에서 잔차가 작을 때(모델이 데이터를 잘 맞출 때)나 거의 선형일 때 — 즉 수렴 중인 SLAM 문제의 전형적인 상태 — 정확합니다. 해 근처에서는 수렴이 거의 이차적입니다. 이 근사는 또한 H⪰0H \succeq 0을 보장하므로, HH가 비특이(nonsingular)인 한 계산된 스텝은 항상 하강 방향(descent direction)이 됩니다.

실패 모드

매니폴드 위에서

자세는 Rn\mathbb{R}^n이 아니라 SE(3)\mathrm{SE}(3) 위에 존재하므로, 업데이트는 지수 사상(exponential map)을 통해 적용됩니다: 증분을 ξ∈R6\boldsymbol{\xi} \in \mathbb{R}^6으로 매개변수화하고, ξ\boldsymbol{\xi}에 대해 정규 방정식을 풀고, T←T⋅exp⁡(ξ^)T \leftarrow T \cdot \exp(\hat{\boldsymbol{\xi}})로 업데이트합니다. 야코비안은 이 국소 섭동(local perturbation)에 대해 취해집니다. 모든 SLAM 솔버(g2o, Ceres, GTSAM)는 이러한 “국소 벡터를 최적화하고 매니폴드로 리트랙션(retract)한다” 형태로 가우스-뉴턴/LM을 구현합니다.

SLAM에서의 의미

가우스-뉴턴은 SLAM의 바로 그 내부 루프입니다. 번들 조정은 재투영 오차에 대한 가우스-뉴턴/LM이며, 여기서 JTJJ^T J의 희소한 블록 구조(자세들은 관측을 통해서만 점들과 결합됨)는 슈어 컴플리먼트(Schur complement)를 통해 활용됩니다. 포즈 그래프 최적화는 상대 자세 잔차에 대한 가우스-뉴턴이며, 직접법(LSD-SLAM, DSO)은 포토메트릭 오차에 대해 이를 실행하고, ICP의 정합 단계조차도 하나의 가우스-뉴턴 반복입니다. 어떤 SLAM 백엔드 논문을 읽더라도 여기서 정의된 용어(잔차, 야코비안, 헤시안 근사, 정규 방정식, 감쇠)에 익숙해야 하며, 실무적인 디버깅(내 최적화가 왜 발산했는가? 내 헤시안이 왜 특이한가?) 대부분은 위에 나열된 가정들로 거슬러 올라갑니다.

관련 문서