직교 매칭 추구

수치해석 통계 마지막 수정: 2026-08-06 05:05:19

1. 개요[편집]

직교 매칭 추구 Orthogonal Matching Pursuit
약칭	OMP
부류	탐욕(greedy) 희소 복원 알고리즘
기원	Pati–Rezaiifar–Krishnaprasad, Davis–Mallat–Zhang (1993~94)
반복 수	k-희소 신호에 정확히 k회
대표 보증	μ < 1/(2k−1)이면 정확 복원

직교 매칭 추구(OMP)는 과결정되지 않은 선형계 $y = Ax$ 에서 $x$ 가 희소하다는 가정 아래, 지지집합(0이 아닌 성분의 위치)을 한 번에 하나씩 탐욕적으로 골라 나가는 복원 알고리즘이다. 압축센싱의 두 축 중 볼록 완화( $\ell_1$ 최소화)가 아닌 탐욕 계열의 대표 주자다.

행렬 $A \in \mathbb{R}^{m\times n}$ 의 각 열 $a_j$ 를 원자(atom)라 부르고, 열은 전부 $\|a_j\|_2 = 1$ 로 정규화돼 있다고 하자. 한 반복은 세 동작이다.

선택 — 현재 잔차와 가장 잘 맞는 원자를 하나 고른다. $\; j^\star = \arg\max_j |\langle a_j, r^k\rangle|$
재투영 — 지금까지 고른 원자 전체 $S^{k+1} = S^k \cup \{j^\star\}$ 위에서 최소제곱을 다시 푼다. $\; x^{k+1} = \arg\min_{\mathrm{supp}(x)\subseteq S^{k+1}} \|y - Ax\|_2$
갱신 — $r^{k+1} = y - Ax^{k+1}$ .

핵심은 2번이다. 매 단계 전체 지지집합에 대해 최소제곱을 다시 푸는 것 — 그것이 이름의 “직교”이자, 이 알고리즘이 원조보다 나은 이유 전부다.¹

2. ”직교”가 뜻하는 것 — MP와의 차이[편집]

원조 매칭 추구(MP, Mallat–Zhang 1993)는 2번이 없다. 고른 원자 방향으로만 잔차를 깎는다.

r^{k+1} = r^k - \langle a_{j^\star}, r^k\rangle\, a_{j^\star}

이러면 새 잔차는 방금 고른 원자 하나에만 직교하고, 이전에 골랐던 원자들과는 다시 상관이 생긴다. 원자들이 비직교(과완비 사전이면 필연이다)이기 때문이다. 그 결과 MP는 같은 원자를 여러 번 고르며 계수를 조금씩 갉아 먹는다. 수렴은 하지만 반복 수가 지지집합 크기와 무관하게 늘어지고, 결과가 희소하다는 보장도 없다.

OMP의 최소제곱 재투영은 잔차를 $\mathrm{span}\{a_j : j \in S\}$ 의 직교 여공간으로 사영한다. 즉

r^{k+1} = (I - P_{S^{k+1}})\,y, \qquad P_S = A_S (A_S^\top A_S)^{-1} A_S^\top

이므로 $\langle a_j, r^{k+1}\rangle = 0$ 이 선택된 모든 $j$ 에 대해 성립한다. 이미 고른 원자는 상관이 정확히 0이니 다시 뽑힐 수 없다. 따라서 매 반복이 지지집합을 정확히 1개씩 키우고, $k$ -희소 신호는 정확히 $k$ 회 만에 끝난다. 잔차 노름도 단조 감소한다(부분공간이 커지니까). 이 두 성질이 OMP를 실무에서 쓸 만하게 만든다.

대가는 있다. 한 번 잘못 고른 원자는 영원히 지지집합에 남는다. OMP에는 되돌리기(backtracking)나 가지치기가 없어서, 초반에 미끄러지면 그 뒤 반복 전체가 오염된다. 뒤에 나오는 CoSaMP·부분공간 추구가 손대는 지점이 정확히 여기다.

3. 언제 정확히 복원되는가[편집]

보증은 대개 상호간섭성(mutual coherence)으로 서술한다. 열이 정규화됐을 때

\mu = \max_{i \ne j} |\langle a_i, a_j\rangle|

이며, $\mu$ 가 작다는 것은 원자들이 서로 최대한 안 닮았다는 뜻이다. 고전적 결과(Tropp 2004, “Greed is good”)는 이렇다 — $x$ 가 $k$ -희소이고

\mu < \frac{1}{2k-1}

이면 잡음 없는 경우 OMP가 $k$ 회 반복 만에 지지집합과 계수를 정확히 복원한다. 증명의 뼈대는 “매 단계에서 참 지지집합 안의 원자와의 상관이 바깥 원자와의 상관보다 항상 크다”는 부등식이며, 등가 조건인 정확 복원 조건(ERC) $\max_{j\notin S}\|A_S^{+} a_j\|_1 < 1$ 이 더 날카롭다.

이 조건은 계산이 쉽지만(열 그람 행렬 한 번) 매우 보수적이다. 웰치 경계 $\mu \ge \sqrt{(n-m)/(m(n-1))}$ 때문에 $\mu$ 는 아무리 잘 설계해도 대략 $1/\sqrt{m}$ 아래로 못 내려가고, 결국 간섭성 기반 보증은 $k \lesssim \sqrt{m}$ 정도의 희소도까지만 커버한다. 실제 성공 영역은 훨씬 넓다.

더 날카로운 쪽은 RIP 기반 조건이다. $A$ 가 차수 $k+1$ 의 제한등거리상수 $\delta_{k+1}$ 을 가질 때, 초기에는 $\delta_{k+1} < 1/(3\sqrt{k})$ 면 충분하다는 결과가 나왔고 이후 $\delta_{k+1} < 1/(\sqrt{k}+1)$ 까지 개선됐다(그리고 이 값은 더 못 밀어붙인다는 의미에서 날카롭다). 랜덤 가우시안 행렬이라면 $m \gtrsim k\log n$ 측정이면 높은 확률로 성공한다.

잡음이 있으면 이야기가 조금 바뀐다. 정지 조건을 반복 수 $k$ 가 아니라 잔차 문턱 $\|r^k\|_2 \le \varepsilon$ 으로 바꾸고, 신호의 최소 비영 성분 크기가 잡음 대비 충분히 커야 지지집합이 맞는다. 작은 성분은 잡음에 묻혀 순서가 뒤바뀌고, 앞서 말했듯 OMP는 그걸 되돌리지 못한다.

4. ℓ₁ 최소화와의 비교[편집]

같은 희소 복원 문제를 OMP와 기저 추구( $\min\|x\|_1$ s.t. $Ax=y$ ) 두 진영이 각각 공략한다. 정직하게 비교하면 이렇다.

항목	OMP (탐욕)	ℓ1 최소화 (기저 추구)
이론 보증	조건이 더 빡셈, 균일 보증 약함	더 넓은 영역, 날카로운 위상 전이
계산량	k회 반복, 반복당 O(mn)	LP/QP 또는 1차법 수백~수천 반복
출력	지지집합을 명시적으로 줌	계수 벡터(임계화가 따로 필요)
편향	지지집합 위 최소제곱이라 축소 편향 없음	λ만큼 축소 편향
튜닝	k 또는 잔차 문턱	λ (연속값)

요약하면 이론은 $\ell_1$ , 속도는 OMP다. 총비용이 $O(kmn)$ 이라 $k$ 가 정말 작으면 압도적으로 싸고, 구현이 스무 줄이며, 지지집합을 바로 돌려주니 이후에 그 위에서 통계 추론을 하기도 좋다. 반면 $k$ 가 커지거나 원자들이 서로 닮았을수록 탐욕 선택이 흔들려 성능이 급격히 무너진다. 실무 감각은 “매우 희소하면 OMP, 애매하게 희소하면 근접 경사법류로 $\ell_1$ “이다.

한 가지 더. OMP의 계수는 지지집합 위 최소자승법 해라서 축소 편향이 없다. LASSO 해는 $\lambda$ 만큼 원점으로 당겨져 있어 크기를 그대로 믿으면 안 되고, 그래서 실무에서는 LASSO로 지지집합만 고르고 그 위에서 다시 최소제곱을 푸는 “디바이어싱”을 한다 — 그 두 번째 단계가 사실 OMP가 매 반복 하는 일과 같다.

5. 구현 — 증분 QR[편집]

순진하게 짜면 매 반복마다 $|S| \times |S|$ 정규방정식을 처음부터 다시 푼다. 그러면 총비용에 $O(k^4)$ 항이 붙고, 정규방정식은 조건수를 제곱하므로 수치적으로도 나쁘다. 제대로 된 구현은 QR 분해를 증분으로 갱신한다.

$A_S = Q_S R_S$ 를 들고 있다가 새 열 $a_{j^\star}$ 가 들어오면, 기존 $Q_S$ 에 대해 그람-슈미트(수치적으로는 재직교화 1회를 덧붙인 MGS)나 기븐스 회전으로 한 열만 직교화해 붙인다. 비용은 반복당 $O(m|S|)$ 이고, 최소제곱 해는 삼각계 후진 대입 $O(|S|^2)$ 로 끝난다. 콜레스키 기반이면 $A_S^\top A_S$ 의 촐레스키 분해 인수에 행 하나를 얹는 rank-1 갱신을 쓴다 — 더 싸지만 조건수 제곱을 감수해야 한다.

또 하나의 요령은 잔차 갱신을 이용한 상관 계산이다. $A^\top r$ 을 매번 처음부터 계산하지 않고, 새로 추가된 직교 방향 $q$ 에 대해 $A^\top r^{k+1} = A^\top r^k - (q^\top r^k)\,A^\top q$ 로 내린다. $A$ 가 명시 행렬이 아니라 고속 푸리에 변환 같은 연산자로만 주어지는 대규모 문제에서는 이런 형태가 사실상 유일한 선택지다.

6. 변형과 응용[편집]

StOMP(단계적 OMP). 매 단계에서 문턱을 넘는 원자를 여러 개 한꺼번에 고른다. 반복 수가 $k$ 회에서 수 회로 줄어든다.
ROMP(정규화 OMP). 크기가 비슷한 상관들만 묶어 고르는 규칙을 넣어 균일 RIP 보증을 얻는다.
CoSaMP / 부분공간 추구. 후보를 넉넉히 잡았다가 크기 하위 성분을 잘라내는 가지치기를 넣는다. 덕분에 초반 오선택을 되돌릴 수 있고, RIP 기반으로 $\ell_1$ 에 필적하는 균일 보증과 최적 차수의 계산량을 동시에 얻는다. 사실상 현대적 탐욕법의 표준.
가중·블록 변형. 지지집합이 그룹으로 뭉쳐 있다는 사전 지식이 있으면 원자 대신 블록 단위로 고른다.

응용에서 OMP가 가장 많이 도는 곳은 딕셔너리 학습의 희소 코딩 단계다. K-SVD는 딕셔너리 갱신과 희소 코딩을 번갈아 도는데, 후자는 수만 개 신호 각각에 대해 ” $T_0$ 개 원자로 근사”를 푸는 문제라 신호 하나당 정확히 $T_0$ 회면 끝나는 OMP의 성질이 결정적이다(반복 수가 예측 가능해야 전체 학습 시간이 예측 가능하다). 그 밖에 레이더의 성긴 산란점 추정, 채널 추정, 스펙트럼 감지, 축소차수모델의 경험적 보간(DEIM에서 인덱스를 탐욕적으로 고르는 절차가 구조적으로 같다) 등에서 쓴다.² 마지막으로 짚어 둘 것 — 원래 문제 $\min\|x\|_0$ 는 NP-난해이고, OMP는 그것을 푸는 알고리즘이 아니라 조건이 좋을 때만 같은 답을 내는 휴리스틱이다. 조건이 나빠지면 조용히 틀린 지지집합을 자신 있게 돌려준다.³

7. 관련 문서[편집]

그래서 이 알고리즘을 처음 구현할 때 가장 흔한 버그가 “재투영을 빼먹고 MP를 짜 놓고 OMP라고 부르는 것”이다. 증상도 명확하다 — 반복 수가 $k$ 를 훌쩍 넘고, 지지집합 크기가 반복 수보다 작으며, 같은 인덱스가 로그에 계속 찍힌다. 이 세 가지가 보이면 그건 OMP가 아니다. ↩
이 계열의 알고리즘이 서로 다른 분야에서 독립적으로 재발명된 횟수는 세기 어려울 정도다. 통계의 전진 선택(forward selection), 신호처리의 매칭 추구, 수치선형대수의 열 피벗 QR, 모델 축소의 DEIM/Q-DEIM이 전부 “잔차와 가장 잘 맞는 열을 하나씩 고르고 재투영한다”는 같은 문장이다. 이름이 넷인 이유는 학회가 넷이기 때문. ↩
OMP에는 “나 실패했어요” 신호가 없다는 게 진짜 함정이다. 잔차는 반복마다 얌전히 줄어들고 최종 잔차도 작을 수 있는데 지지집합만 틀려 있는 경우가 있다. 지지집합의 물리적 의미(고장 위치, 산란점 좌표)가 중요한 응용에서는 잔차만 보고 안심하면 안 되고, 서로 다른 $k$ 나 다른 알고리즘으로 교차 확인하는 게 국룰이다. ↩