Levenberg-Marquardt 최적화

Levenberg-Marquardt 알고리즘은 비선형 최소자승 문제를 해결하는데 주로 사용되는 최적화 기법으로, 카메라 캘리브레이션에서 매개변수 최적화에 매우 유용하다. 이 알고리즘은 Gauss-Newton 방법과 Gradient Descent 방법의 장점을 결합한 방식으로, 안정성과 수렴 속도를 모두 고려한 비선형 최적화에 적합한다.

비선형 최소자승 문제 정의

카메라 캘리브레이션 과정에서 우리는 모델 파라미터를 추정하여 관찰된 데이터와 모델이 예측하는 데이터 간의 차이를 최소화하려고 한다. 이 과정은 다음과 같은 비선형 최소자승 문제로 정의할 수 있다:

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

여기서: - $\mathbf{x}$ 는 최적화해야 할 파라미터 벡터 - $r_i(\mathbf{x})$ 는 관찰값과 모델 예측값 간의 잔차(residual)이다.

Gauss-Newton 방법과 Levenberg-Marquardt의 차이점

Gauss-Newton 방법은 잔차 함수의 Jacobian을 사용하여 비선형 최소자승 문제를 해결한다. 그러나, Gauss-Newton 방법은 잔차가 비선형일 때 수렴이 어려울 수 있다. 이러한 문제를 해결하기 위해 Levenberg-Marquardt 방법은 다음과 같이 수정된 해를 제안한다:

$(\mathbf{J}^\top \mathbf{J} + \lambda \mathbf{I}) \Delta \mathbf{x} = -\mathbf{J}^\top \mathbf{r}$

여기서: - $\mathbf{J}$ 는 잔차 $r_i(\mathbf{x})$ 의 Jacobian 행렬 - $\lambda$ 는 가변적인 감쇠 계수(damping factor) - $\mathbf{I}$ 는 항등 행렬 - $\Delta \mathbf{x}$ 는 파라미터의 업데이트 값 - $\mathbf{r}$ 는 잔차 벡터

Levenberg-Marquardt 알고리즘은 $\lambda$ 를 조절하여 Gauss-Newton과 Gradient Descent 방법 사이에서 동적으로 전환한다. $\lambda$ 값이 작으면 Gauss-Newton 방법과 유사하게 동작하며, $\lambda$ 값이 크면 Gradient Descent와 유사하게 동작한다. 이를 통해 수렴이 느린 문제에서도 안정적인 수렴을 보장한다.

Jacobian 행렬 계산

Jacobian 행렬 $\mathbf{J}$ 는 잔차 함수 $r_i(\mathbf{x})$ 를 파라미터 벡터 $\mathbf{x}$ 에 대해 편미분한 값들로 구성된다. 즉, 각 잔차 $r_i$ 에 대한 파라미터들의 기울기로 이루어진 행렬이다. 이 Jacobian은 다음과 같이 정의된다:

$\mathbf{J} = \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}$

여기서: - $m$ 은 관찰된 데이터의 수 (즉, 잔차의 수) - $n$ 은 최적화할 파라미터의 수

업데이트 규칙

Levenberg-Marquardt 알고리즘은 다음과 같은 업데이트 규칙을 따른다:

초기 파라미터 $\mathbf{x}_0$ 와 감쇠 계수 $\lambda_0$ 를 설정한다.
현재 파라미터 $\mathbf{x}_k$ 에서 잔차 $\mathbf{r}(\mathbf{x}_k)$ 와 Jacobian $\mathbf{J}_k$ 를 계산한다.
$\Delta \mathbf{x}_k$ 를 다음 식을 통해 계산한다:

$(\mathbf{J}_k^\top \mathbf{J}_k + \lambda_k \mathbf{I}) \Delta \mathbf{x}_k = -\mathbf{J}_k^\top \mathbf{r}_k$

$\mathbf{x}_{k+1} = \mathbf{x}_k + \Delta \mathbf{x}_k$ 로 파라미터를 업데이트한다.
잔차의 크기에 따라 $\lambda$ 를 조정한다:
만약 잔차가 줄어들면 $\lambda$ 를 줄이고 Gauss-Newton 방법에 가깝게 만든다.
잔차가 줄어들지 않으면 $\lambda$ 를 늘려 Gradient Descent 방식에 가깝게 만든다.

감쇠 계수 $\lambda$ 의 조정

Levenberg-Marquardt 알고리즘의 핵심 요소 중 하나는 감쇠 계수 $\lambda$ 의 조정 방식이다. $\lambda$ 는 최적화 과정에서 중요한 역할을 하며, 문제의 비선형성에 따라 그 값이 동적으로 조정된다.

잔차가 줄어드는 경우:
$\mathbf{x}_{k+1}$ 에서의 잔차가 $\mathbf{x}_k$ 에서의 잔차보다 작아지면, 모델은 목표 함수의 최소값에 더 가까워졌다는 의미이다.
이 경우, Gauss-Newton 방법의 영향을 강화하기 위해 $\lambda$ 를 감소시킨다. $\lambda$ 가 0에 가까워질수록, 업데이트 식은 Gauss-Newton 방법과 비슷하게 작동한다.

$\lambda_{k+1} = \frac{\lambda_k}{\nu}, \quad \nu > 1$

잔차가 줄어들지 않는 경우:
$\mathbf{x}_{k+1}$ 에서 잔차가 줄어들지 않으면, Newton의 방법은 수렴하지 않을 가능성이 높다는 것을 의미한다.
이 경우, 더 안정적인 Gradient Descent 방법으로 전환하기 위해 $\lambda$ 를 증가시킨다. $\lambda$ 가 커질수록 항등 행렬의 영향이 커지며, 이는 Gradient Descent와 유사하게 작동한다.

$\lambda_{k+1} = \lambda_k \cdot \nu, \quad \nu > 1$

수렴 조건

Levenberg-Marquardt 알고리즘은 반복적인 갱신을 통해 최적화 문제를 해결하지만, 최적화가 완료되는 시점을 결정하는 수렴 조건이 필요하다. 일반적으로 다음과 같은 조건을 만족할 때 알고리즘은 종료된다:

목표 함수의 변화량이 매우 작을 때:
목표 함수의 변화량 $|\mathbf{r}(\mathbf{x}_k) - \mathbf{r}(\mathbf{x}_{k+1})|$ 이 사전에 정의된 임계값 $\epsilon$ 보다 작을 때.

$|\mathbf{r}(\mathbf{x}_k) - \mathbf{r}(\mathbf{x}_{k+1})| < \epsilon$

파라미터 벡터의 변화량이 매우 작을 때:
파라미터 벡터 $\mathbf{x}_k$ 와 $\mathbf{x}_{k+1}$ 간의 변화량이 매우 작으면, 파라미터가 거의 수렴한 것으로 간주한다.

$|\mathbf{x}_k - \mathbf{x}_{k+1}| < \epsilon$

최대 반복 횟수에 도달했을 때:
주어진 반복 횟수 $K_{max}$ 에 도달하면 알고리즘은 자동으로 종료된다. 이 방법은 수렴하지 않는 문제에서 무한 루프를 방지하는 역할을 한다.

Levenberg-Marquardt 알고리즘의 장점

Levenberg-Marquardt 알고리즘의 가장 큰 장점은 비선형 문제에 대한 빠른 수렴 속도와 안정성이다. 특히, 다음과 같은 점에서 유용하다:

빠른 수렴: 초기 근사값이 목표값에 충분히 가깝다면, Gauss-Newton 방법의 특성 덕분에 빠르게 수렴한다.
안정성: 초기 근사값이 목표값에서 멀어도 Gradient Descent 방식으로 전환하여 안정적인 수렴을 보장한다.
비선형성 처리: 비선형 문제에서의 잔차 함수의 특성을 잘 반영하여 보다 정확한 결과를 도출할 수 있다.