비선형 최소제곱(Nonlinear Least Squares, NLS) 문제는 데이터 과학, 공학, 통계학, 기계학습 등 수많은 과학 및 기술 분야에서 나타나는 근본적인 최적화 문제이다.1 이 문제는 관측된 데이터에 비선형 모델을 가장 잘 부합시키는 파라미터를 찾는 과정에서 발생하며, 그 핵심은 모델 예측과 실제 관측값 사이의 오차 제곱합을 최소화하는 데 있다. 가우스-뉴턴(Gauss-Newton, GN) 방법은 이러한 NLS 문제 해결을 위해 특별히 설계된 가장 대표적이고 효율적인 반복 최적화 알고리즘 중 하나로 평가받는다. 이 방법은 2차 미분 정보(헤시안 행렬)를 사용하여 빠른 수렴 속도를 보이는 뉴턴 방법의 강력함과, 1차 미분 정보(그래디언트)만을 사용하여 계산이 간단한 경사 하강법의 실용성 사이에서 절묘한 균형점을 찾으려는 시도에서 탄생했다.
본 보고서는 가우스-뉴턴 방법의 핵심 원리를 다각도에서 심층적으로 분석하는 것을 목표로 한다. 먼저 비선형 최소제곱 문제의 수학적 정립을 시작으로, 가우스-뉴턴 알고리즘의 유도 과정을 상세히 추적한다. 이 과정에서 뉴턴 방법과의 근본적인 관계를 헤시안 행렬의 근사라는 관점에서 명확히 규명하고, 이를 통해 알고리즘의 강점과 약점을 분석한다. 나아가 수렴 속도와 조건, 그리고 알고리즘이 실패할 수 있는 내재적 한계를 고찰하며, 이러한 한계를 극복하기 위해 제안된 레벤버그-마르카르트(Levenberg-Marquardt)와 같은 핵심적인 개선 알고리즘을 탐구한다. 마지막으로, 이론적 논의에 그치지 않고 컴퓨터 비전 분야의 번들 조정(Bundle Adjustment)과 로보틱스 분야의 그래프 기반 SLAM(Graph-based SLAM)이라는 대규모 실세계 문제에 가우스-뉴턴의 원리가 어떻게 적용되고 확장되는지 구체적인 사례를 통해 분석함으로써, 이론과 실제를 연결하는 포괄적인 통찰을 제공하고자 한다.
비선형 최소제곱 문제는 $m$개의 독립 변수-종속 변수 쌍으로 이루어진 관측 데이터 $(x_i, y_i)$가 주어졌을 때, 이를 가장 잘 설명하는 $n$개의 파라미터 벡터 $\boldsymbol{\beta} = [\beta_1, \dots, \beta_n]^T$를 가진 비선형 모델 함수 $f(x, \boldsymbol{\beta})$를 찾는 문제로 정의된다.1 문제의 목표는 각 관측값 $y_i$와 모델의 예측값 $f(x_i, \boldsymbol{\beta})$ 사이의 차이, 즉 잔차(residual) $r_i(\boldsymbol{\beta}) = y_i - f(x_i, \boldsymbol{\beta})$의 제곱합(Sum of Squared Errors, SSE)을 최소화하는 최적의 파라미터 $\boldsymbol{\beta}$를 찾는 것이다.1
이 목적 함수 $S(\boldsymbol{\beta})$는 $m$개의 잔차로 구성된 벡터 $\mathbf{r}(\boldsymbol{\beta}) = [r_1(\boldsymbol{\beta}), \dots, r_m(\boldsymbol{\beta})]^T$를 이용하여 다음과 같이 간결하게 표현할 수 있다.
\(S(\boldsymbol{\beta}) = \sum_{i=1}^{m} r_i(\boldsymbol{\beta})^2 = \mathbf{r}(\boldsymbol{\beta})^T \mathbf{r}(\boldsymbol{\beta}) = ||\mathbf{r}(\boldsymbol{\beta})||_2^2\) 일반적으로 데이터의 개수 $m$이 파라미터의 개수 $n$보다 크거나 같은 과결정 시스템(overdetermined system, $m \ge n$)을 다루게 되는데, 이 경우 모든 잔차 $r_i$를 동시에 0으로 만드는 완벽한 해는 거의 존재하지 않는다.7 따라서 오차의 총합을 최소화하는 최적의 근사해를 찾는 것이 현실적인 목표가 된다.
이러한 최적화 문제를 푸는 접근법은 크게 두 가지로 나뉜다. 첫째는 1차 최적화 기법으로, 대표적으로 경사 하강법(Gradient Descent)이 있다. 이 방법은 목적 함수의 1차 미분 정보인 그래디언트(gradient)만을 사용하여 함수의 값이 가장 가파르게 감소하는 방향으로 파라미터를 점진적으로 업데이트한다.8 구현이 매우 간단하지만, 수렴 속도가 느리고 최적의 스텝 크기(학습률, learning rate)를 결정하기 어려운 단점이 있다.10
둘째는 2차 최적화 기법으로, 뉴턴 방법(Newton’s method)이 대표적이다. 이 방법은 1차 미분 정보뿐만 아니라 2차 미분 정보인 헤시안(Hessian) 행렬까지 활용하여 목적 함수를 국소적으로 2차 함수로 근사한다.8 이 2차 모델의 최소점을 다음 스텝으로 삼기 때문에, 해 근처에서 매우 빠른 2차 수렴(quadratic convergence)이 가능하다.12 하지만 매 반복마다 헤시안 행렬을 계산하고 그 역행렬을 구해야 하므로 계산 비용이 매우 크다는 치명적인 단점을 가진다.
여기서 비선형 최소제곱 문제의 구조적 특성이 중요해진다. 일반적인 최적화 문제와 달리, NLS의 목적 함수 $S(\boldsymbol{\beta})$는 ‘잔차 제곱의 합’이라는 매우 구체적인 형태를 띤다. 가우스-뉴턴 방법의 독창성은 바로 이 구조적 특성을 깊이 파고들어, 2차 최적화의 핵심인 헤시안 행렬을 직접 계산하지 않고도 유사한 효과를 얻는 길을 찾아냈다는 점에 있다. 이 접근법의 논리적 흐름은 다음과 같다. 먼저, 일반적인 함수 $g(\mathbf{x})$를 최적화하는 뉴턴 방법은 헤시안 $H_g$를 필요로 한다. NLS 문제의 목적 함수 $S(\boldsymbol{\beta}) = \mathbf{r}^T\mathbf{r}$의 헤시안을 직접 계산해보면, 그 구조가 $2\mathbf{J}^T\mathbf{J} + (\text{2차 미분 항})$ 형태로 나타남을 알 수 있다.2 여기서
$\mathbf{J}$는 잔차 벡터 $\mathbf{r}$의 1차 미분인 자코비안(Jacobian) 행렬이다. 이는 목적 함수 $S$의 2차 정보(헤시안) 중 상당 부분이 잔차 $\mathbf{r}$의 1차 정보($\mathbf{J}$)만으로 구성된다는 중요한 사실을 시사한다. 이로부터 “만약 2차 미분 항을 무시할 수 있다면, 1차 미분 정보만으로 2차 최적화와 유사한 성능을 낼 수 있지 않을까?”라는 혁신적인 아이디어가 도출되며, 이것이 바로 가우스-뉴턴 방법의 출발점이 된다.
가우스-뉴턴 방법의 핵심 아이디어는 복잡한 비선형 목적 함수 $S(\boldsymbol{\beta})$를 직접 다루는 대신, 그 구성 요소인 비선형 잔차 함수 $\mathbf{r}(\boldsymbol{\beta})$를 현재 파라미터 추정치 $\boldsymbol{\beta}_k$ 근방에서 1차 테일러 급수를 이용해 선형 함수로 근사하는 것이다.1 파라미터의 작은 변화량 $\Delta\boldsymbol{\beta}$에 대한 잔차의 변화는 다음과 같이 근사할 수 있다.
\(\mathbf{r}(\boldsymbol{\beta}_k + \Delta\boldsymbol{\beta}) \approx \mathbf{r}(\boldsymbol{\beta}_k) + \mathbf{J}(\boldsymbol{\beta}_k) \Delta\boldsymbol{\beta}\) 여기서 $\mathbf{J}(\boldsymbol{\beta}k)$는 현재 추정치 $\boldsymbol{\beta}_k$에서 계산된 잔차 함수 $\mathbf{r}$의 자코비안 행렬이며, 그 원소는 $(J){ij} = \frac{\partial r_i}{\partial \beta_j}$로 정의된다.6
| 이 선형 근사식을 원래의 목적 함수 $S(\boldsymbol{\beta}) = | \mathbf{r}(\boldsymbol{\beta}) | _2^2$에 대입하면, 다음 파라미터 업데이트 스텝 $\Delta\boldsymbol{\beta}$를 찾기 위한 선형 최소제곱 문제를 얻게 된다.1 |
\(\min_{\Delta\boldsymbol{\beta}} ||\mathbf{r}(\boldsymbol{\beta}_k) + \mathbf{J}(\boldsymbol{\beta}_k) \Delta\boldsymbol{\beta}||_2^2\) 이 문제는 $\Delta\boldsymbol{\beta}$에 대한 2차 함수이므로, 이를 최소화하는 해는 목적 함수를 $\Delta\boldsymbol{\beta}$에 대해 미분하여 그 결과가 0이 되는 지점에서 찾을 수 있다.1 미분 과정은 다음과 같다.
\(\frac{\partial}{\partial \Delta\boldsymbol{\beta}} ||\mathbf{r} + \mathbf{J} \Delta\boldsymbol{\beta}||_2^2 = \frac{\partial}{\partial \Delta\boldsymbol{\beta}} (\mathbf{r} + \mathbf{J} \Delta\boldsymbol{\beta})^T (\mathbf{r} + \mathbf{J} \Delta\boldsymbol{\beta}) = 2\mathbf{J}^T(\mathbf{r} + \mathbf{J} \Delta\boldsymbol{\beta}) = \mathbf{0}\) 이 식을 $\Delta\boldsymbol{\beta}$에 대해 정리하면, 가우스-뉴턴 방법의 핵심 업데이트 규칙인 정규방정식(Normal Equations)이 도출된다.1
\((\mathbf{J}^T \mathbf{J}) \Delta\boldsymbol{\beta} = -\mathbf{J}^T \mathbf{r}\) 이 정규방정식은 $\Delta\boldsymbol{\beta}$에 대한 선형 연립방정식이다. 만약 $\mathbf{J}^T \mathbf{J}$ 행렬이 가역(invertible)이라면, 업데이트 스텝 $\Delta\boldsymbol{\beta}$는 다음과 같이 직접 계산할 수 있다.
\(\Delta\boldsymbol{\beta} = -(\mathbf{J}^T \mathbf{J})^{-1} \mathbf{J}^T \mathbf{r}\) 이러한 수학적 원리에 기반한 가우스-뉴턴 알고리즘의 단계별 절차는 다음과 같다.3
초기화: 파라미터의 초기 추정치 $\boldsymbol{\beta}_0$와 수렴 판정을 위한 허용오차 $\epsilon$을 설정한다.
반복: 다음 과정을 수렴할 때까지 반복한다.
a. 현재 파라미터 $\boldsymbol{\beta}_k$에서 잔차 벡터 $\mathbf{r}(\boldsymbol{\beta}_k)$와 자코비안 행렬 $\mathbf{J}(\boldsymbol{\beta}_k)$를 계산한다.
b. 정규방정식 $(\mathbf{J}(\boldsymbol{\beta}_k)^T \mathbf{J}(\boldsymbol{\beta}_k)) \Delta\boldsymbol{\beta}_k = -\mathbf{J}(\boldsymbol{\beta}_k)^T \mathbf{r}(\boldsymbol{\beta}_k)$를 풀어 업데이트 스텝 $\Delta\boldsymbol{\beta}_k$를 구한다.
c. 파라미터를 업데이트한다: $\boldsymbol{\beta}_{k+1} = \boldsymbol{\beta}_k + \Delta\boldsymbol{\beta}_k$.
| 종료 조건: 업데이트 스텝의 크기 $ | \Delta\boldsymbol{\beta}_k | $가 미리 설정한 허용오차 $\epsilon$보다 작아지거나, 목적 함수 $S(\boldsymbol{\beta})$의 감소량이 매우 작아지면 반복을 중단하고 $\boldsymbol{\beta}_{k+1}$을 최적해로 간주한다. |
이 과정은 본질적으로 다루기 힘든 비선형 최적화 문제를 매 단계마다 풀기 쉬운 선형 대수 문제로 변환하는 ‘분할 정복(Divide and Conquer)’ 전략의 한 형태로 볼 수 있다. 즉, 전체 문제의 비선형성을 직접 다루는 대신, 현재 지점에서 가장 적합한 선형 모델을 만들고 그 모델의 최적해를 향해 한 걸음 나아가는 과정을 반복함으로써 점진적으로 해에 접근하는 것이다. 이 변환 과정이야말로 가우스-뉴턴 알고리즘의 정수라 할 수 있다.
가우스-뉴턴 방법의 본질을 가장 명확하게 이해하는 방법은 이를 일반적인 2차 최적화 기법인 뉴턴 방법과 비교하는 것이다. 일반적인 함수 $S(\boldsymbol{\beta})$를 최소화하기 위한 뉴턴 방법의 업데이트 스텝 $\Delta\boldsymbol{\beta}_{\text{Newton}}$은 목적 함수의 그래디언트 $\mathbf{g} = \nabla S$와 헤시안 행렬 $\mathbf{H} = \nabla^2 S$를 이용하여 다음과 같이 정의된다.8
\(\Delta\boldsymbol{\beta}_{\text{Newton}} = -\mathbf{H}^{-1} \mathbf{g}\) 비선형 최소제곱 문제의 목적 함수 $S(\boldsymbol{\beta}) = \mathbf{r}(\boldsymbol{\beta})^T \mathbf{r}(\boldsymbol{\beta})$에 대해 그래디언트와 헤시안을 직접 계산하면 다음과 같은 형태를 얻는다.2
여기서 $\mathbf{J}$는 잔차 벡터 $\mathbf{r}$의 자코비안이고, $\nabla^2 r_i$는 개별 잔차 함수 $r_i$의 헤시안 행렬이다. 뉴턴 방법은 이 완전한 헤시안 행렬 $\mathbf{H}$를 사용해야 한다.
반면, 가우스-뉴턴 방법은 위 헤시안 표현식에서 두 번째 항, 즉 잔차 $r_i$와 잔차의 2차 미분($\nabla^2 r_i$)의 곱으로 이루어진 항을 의도적으로 무시한다. 이 항을 생략함으로써 얻어지는 근사 헤시안 $\mathbf{H}_{\text{GN}} = 2\mathbf{J}^T \mathbf{J}$를 뉴턴 방법의 업데이트 규칙에 대입하면 정확히 가우스-뉴턴의 정규방정식이 유도된다.2
\(\Delta\boldsymbol{\beta}_{\text{GN}} = -(2\mathbf{J}^T \mathbf{J})^{-1} (2\mathbf{J}^T \mathbf{r}) = -(\mathbf{J}^T \mathbf{J})^{-1} \mathbf{J}^T \mathbf{r}\) 이 헤시안 근사는 가우스-뉴턴 방법의 모든 특성을 결정하는 핵심적인 단계이다. 이 근사가 가져오는 장점과 단점은 명확하다.
장점: 가장 큰 장점은 계산 효율성이다. 복잡하고 비용이 많이 드는 2차 미분($\nabla^2 r_i$)을 계산할 필요가 전혀 없어진다.18 오직 1차 미분 정보인 자코비안만으로 2차 최적화에 근접하는 성능을 낼 수 있는 잠재력을 갖게 된다. 또한, 자코비안
$\mathbf{J}$가 full rank를 가지면 $\mathbf{J}^T \mathbf{J}$는 항상 양의 정부호(positive definite) 행렬이 된다. 이는 뉴턴 방법에서 헤시안이 양의 정부호가 아닐 경우 업데이트 방향이 상승 방향이 될 수 있는 문제와 달리, 가우스-뉴턴의 업데이트 방향은 항상 목적 함수를 감소시키는 하강 방향(descent direction)임을 보장해준다.19
단점: 이 근사는 특정 조건 하에서만 유효하다. 무시된 항 $2\sum r_i \nabla^2 r_i$의 크기가 작아야 근사 헤시안이 실제 헤시안과 유사해진다. 이 항의 크기는 두 가지 요인에 의해 결정된다. 첫째, 최적해 근방에서 잔차 $r_i$가 0에 매우 가까운 경우(small-residual problems). 둘째, 잔차 함수 $r_i$ 자체의 비선형성(즉, 곡률을 나타내는 $\nabla^2 r_i$)이 작은 경우. 만약 잔차가 크거나(large-residual problems) 비선형성이 강하면 실제 헤시안과의 오차가 커져 수렴 속도가 현저히 저하되거나 최악의 경우 발산할 수 있다.17
결국 가우스-뉴턴은 ‘최적화 문제의 구조적 특성을 이용한 의도적인 정보 손실’ 전략으로 해석할 수 있다. 뉴턴 방법이 요구하는 완전한 2차 정보 대신, 계산하기 쉬운 1차 정보($\mathbf{J}$)로 구성된 ‘근사 2차 정보’($\mathbf{J}^T\mathbf{J}$)를 사용하는 것이다. 이 트레이드오프의 성공 여부는 ‘버려진 정보’의 중요성에 달려 있으며, 이는 가우스-뉴턴 알고리즘의 성능이 해결하고자 하는 문제 자체의 특성에 깊이 의존함을 의미한다.
가우스-뉴턴 방법의 성능을 평가하기 위해서는 수렴 속도와 조건을 이해하고, 알고리즘이 실패할 수 있는 한계점을 명확히 인지하는 것이 중요하다.
가우스-뉴턴의 수렴 속도는 헤시안 근사의 정확도에 직접적으로 의존하며, 이는 최적해에서의 잔차 크기에 의해 결정된다.
이러한 수렴이 보장되기 위해서는 몇 가지 전제 조건이 충족되어야 한다.16 첫째, 초기 추정치 $\boldsymbol{\beta}_0$가 최적해에 충분히 가까워야 국소적 수렴이 보장된다.1 둘째, 매 반복에서 자코비안 행렬 $\mathbf{J}$가 full column rank를 가져야 한다. 이는 $\mathbf{J}^T\mathbf{J}$가 가역 행렬임을 보장하며, 모델의 파라미터들이 데이터를 통해 잘 식별됨을 의미한다. 마지막으로, 앞서 언급했듯이 최적해에서의 잔차 크기가 작아야 빠른 수렴을 기대할 수 있다.
가우스-뉴턴 방법은 효율적인 만큼 여러 내재적 한계점을 가지고 있다.
이러한 특징들을 종합하여 주요 최적화 알고리즘들을 비교하면 다음 표와 같다.
Table 1: 주요 최적화 알고리즘 비교
| 특징 | 경사 하강법 (Gradient Descent) | 뉴턴 방법 (Newton’s Method) | 가우스-뉴턴 (Gauss-Newton) | 레벤버그-마르카르트 (Levenberg-Marquardt) |
|---|---|---|---|---|
| 기본 아이디어 | 그래디언트 반대 방향으로 이동 | 2차 근사 모델의 최소점으로 이동 | 잔차의 선형 근사 모델의 최소점으로 이동 | GN과 GD의 적응적 결합 (신뢰 영역) |
| 업데이트 규칙 | $\Delta\mathbf{x} = -\alpha \mathbf{g}$ | $\Delta\mathbf{x} = -\mathbf{H}^{-1} \mathbf{g}$ | $\Delta\mathbf{x} = -(\mathbf{J}^T\mathbf{J})^{-1}\mathbf{J}^T\mathbf{r}$ | $\Delta\mathbf{x} = -(\mathbf{J}^T\mathbf{J}+\lambda\mathbf{I})^{-1}\mathbf{J}^T\mathbf{r}$ |
| 필요 정보 | 1차 미분 (Gradient) | 1차, 2차 미분 (Hessian) | 1차 미분 (Jacobian) | 1차 미분 (Jacobian) |
| 수렴 속도 | 선형 (느림) | 2차 (매우 빠름) | 2차 (잔차 작을 시) / 선형 (잔차 클 시) | GN과 유사하나 더 안정적 |
| 계산 비용/반복 | 낮음 | 매우 높음 (Hessian 계산 및 역행렬) | 중간 (Jacobian 계산 및 역행렬) | 중간 (GN과 유사) |
| 강인성/안정성 | 학습률에 따라 비교적 안정적 | 불안정 (H가 양의 정부호 아닐 시) | 불안정 ($\mathbf{J}^T\mathbf{J}$가 특이 행렬일 시) | 매우 높음 |
| 주요 장점 | 구현 용이, 낮은 메모리 | 빠른 수렴 속도 | NLS에 특화된 효율성 | 강인성, 넓은 수렴 반경 |
| 주요 단점 | 느린 수렴, 학습률 민감 | 높은 계산 비용, 수렴 보장 안됨 | Large-residual 문제 및 특이 행렬에 취약 | 파라미터($\lambda$) 튜닝 필요 |
이 표는 각 알고리즘이 ‘속도-비용-안정성’이라는 다차원적 공간에서 어떤 위치를 차지하는지 명확히 보여준다. 가우스-뉴턴은 뉴턴 방법의 ‘속도’와 경사 하강법의 ‘비용’ 사이에서 NLS 문제에 최적화된 지점을 찾으려 시도하며, 레벤버그-마르카르트는 여기에 ‘안정성’을 더한 진화된 형태임을 직관적으로 이해할 수 있게 한다.
가우스-뉴턴 방법의 내재적 한계를 극복하고 더 넓은 범위의 문제에 적용하기 위해 다양한 개선 알고리즘이 개발되었다. 이들은 주로 강인성(robustness)과 대규모 문제에 대한 확장성(scalability)을 높이는 데 초점을 맞춘다.
가우스-뉴턴이 계산한 업데이트 방향 $\Delta\boldsymbol{\beta}$은 올바르지만, 그 스텝의 크기가 너무 커서 오히려 목적 함수 값을 증가시키며 발산하는 경우가 있다. 라인 서치는 이를 방지하기 위한 간단하면서도 효과적인 전략이다. 업데이트 규칙을 $\boldsymbol{\beta}_{k+1} = \boldsymbol{\beta}_k + \alpha \Delta\boldsymbol{\beta}_k$로 수정하고, 목적 함수 $S$를 실제로 감소시키는 최적의 스텝 크기(step size) $\alpha$ (단, $\alpha > 0$)를 찾는 과정을 추가한다.16 이를 통해 알고리즘이 너무 과감한 스텝을 밟지 않도록 제어하여 수렴 안정성을 높일 수 있다.
레벤버그-마르카르트 알고리즘은 가우스-뉴턴의 가장 성공적이고 널리 사용되는 개선안으로, ‘감쇠 최소제곱법(Damped Least Squares)’으로도 불린다.13 이 방법은 가우스-뉴턴의 $\mathbf{J}^T\mathbf{J}$ 행렬이 특이하거나 불량 조건일 때 발생하는 문제를 해결하기 위해 정규방정식에 감쇠 인자(damping factor) $\lambda$를 추가한다.25
\((\mathbf{J}^T \mathbf{J} + \lambda \mathbf{I}) \Delta\boldsymbol{\beta} = -\mathbf{J}^T \mathbf{r}\) 여기서 $\mathbf{I}$는 항등 행렬이며, $\lambda$는 음이 아닌 스칼라 값이다. 이 감쇠 인자 $\lambda$의 역할은 알고리즘의 동작을 동적으로 조절하는 것이다.
LM 알고리즘은 신뢰 영역(Trust Region) 방법의 한 형태로도 해석될 수 있다. 즉, 현재의 선형 근사가 유효하다고 믿는 ‘신뢰 영역’ 반경 내에서만 해를 찾는 제약된 최적화 문제를 푸는 것과 같다.13
$\lambda$는 이 신뢰 영역의 크기를 간접적으로 조절하는 역할을 한다. 매 반복마다 실제 목적 함수 감소량과 모델이 예측한 감소량을 비교하여 그 비율($\rho$)을 계산하고, 이 비율에 따라 $\lambda$ 값을 동적으로 조절한다. 이를 통해 알고리즘은 해에서 멀리 있을 때는 경사 하강법처럼 안정적으로 움직이고, 해에 가까워지면 가우스-뉴턴처럼 빠르게 수렴하는 지능적인 전환을 수행한다.
수만 개 이상의 파라미터를 가진 대규모 문제(예: 번들 조정)에서는 $\mathbf{J}^T\mathbf{J}$ 행렬을 메모리에 명시적으로 구성하고 그 역행렬을 구하는 것이 계산적으로 불가능하다. 이러한 문제를 해결하기 위해 정규방정식을 근사적으로 푸는 기법들이 개발되었다.
이러한 개선 알고리즘들의 발전 과정은 최적화 알고리즘 개발의 보편적인 패턴을 보여준다. 즉, 기본 알고리즘의 수렴 실패 사례를 분석하고, 이를 막기 위한 안전장치(라인 서치, 감쇠)를 추가하여 강인성을 높인 후, 대규모 문제에 적용하기 위해 계산 병목 지점(선형 시스템 풀이)을 근사적인 방법으로 대체하여 확장성을 확보하는 방향으로 진화한다.
가우스-뉴턴 방법과 그 변형들은 이론적인 중요성을 넘어, 컴퓨터 비전과 로보틱스 분야의 핵심적인 대규모 최적화 문제를 해결하는 데 필수적인 도구로 사용된다. 특히 번들 조정(Bundle Adjustment)과 그래프 기반 SLAM은 가우스-뉴턴 원리가 문제의 구조와 결합하여 어떻게 강력한 성능을 발휘하는지를 보여주는 대표적인 사례이다.
번들 조정은 여러 장의 이미지에서 관측된 2D 특징점들의 위치 정보를 이용하여, 3D 공간상에 존재하는 점들의 3차원 좌표와 각 이미지를 촬영한 카메라의 위치/자세(외부 파라미터) 및 초점 거리 등(내부 파라미터)을 동시에 정밀하게 최적화하는 문제이다.30 이는 다중 시점 영상으로부터 3차원 구조를 복원하는 SfM(Structure from Motion)이나 로봇이 자신의 위치를 추정하며 지도를 작성하는 SLAM의 마지막 단계에서 전역적인 일관성을 확보하기 위한 핵심 후처리 과정으로 사용된다.32
BA의 비용 함수는 재투영 오차(reprojection error)의 제곱합으로 정의된다. 즉, 추정된 3D 점을 추정된 카메라 모델을 통해 2D 이미지 평면에 투영시킨 좌표(예측값)와, 이미지에서 실제 관측된 2D 특징점 좌표(관측값) 사이의 유클리드 거리 제곱합을 최소화하는 것이다.31
\(\min_{\mathbf{C}_j, \mathbf{X}_i} \sum_{i} \sum_{j} v_{ij} ||\mathbf{u}_{ij} - \pi(\mathbf{C}_j, \mathbf{X}_i)||^2\) 여기서 $\mathbf{C}j$는 $j$번째 카메라의 파라미터, $\mathbf{X}_i$는 $i$번째 3D 점의 좌표, $\pi(\cdot)$는 투영 함수, $\mathbf{u}{ij}$는 관측된 2D 좌표, $v_{ij}$는 점 $i$가 카메라 $j$에서 보이는지 여부를 나타내는 이진 변수이다.
이 문제의 가장 중요한 특징은 자코비안과 헤시안($\mathbf{J}^T\mathbf{J}$) 행렬이 매우 거대하지만, 동시에 극도로 희소(sparse)한 블록 구조를 가진다는 점이다.32 그 이유는 하나의 재투영 오차 항 $r_{ij} = \mathbf{u}_{ij} - \pi(\mathbf{C}_j, \mathbf{X}_i)$이 수많은 파라미터 중 오직 하나의 카메라 파라미터 $\mathbf{C}_j$와 하나의 3D 점 파라미터 $\mathbf{X}_i$에만 의존하기 때문이다.
이러한 희소 구조를 효과적으로 활용하기 위해 슈어 보수(Schur Complement) 트릭이 사용된다. 정규방정식을 카메라 파라미터와 3D 점 파라미터에 대한 블록 행렬로 재배열한 후, 대수적 조작을 통해 3D 점 파라미터에 대한 항을 소거한다. 이를 통해 거대한 전체 시스템을 직접 푸는 대신, 상대적으로 크기가 훨씬 작은 ‘카메라 시스템’을 먼저 풀고, 그 결과를 이용해 각 3D 점의 위치를 계산하는 방식으로 문제를 분리할 수 있다.32 이 기법은 문제의 물리적 구조(카메라와 점의 관계)가 수학적 구조(행렬의 희소성)로 이어지고, 이를 다시 효율적인 대수적 기법(슈어 보수)으로 풀어내는 완벽한 예시이다. 덕분에 수십만 개 이상의 파라미터를 가진 대규모 BA 문제도 현실적인 시간 내에 해결이 가능해졌다.
그래프 기반 SLAM은 로봇의 이동 경로(일련의 자세들)와 환경 지도(랜드마크)를 하나의 거대한 그래프로 표현하여 SLAM 문제를 해결하는 접근법이다. 이 그래프에서 노드(vertex)는 특정 시점의 로봇 자세 또는 랜드마크의 위치를 나타내고, 엣지(edge)는 두 노드 간의 공간적 제약 조건을 모델링한다. 이러한 제약은 로봇의 움직임 측정(오도메트리)이나 랜드마크 관측으로부터 얻어진다.34 센서 측정에는 항상 노이즈가 포함되므로, 시간이 지남에 따라 오차가 누적되어 그래프 전체의 일관성이 깨지게 된다.
그래프 기반 SLAM의 목표는 이처럼 일관성이 깨진 그래프를, 모든 엣지 제약 조건을 통계적으로 가장 잘 만족시키는 노드 구성으로 바로잡는 것이다. 이는 측정된 제약과 현재 추정된 노드 위치 간의 오차 제곱합을 최소화하는 비선형 최소제곱 문제로 공식화된다.37
\(\mathbf{x}^* = \arg\min_{\mathbf{x}} \sum_{i,j} \mathbf{e}_{ij}(\mathbf{x}_i, \mathbf{x}_j)^T \mathbf{\Omega}_{ij} \mathbf{e}_{ij}(\mathbf{x}_i, \mathbf{x}_j)\) 여기서 $\mathbf{x}$는 모든 노드(자세, 랜드마크)의 상태 벡터, $\mathbf{e}{ij}$는 엣지에 해당하는 오차 함수, $\mathbf{\Omega}{ij}$는 해당 측정의 신뢰도를 나타내는 정보 행렬(불확실성의 역행렬)이다.
가우스-뉴턴 방법은 이 최적화 문제를 푸는 데 핵심적인 역할을 한다.
BA와 SLAM 사례에서 가우스-뉴턴은 단순한 최적화 도구를 넘어, 문제의 물리적/기하학적 구조를 계산 가능한 수학적 형태로 변환하고 이를 효율적으로 해결하는 ‘언어’ 또는 ‘프레임워크’의 역할을 수행한다. 알고리즘의 성공은 순수한 수치적 성능뿐만 아니라, 문제의 본질적인 구조를 얼마나 잘 활용하는지에 달려 있음을 명확히 보여준다.
가우스-뉴턴 방법은 비선형 최소제곱 문제의 목적 함수가 ‘잔차 제곱의 합’이라는 독특한 구조를 가진다는 점을 예리하게 활용한 최적화 알고리즘이다. 이 구조적 특성을 통해, 계산 비용이 높은 헤시안 행렬의 2차 미분 항을 생략하고 1차 미분 정보(자코비안)만으로 2차 최적화에 근접하는 성능을 달성함으로써 효율성을 극대화했다.
이론적으로 가우스-뉴턴 방법은 잔차가 작은 문제에서 뉴턴 방법과 유사한 2차 수렴 속도를 보이며 매우 강력한 성능을 발휘한다. 하지만 현실에서 마주하는 많은 문제, 특히 잔차가 크거나 파라미터 식별이 어려운 문제에서는 수렴이 선형으로 저하되거나, 자코비안의 불량 조건으로 인해 수치적으로 불안정해져 발산할 수 있다는 명백한 한계를 지닌다. 이러한 이론과 현실의 간극은 가우스-뉴턴의 빠른 수렴성과 경사 하강법의 안정성을 지능적으로 결합한 레벤버그-마르카르트 알고리즘의 개발을 촉진하는 중요한 계기가 되었다.
현대적 관점에서 가우스-뉴턴의 원리는 그 자체로 사용되기보다는, 더 큰 문제 해결 프레임워크의 핵심적인 이론적 기반으로 작용한다. 특히 컴퓨터 비전의 번들 조정과 로보틱스의 SLAM과 같은 대규모 최적화 문제에서, 가우스-뉴턴의 기본 원리는 문제의 희소 구조를 활용하는 슈어 보수나 켤레 기울기법과 같은 고급 선형 대수 기법과 결합된다. 이를 통해 수십만, 수백만 개의 파라미터를 가진, 과거에는 해결이 불가능했던 문제들을 효율적으로 풀 수 있는 강력한 프레임워크로 확장된다. 결국 가우스-뉴턴 방법은 단순한 수치 해석 알고리즘을 넘어, 복잡한 실세계의 기하학적 문제를 풀 수 있는 수학적 모델로 변환하고 해결하는 현대 계산 과학의 중요한 패러다임 중 하나로 확고히 자리매김하고 있다.