직교 프로크루스테스 문제

1. 개요[편집]

직교 프로크루스테스 문제 Orthogonal Procrustes Problem
문제	$\min_{\Omega^{\mathsf T}\Omega = I}\ \lVert A\Omega - B\rVert_F$
해	$\Omega = UV^{\mathsf T}$, 단 $A^{\mathsf T}B = U\Sigma V^{\mathsf T}$
도구	특이값 분해 한 번, $O(mp^2 + p^3)$
회전만 원하면	$\Omega = U\,\mathrm{diag}(1,\dots,1,\det(UV^{\mathsf T}))\,V^{\mathsf T}$
출처	Green 1952(정칙 경우) · Schönemann 1966(일반) · Kabsch 1976
단골 무대	RMSD, 점군 정합, 형상 통계, 단어 임베딩 정렬

손님이 침대에 안 맞으면 손님을 늘이거나 자른다. 여기서는 침대(정답 $B$)에 맞게 손님($A$)을 돌리기만 한다.

직교 프로크루스테스 문제는 주어진 두 행렬 $A, B \in \mathbb R^{m\times p}$ 에 대해 $A\Omega$ 를 $B$ 에 가장 가깝게 만드는 직교행렬 $\Omega$ 를 찾는 최소제곱 문제다.

$$\min_{\Omega \in \mathbb R^{p\times p},\ \Omega^{\mathsf T}\Omega = I_p} \ \bigl\|A\Omega - B\bigr\|_F$$

이름은 그리스 신화의 강도 프로크루스테스에서 왔다.¹ 인자분석에서 회전된 인자구조를 목표 구조에 맞추는 절차를 부르던 말이 통계 밖으로 퍼져 나갔고, 지금은 “두 점 집합을 최적으로 겹치는 문제” 전반을 가리킨다.

이 문제가 유명한 이유는 직교 제약이 걸린 최적화인데 닫힌 해가 있기 때문이다. 스티펠 다양체 위의 최적화는 대개 반복법이 필요한데 이 경우만 특이값 분해 한 번으로 끝난다. 그린(1952)이 $A^{\mathsf T}B$ 가 정칙일 때를 풀었고, 쇤네만(1966)이 특이한 경우까지 포함한 일반해를 냈다.

2. 닫힌 해와 유도[편집]

핵심은 목적함수에서 $\Omega$ 에 의존하는 항이 트레이스 하나뿐이라는 것이다.

$$\|A\Omega - B\|_F^2 = \mathrm{tr}(\Omega^{\mathsf T}A^{\mathsf T}A\Omega) - 2\,\mathrm{tr}(\Omega^{\mathsf T}A^{\mathsf T}B) + \|B\|_F^2$$

$\Omega$ 가 정방 직교행렬이면 $\Omega\Omega^{\mathsf T} = I$ 이므로 첫 항이 $\mathrm{tr}(A^{\mathsf T}A\Omega\Omega^{\mathsf T}) = \|A\|_F^2$ 로 상수가 된다. 따라서 문제는 트레이스 최대화로 환원된다.

$$\max_{\Omega^{\mathsf T}\Omega = I}\ \mathrm{tr}(\Omega^{\mathsf T}M), \qquad M := A^{\mathsf T}B$$

$M = U\Sigma V^{\mathsf T}$ 로 특이값 분해하고 $Z := V^{\mathsf T}\Omega^{\mathsf T}U$ 라 두면 $Z$ 는 직교행렬이고

$$\mathrm{tr}(\Omega^{\mathsf T}U\Sigma V^{\mathsf T}) = \mathrm{tr}(Z\Sigma) = \sum_i z_{ii}\sigma_i \ \le\ \sum_i \sigma_i$$

직교행렬의 성분은 절댓값이 1을 넘을 수 없으므로($|z_{ii}|\le1$) 상한이 $\sum_i\sigma_i$, 즉 $M$ 의 핵노름이고, 등호는 $Z = I$ 일 때 성립한다. 거기서 $\Omega$ 를 풀면

$$\boxed{\ \Omega^\star = UV^{\mathsf T}\ },\qquad A^{\mathsf T}B = U\Sigma V^{\mathsf T}$$

$\Sigma$ 가 특이해도(즉 $\sigma_i = 0$ 이 있어도) 이 $\Omega^\star$ 는 여전히 최적이며, 다만 유일하지 않을 수 있다. $\sigma_i > 0$ 이 모든 $i$ 에 대해 성립하면 해가 유일하다.

일반적인 상계로는 폰 노이만의 트레이스 부등식 $\mathrm{tr}(X^{\mathsf T}Y) \le \sum_i\sigma_i(X)\sigma_i(Y)$ 를 쓸 수도 있지만, 여기서는 $\Omega$ 의 특이값이 전부 1이라 위의 세 줄짜리 논증으로 충분하다.

부호와 전치 방향은 매번 틀리는 곳이다. $M = A^{\mathsf T}B$ 냐 $B^{\mathsf T}A$ 냐, $UV^{\mathsf T}$ 냐 $VU^{\mathsf T}$ 냐를 헷갈리면 정확히 전치된 답이 나오고, 대칭적인 테스트 데이터에서는 그게 통과해 버린다. 문헌마다 $A\Omega \approx B$ 냐 $\Omega A \approx B$ 냐가 다르니 공식을 외우지 말고 매번 검산하라. 검산은 한 줄이면 된다 — $\|A\Omega - B\|_F$ 와 $\|A\Omega^{\mathsf T} - B\|_F$ 를 둘 다 계산해 작은 쪽을 취하고, 큰 쪽이 나왔으면 유도를 다시 본다.²

3. 극분해와 같은 물건이다[편집]

$M = A^{\mathsf T}B$ 의 극분해를 $M = \Omega P$ 라 쓰면 $\Omega = UV^{\mathsf T}$ 로 위 답과 정확히 일치한다. 즉 직교 프로크루스테스의 해는 $A^{\mathsf T}B$ 에 가장 가까운 직교행렬이며, 두 문제는 같은 정리의 두 얼굴이다. 최적성이 프로베니우스 노름뿐 아니라 임의의 유니터리 불변 노름에서 성립한다는 팬-호프만 정리도 그대로 물려받는다. 계산 쪽 이야기(뉴턴 반복, QDWH, SVD 없이 $\Omega$ 만 구하기)는 극분해 문서가 다룬다.

4. 회전만 허용할 때 — 카브슈 보정[편집]

여기가 실무에서 가장 자주 사고가 나는 지점이다. 위의 최적화는 직교군 $O(p)$ 전체 위에서 이루어졌으므로 답에 반사가 섞일 수 있다. $\det\Omega^\star = -1$ 이면 그건 거울상 변환이다. 그런데 물리적 응용에서 원하는 것은 거의 언제나 회전, 즉 $SO(p)$ 위의 해다.

$$\Omega^\star_{SO} = U\,D\,V^{\mathsf T}, \qquad D = \mathrm{diag}\bigl(1,\dots,1,\ \det(UV^{\mathsf T})\bigr)$$

마지막 자리만 뒤집는 이유는 그렇게 해야 $\mathrm{tr}(D\Sigma) = \sigma_1 + \cdots + \sigma_{p-1} - \sigma_p$ 로 손실이 가장 작은 특이값 하나에만 국한되기 때문이다. $\det(\Omega_{SO}) = \det(U)\det(V)\det(UV^{\mathsf T}) = \det(UV^{\mathsf T})^2 = +1$ 로 회전이 보장된다.

이 보정이 붙은 것이 카브슈 알고리즘(Kabsch 1976, 1978년 정오표)이고, 구조생물학 코드에서 “마지막 열에 $\det$ 를 곱하는 한 줄”의 정체다. 이 한 줄을 빼먹으면 분자를 거울상과 정렬한다. 잡음이 큰 데이터나 거의 평면인 구조에서 $\sigma_p$ 가 0 근처면 $\det$ 부호가 실행마다 뒤집혀서, RMSD 가 어떤 프레임에서는 0.5 Å 이고 어떤 프레임에서는 3 Å 인 유명한 증상이 나온다. 궤적 후처리에서 갑자기 튀는 RMSD 를 보면 이걸 먼저 의심한다.³

$\sigma_{p-1} = \sigma_p$ 로 축퇴한 경우에는 회전해 자체가 유일하지 않다. 완전한 구형 대칭 배치나 직선 위에 놓인 세 점 같은 병적인 입력이 그렇고, 이때는 답을 고르는 규칙을 따로 정해야 한다.

5. RMSD — 정합의 실제 목적[편집]

분자동역학에서 두 구조의 유사도는 RMSD(root-mean-square deviation)로 잰다. 원자 좌표를 $N\times3$ 행렬 $A, B$ 로 쌓고 각자의 무게중심으로 평행이동한 뒤 최적 회전을 씌우면

$$\mathrm{RMSD} = \sqrt{\frac{\|A\|_F^2 + \|B\|_F^2 - 2(\sigma_1 + \sigma_2 + d\,\sigma_3)}{N}}, \qquad d = \det(UV^{\mathsf T})$$

로 회전행렬을 명시적으로 만들지 않고도 값이 나온다. 순서가 중요하다 — 평행이동 제거가 먼저고 회전이 나중이다. 무게중심을 안 맞춘 채 회전만 최적화하면 전혀 다른 답이 나온다.

이 공식에는 수치적 함정이 하나 더 있다. 잘 겹치는 두 구조에서는 분자가 큰 두 수의 차라 상쇄오차가 나서, RMSD 가 0.01 Å 수준일 때 유효숫자가 몇 자리씩 날아간다. 쿠치아스·석·딜(2004)의 사원수 기반 정식화와 시어볼드(2005)의 QCP(quaternion characteristic polynomial) 방법이 이 문제를 피하면서 SVD 보다 빠르기까지 해서, 요즘 MD 분석 라이브러리의 기본값이 됐다. 수백만 프레임의 궤적에 프레임마다 SVD를 돌리는 것은 생각보다 비싼 일이다.

같은 계산이 점군 정합의 ICP 알고리즘 안쪽에도 그대로 들어 있다. ICP 는 “대응점 찾기 → 프로크루스테스로 정합 → 반복”이고, 두 번째 단계가 정확히 이 문제다. 로봇 SLAM, 3D 스캔 병합, 크라이오전자현미경 입자 정렬이 전부 같은 커널을 부른다.

6. 확장[편집]

평행이동·스케일 포함. $\min\|sA\Omega + \mathbf 1 t^{\mathsf T} - B\|_F$ 형태는 순서대로 풀린다. 먼저 각 행렬을 무게중심으로 중심화하면 $t$ 가 분리되고, 중심화된 문제에서 $\Omega$ 를 위 공식으로 구한 뒤, 스케일은

$$s^\star = \frac{\mathrm{tr}(\Sigma)}{\|A\|_F^2} = \frac{\sum_i\sigma_i}{\|A\|_F^2}$$

로 닫힌 형태로 나온다. 이 세 단계 묶음이 완전 프로크루스테스 정합(full Procrustes superimposition)이고, 형상 통계의 기본 전처리다.

직사각 $\Omega$ 는 닫힌 해가 없다. 흔한 오해라 못 박아 둔다. $\Omega \in \mathbb R^{p\times q}$, $\Omega^{\mathsf T}\Omega = I_q$, $q < p$ 인 “불균형 프로크루스테스 문제”에서는 $\Omega\Omega^{\mathsf T} \ne I$ 이므로 $\mathrm{tr}(\Omega^{\mathsf T}A^{\mathsf T}A\Omega)$ 가 상수가 아니다. 유도의 첫 단추가 빠지므로 $UV^{\mathsf T}$ 공식이 성립하지 않고, 실제로 이 문제는 진짜 스티펠 다양체 최적화라 반복법이 필요하다(엘덴·박 1999). 반면 순수한 트레이스 최대화 $\max_{\Omega\in\mathrm{St}(p,q)}\mathrm{tr}(\Omega^{\mathsf T}M)$ 은 직사각에서도 얇은 SVD의 $UV^{\mathsf T}$ 가 답이다. 두 문제를 구분하지 못하면 틀린 코드가 조용히 그럴듯한 값을 뱉는다.

가중 프로크루스테스. 점마다 신뢰도가 다르면 $\min\|W^{1/2}(A\Omega - B)\|_F$ 를 풀고, 이는 $M = A^{\mathsf T}WB$ 로 바꾸는 것만으로 처리된다. 원자 질량으로 가중한 RMSD 가 이 경우다.

일반화 프로크루스테스 분석(GPA). 형상이 둘이 아니라 $K$ 개일 때, 기준을 하나 정하지 않고 모두를 동시에 정렬한다(Gower 1975). 알고리즘은 교대법이다.

1. 현재 평균 형상에 모든 형상을 프로크루스테스 정합한다.
2. 정합된 형상들의 평균을 다시 계산한다.
3. 수렴할 때까지 반복.

목적함수가 모든 쌍의 거리 제곱합이라 단조 감소가 보장된다. 눈치챘겠지만 이건 프레셰 평균을 구하는 반복이다 — 켄들 형상공간에서 프로크루스테스 거리에 대한 프레셰 평균이 정확히 GPA 의 극한이고, 그래서 이 절차의 수렴·유일성 이론이 다양체 위의 평균 이론과 같은 것을 쓴다.

7. 다른 무대들[편집]

• 회전 평균. 여러 회전행렬 $R_i$ 의 코달 평균은 $\frac1N\sum_i R_i$ 를 $SO(3)$ 로 사영한 것, 즉 프로크루스테스 한 번이다. 회전행렬·사원수·프레셰 평균 문서 참조.
• 단어 임베딩 정렬. 서로 다른 언어(또는 서로 다른 학습 실행)의 임베딩 공간을 겹치는 문제. 초기에는 자유로운 선형사상을 학습했는데, 직교로 제약하면 코사인 유사도가 보존되고 과적합이 줄어 성능이 오른다는 것이 밝혀지면서 프로크루스테스가 표준이 됐다. 사전 몇 천 쌍만 있으면 SVD 한 번으로 두 언어를 정렬할 수 있다는 결과가 다국어 워드 임베딩 연구의 기본 베이스라인이다.
• 인자분석·심리측정. 원산지. 추출된 인자행렬을 해석 가능한 목표 구조에 맞춰 회전시키는 절차였고, 문제 이름도 여기서 나왔다.
• fMRI 하이퍼얼라인먼트. 피험자마다 다른 복셀 공간의 반응 패턴을 공통 공간으로 회전시켜 맞춘다. 해부학적 정렬이 아니라 기능적 정렬이라는 발상이고, 수학은 GPA 그대로다.

8. 실무 체크리스트[편집]

• 중심화 먼저, 회전 나중. 순서를 바꾸면 답이 다르다.
• $\det$ 보정 잊지 말 것. 회전을 원하면 필수. 반사가 허용되는 문제(순수 인자 회전 등)에서는 넣으면 안 된다 — 무엇을 원하는지부터 정하라.
• 전치 방향은 검산으로. 대칭 테스트 데이터는 전치 버그를 못 잡는다. 일부러 비대칭인 입력으로 단위 테스트를 짠다.
• $\sigma_p \approx 0$ 이면 경고를 띄운다. 축퇴 근처에서는 답이 불안정하고 $\det$ 부호가 튄다.
• 대량 반복이면 QCP 를 고려한다. RMSD 값만 필요하고 회전행렬은 안 쓸 때 특히 이득이 크다.
• 스케일을 넣을지 말지는 물리가 정한다. 분자 정합에서는 보통 넣지 않고(결합 길이는 물리량이다), 형상 통계에서는 거의 항상 넣는다.

9. 관련 문서[편집]

• 특이값 분해 · 극분해 · 행렬 제곱근 · 최소자승법
• 스티펠 다양체 · 그라스만 다양체 · 프레셰 평균 · 리만 다양체
• 회전행렬 · 사원수 · 리 군
• 분자동역학 · GROMACS · 연속체역학
• 점군 정합 · RMSD · 워드 임베딩

10. Footnotes[편집]

1. 아테네 근처에서 여관을 하며 손님을 쇠침대에 눕히고, 짧으면 잡아 늘이고 길면 잘라 냈다는 그 인물. 테세우스에게 같은 방식으로 당한다. 통계학자들이 “데이터를 미리 정한 구조에 억지로 맞춘다”는 자조를 담아 붙인 이름인데, 정작 이 문제의 직교판은 억지가 전혀 없는 정직한 최소제곱이라 이름값을 못 한다. ↩

2. 이 검산 습관은 생각보다 값어치가 크다. 프로크루스테스는 최적성이 보장된 문제라 “값이 그럴듯하니 맞겠지”가 안 통한다 — 전치된 답도 대부분의 데이터에서 그럴듯한 값을 준다. 리뷰 때 “여기 전치 맞아요?”라고 물으면 열에 셋은 다시 확인하러 간다. ↩

3. 이 버그의 수명이 길다. 카브슈의 1976년 원논문 자체가 이 보정을 명시하지 않아 1978년 정오표가 따로 나왔고, 그 뒤로도 40년 넘게 새로 짜인 코드에서 재발하고 있다. “거울상 단백질”은 이 바닥의 국룰 밈이 됐다. ↩