슈어 보완 / 희소성

번들 조정은 처음 보면 다루기 힘들어 보입니다: $m$개의 키프레임과 $n$개의 점을 가진 소박한 지도조차 $6m + 3n$개의 미지수를 가지며, $n$은 쉽게 수십만에 이릅니다. 이를 실용적으로 만드는 것은 이 문제가 희소(sparse) 하다는 사실이며, 슈어 보완(Schur complement) 은 이 희소성을 활용하는 트릭입니다.

희소성이 나오는 곳. 각 재투영 오차 항은 정확히 하나의 자세와 하나의 점만을 포함합니다. 따라서 $H = J^T J$인 가우스-뉴턴 정규 방정식 $H \Delta\mathbf{x} = -\mathbf{b}$에서, 헤시안은 화살표 모양의 블록 구조를 가집니다.

$$H = \begin{bmatrix} B & E \\ E^T & C \end{bmatrix}$$

여기서 $B$ ($6m \times 6m$)는 자세들만을 결합하고, $C$ ($3n \times 3n$)는 점들만을 결합하며, $E$는 자세-점 결합을 담습니다. 결정적으로, 두 점이 동일한 잔차에 함께 나타나는 일은 없으므로 $C$는 블록 대각(block-diagonal) 입니다 — 점마다 독립적인 하나의 $3 \times 3$ 블록입니다.

슈어 보완 단계(점들을 마지널라이즈한다고도 불립니다)는 선형계에서 점 변수를 제거하여 축소된 카메라 시스템을 남깁니다:

$$\left(B - E C^{-1} E^T\right) \Delta\mathbf{x}_{\text{cam}} = -\mathbf{b}_{\text{cam}} + E C^{-1} \mathbf{b}_{\text{pts}}$$

$C$가 블록 대각이므로, $C^{-1}$은 거의 비용이 들지 않습니다(각 $3 \times 3$ 블록을 역행렬 계산). $6m \times 6m$ 축소 시스템을 풀어 자세 업데이트를 얻은 다음, 역대입을 통해 각 점의 업데이트를 독립적으로 복원합니다. $(6m + 3n)$차원의 풀이가 $6m$차원의 풀이가 되는 것입니다 — $n \gg m$일 때(항상 그렇습니다) 몇 자릿수 더 빠릅니다.

실제로는 두 가지 희소성 층이 더 중요하게 작용합니다. 첫째, 축소된 카메라 행렬 $B - EC^{-1}E^T$ 자체도 희소합니다: 항목 $(i, j)$는 키프레임 $i$와 $j$가 공통의 점을 관측할 때만(공동 가시성 구조) 0이 아니므로, 좋은 변수 순서(COLAMD)를 가진 희소 콜레스키 분해가 적용됩니다. 둘째, 동일한 소거 관점이 일반화됩니다: 팩터 그래프의 관점에서 슈어 보완은 단순히 변수 소거이며, 이는 슬라이딩 윈도우 VIO와 iSAM2 같은 증분 스무더의 마지널화 이면에 있는 연산입니다.

이 공식이 나오는 곳

슈어 보완은 블록 가우스 소거법 이상의 특별한 것이 아닙니다. 정규 방정식의 두 블록 행을 풀어서 써 보면:

$$B\,\Delta\mathbf{x}_{\text{cam}} + E\,\Delta\mathbf{x}_{\text{pts}} = -\mathbf{b}_{\text{cam}}$$ $$E^T \Delta\mathbf{x}_{\text{cam}} + C\,\Delta\mathbf{x}_{\text{pts}} = -\mathbf{b}_{\text{pts}}$$

두 번째 행을 점 업데이트에 대해 풀면 $\Delta\mathbf{x}_{\text{pts}} = -C^{-1}\left(\mathbf{b}_{\text{pts}} + E^T \Delta\mathbf{x}_{\text{cam}}\right)$이 되고, 이를 첫 번째 행에 대입하면 — 위의 축소된 카메라 시스템이 곧바로 나타나며, $\Delta\mathbf{x}_{\text{cam}}$을 알고 나면 동일한 표현식이 곧 역대입 규칙입니다. 통계적으로, 축소된 시스템은 카메라들에 대한 마지널 분포의 정보 행렬 형태입니다: 점들을 소거하는 것은 아무것도 근사하지 않으며, 동일한 가우시안을 정확히 재표현하는 것입니다.

이득을 계산해 보면. 전체 시스템의 밀집 풀이는 $O((6m + 3n)^3)$의 비용이 듭니다. 슈어 트릭을 사용하면: $C$의 역행렬 계산은 $n$개의 독립적인 $3\times 3$ 역행렬 계산($O(n)$)이고, 축소된 시스템을 구성하는 것은 관측 개수로 한정되며, 남은 풀이는 최악의 경우 $O((6m)^3)$입니다 — 공동 가시성 희소성 덕분에 보통 이보다 훨씬 적습니다. $m$이 수백, $n$이 수십만에 이를 때, 점 소거는 밀리초와 분(minute)의 차이를 만듭니다. $m$ 자체가 커지면(도시 규모 SfM), 축소된 시스템조차 분해하기에 저렴하지 않게 되고, 솔버는 반복적 방법(슈어 보완에 대한 전처리된 켤레기울기법 — Ceres의 ITERATIVE_SCHUR)으로 전환합니다.

Ceres에서는 이 모든 것이 하나의 설정 선택입니다:

ceres::Solver::Options options;
options.linear_solver_type = ceres::SPARSE_SCHUR;  // or DENSE_SCHUR, ITERATIVE_SCHUR

솔버는 자세/점 소거 순서를 자동으로 감지합니다(또는 명시적인 ParameterBlockOrdering을 받을 수 있습니다). Ceres, g2o, GTSAM 등 모든 진지한 솔버가 동일한 트릭을 구현합니다. 이를 알면 왜 BA가 확장 가능한지, 왜 오래된 상태를 마지널화하면 남은 헤시안에 필-인(fill-in, 밀집 블록)이 생기는지, 그리고 왜 솔버 선택과 순서 지정이 실행 시간을 몇 자릿수나 바꿀 수 있는지를 설명할 수 있습니다.

흔한 함정

• 잘못된 순서로 소거하기 — 이 트릭은 점들이 많고, 저렴하며, 상호 독립적이기 때문에 동작합니다. 자세를 먼저 소거하면 그 모든 점들이 서로 결합되어 시스템이 밀집화됩니다. 소거 순서는 성능의 정확성을 좌우하는 결정입니다.
• 마지널화와 삭제의 혼동 — 오래된 상태를 버리는 것과 마지널화하는 것은 다릅니다: 마지널화는 그 정보를 인접 상태에 대한 밀집 사전 분포로 유지합니다(필-인). 이 밀집성 때문에 슬라이딩 윈도우 VIO 시스템은 마지널화할 것과 버릴 것을 신중하게 선택합니다.
• 게이지 자유도 — 완전 BA는 단안의 경우 관측 불가능한 7개의 자유도(6 + 스케일)를 가집니다. 자세 하나를 고정(또는 사전 분포를 추가)하지 않으면, 축소된 카메라 행렬은 특이 행렬이 되고 솔버는 절뚝거리거나 실패합니다.
• 먼 점으로 인한 조건 불량 — 거의 무한대의 깊이에 있는 점들은 그 $3\times3$ 블록을 거의 특이 행렬로 만듭니다. 역깊이 파라미터화 또는 깊이 사전 분포는 $C^{-1}$을 잘 작동하게 유지합니다.

SLAM에서의 의미

실시간 SLAM은 구조를 활용하는 선형대수 덕분에 존재합니다: 슈어 보완이 없다면 단 몇백 개의 키프레임에 대한 번들 조정조차 절망적일 것입니다. 동일한 아이디어 — 변수를 소거하되 문제를 희소하게 유지한다 — 는 마지널화, 슬라이딩 윈도우 추정기, 증분 스무딩에서 다시 등장하므로, 이는 전체 로드맵에서 가장 활용도가 높은 수학 중 하나입니다.

관련 문서

• MAP inference as sparse nonlinear least squares
• Pose graph optimization
• Marginalization
• Math libraries