Gauss-Newton 방법 - 실험 도서관

Gauss-Newton 알고리즘의 개요

Gauss-Newton 방법은 비선형 최소제곱 문제를 해결하기 위한 반복적인 최적화 알고리즘이다. 카메라 캘리브레이션 과정에서 주로 사용되는 최적화 기법 중 하나로, 비선형 함수의 최소 제곱 오차를 최소화하는 데 목적이 있다. 이 방법은 Levenberg-Marquardt와 같은 다른 최적화 알고리즘에 비해 간단한 구조를 가지지만, 매우 효과적인 결과를 제공한다.

Gauss-Newton 방법은 기본적으로 Taylor 급수를 이용하여 비선형 함수를 선형 근사한 후, 그 선형화된 문제를 반복적으로 풀어나가는 방식이다. 수학적으로는 비선형 함수 $f(\mathbf{x})$ 가 주어졌을 때, 이 함수에 대해 잔차(residual) $r(\mathbf{x})$ 를 최소화하는 해 $\mathbf{x}$ 를 찾는 문제로 볼 수 있다.

잔차 함수 $r(\mathbf{x})$ 는 다음과 같이 정의된다:

$r(\mathbf{x}) = \mathbf{y} - f(\mathbf{x})$

여기서, $\mathbf{y}$ 는 관측된 값이고 $f(\mathbf{x})$ 는 모델에 의해 예측된 값이다. Gauss-Newton 방법은 잔차 $r(\mathbf{x})$ 의 제곱 합을 최소화하는 해를 찾는 것이 목표이다.

최소제곱 문제의 수학적 정의

Gauss-Newton 방법은 다음의 최소제곱 문제를 풀기 위한 방법이다:

$\min_{\mathbf{x}} \frac{1}{2} \sum_{i=1}^{n} \left( r_i(\mathbf{x}) \right)^2$

여기서 $r_i(\mathbf{x})$ 는 각 데이터 포인트에 대한 잔차를 의미한다. 이 식을 벡터 형태로 표현하면:

$\min_{\mathbf{x}} \frac{1}{2} \| \mathbf{r}(\mathbf{x}) \|^2$

여기서 $\mathbf{r}(\mathbf{x})$ 는 잔차 벡터로, 각 구성 요소가 잔차를 나타낸다. 이 문제는 잔차 벡터의 제곱합을 최소화하는 것이다.

선형화와 Jacobian 행렬

비선형 문제를 풀기 위해, Gauss-Newton 방법은 잔차 함수를 선형화하는 과정을 거친다. $\mathbf{x}$ 근처에서 잔차 함수 $\mathbf{r}(\mathbf{x})$ 를 Taylor 급수로 전개하면 다음과 같다:

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

여기서 $\mathbf{J}(\mathbf{x})$ 는 잔차 함수의 Jacobian 행렬이다. Jacobian 행렬 $\mathbf{J}(\mathbf{x})$ 는 각 잔차 $r_i(\mathbf{x})$ 에 대한 변수 $\mathbf{x}$ 의 편미분으로 구성된 행렬이다:

$\mathbf{J}(\mathbf{x}) = \begin{bmatrix} \frac{\partial r_1}{\partial x_1} & \frac{\partial r_1}{\partial x_2} & \dots & \frac{\partial r_1}{\partial x_n} \\ \frac{\partial r_2}{\partial x_1} & \frac{\partial r_2}{\partial x_2} & \dots & \frac{\partial r_2}{\partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial r_m}{\partial x_1} & \frac{\partial r_m}{\partial x_2} & \dots & \frac{\partial r_m}{\partial x_n} \end{bmatrix}$

따라서, 선형화된 잔차 함수에 대한 최적화 문제는 다음과 같이 표현할 수 있다:

$\min_{\Delta \mathbf{x}} \| \mathbf{r}(\mathbf{x}) + \mathbf{J}(\mathbf{x}) \Delta \mathbf{x} \|^2$

이 문제는 선형 최소제곱 문제로 변환되며, 이를 통해 $\Delta \mathbf{x}$ 의 해를 구할 수 있다. Gauss-Newton 방법은 이 과정을 반복하여 $\mathbf{x}$ 를 갱신한다.

Gauss-Newton 업데이트 규칙

최적화 문제를 풀기 위해, Gauss-Newton 방법은 선형 최소제곱 문제의 해를 이용해 변수 $\mathbf{x}$ 를 갱신한다. 최적화 과정에서 $\mathbf{x}$ 는 다음과 같이 업데이트된다:

$\Delta \mathbf{x} = - \left( \mathbf{J}^\top(\mathbf{x}) \mathbf{J}(\mathbf{x}) \right)^{-1} \mathbf{J}^\top(\mathbf{x}) \mathbf{r}(\mathbf{x})$

이 업데이트 식을 이용하여 새로운 $\mathbf{x}$ 는 다음과 같이 갱신된다:

$\mathbf{x}_{\text{new}} = \mathbf{x} + \Delta \mathbf{x}$

여기서, $\mathbf{J}^\top(\mathbf{x}) \mathbf{J}(\mathbf{x})$ 는 Hessian 행렬의 근사치로 사용되며, 이 값을 통해 비선형 문제를 선형 문제로 풀 수 있다.

Gauss-Newton 알고리즘의 수렴 조건

Gauss-Newton 방법이 수렴하기 위해서는 몇 가지 중요한 조건이 필요하다. 먼저, 초기 추정값 $\mathbf{x}_0$ 가 실제 해에 가깝게 설정되어야 한다. Gauss-Newton 방법은 기본적으로 2차 정확도(즉, 2차 미분에 대한 정보)를 사용하지 않기 때문에, 초기 값이 너무 멀리 떨어져 있을 경우 잘못된 지역 해에 빠질 수 있다.

또한, Jacobian 행렬 $\mathbf{J}(\mathbf{x})$ 가 비특이(singular)하지 않아야 한다. 만약 $\mathbf{J}(\mathbf{x})^\top \mathbf{J}(\mathbf{x})$ 가 특이 행렬이라면, 이 식의 역행렬이 존재하지 않게 되어 알고리즘이 실패할 수 있다. 따라서, 문제의 구조가 잘 정의되어 있고 충분히 독립적인 데이터 포인트가 있어야 한다.

Gauss-Newton 알고리즘의 단계

Gauss-Newton 방법은 다음의 반복적인 절차를 따른다:

초기 추정값 $\mathbf{x}_0$ 을 설정한다.
현재의 $\mathbf{x}_k$ 에서 잔차 함수 $\mathbf{r}(\mathbf{x}_k)$ 와 Jacobian $\mathbf{J}(\mathbf{x}_k)$ 를 계산한다.
업데이트 규칙 $\Delta \mathbf{x}_k = - \left( \mathbf{J}^\top(\mathbf{x}_k) \mathbf{J}(\mathbf{x}_k) \right)^{-1} \mathbf{J}^\top(\mathbf{x}_k) \mathbf{r}(\mathbf{x}_k)$ 을 사용하여 $\Delta \mathbf{x}_k$ 를 계산한다.
새로운 변수 값을 갱신한다: $\mathbf{x}_{k+1} = \mathbf{x}_k + \Delta \mathbf{x}_k$ .
종료 조건(예: $\|\Delta \mathbf{x}_k\|$ 또는 $\| \mathbf{r}(\mathbf{x}_k) \|$ 이 작은 값이 될 때까지)을 만족할 때까지 2번부터 4번 단계를 반복한다.

장단점

Gauss-Newton 방법은 다른 비선형 최적화 알고리즘에 비해 몇 가지 장점과 단점을 가진다.

장점

간단한 구조: Gauss-Newton 방법은 비교적 간단하게 구현할 수 있으며, 계산 비용도 적은 편이다. 이는 특히 다차원 문제에서도 쉽게 적용할 수 있다.
빠른 수렴: 초기 추정값이 실제 해에 가까운 경우, Gauss-Newton 방법은 매우 빠르게 수렴할 수 있다.

단점

초기값 의존성: Gauss-Newton 방법은 초기 추정값에 매우 민감하다. 잘못된 초기값을 사용하면 수렴하지 않거나 잘못된 해를 찾을 수 있다.
Jacobian 계산의 복잡성: Jacobian 행렬을 계산하는 것이 복잡하거나 비용이 많이 들 수 있다. 특히 함수가 복잡한 경우, 이 행렬을 효율적으로 계산하는 것이 까다로울 수 있다.