CoSaMP

1. 개요[편집]

CoSaMP Compressive Sampling Matching Pursuit
제안	Deanna Needell, Joel A. Tropp (2009)
부류	탐욕 + 가지치기 희소 복원
한 반복	프록시 → 2k 선택 → 3k 병합 → 최소제곱 → k 절단
보증	RIP 기반 균일 복원, 반복당 오차 반감
필요 정보	희소도 k 를 미리 알아야 함

CoSaMP(Compressive Sampling Matching Pursuit)는 압축센싱의 희소 복원 문제 $y = Ax + e$ 를 푸는 탐욕 알고리즘으로, 매 반복마다 후보 지지집합을 넉넉히 늘렸다가 다시 잘라내는 가지치기를 도입해 직교 매칭 추구(OMP)의 고질적 약점인 “한 번 잘못 고르면 끝”을 해결한 방법이다. 니델과 트로프가 2009년 Applied and Computational Harmonic Analysis 에 발표했다.

이 알고리즘이 중요한 위치를 차지하는 이유는, 탐욕 계열에서 처음으로 $\ell_1$ 최소화급의 균일 보증과 사실상 최적인 계산량을 동시에 달성했기 때문이다. 그전까지 이 바닥의 구도는 “보증이 강한 기저 추구 vs 빠른 OMP”라는 양자택일이었다. CoSaMP는 그 사이를 끊었다 — 제한등척성(RIP) 조건 아래 모든 희소 신호에 대해 동작하고, 잡음과 비희소성에 대해 안정적이며, 반복 수가 $\log$ 로 끝난다.

2. 한 반복이 하는 일[편집]

$k$-희소 신호를 찾는다고 하자. 현재 추정 $x^{j}$ 와 잔차 $r = y - Ax^{j}$ 를 들고 시작한다. 한 반복은 다섯 동작이다.

1. 프록시(proxy) — $p = A^\top r$. RIP 아래에서 $A^\top A \approx I$ 이므로 $p$ 는 잔차 신호의 대략적인 복사본 노릇을 한다. 큰 성분의 위치가 곧 놓친 지지집합의 후보다.
2. 선택 — $\Omega = \operatorname{supp}(p_{2k})$, 즉 $p$ 에서 크기 상위 $2k$ 개 인덱스. OMP가 1개를 고르는 자리에서 $2k$ 개를 한꺼번에 집는다.
3. 병합 — $T = \Omega \cup \operatorname{supp}(x^{j})$. 크기가 최대 $3k$ 인 후보 집합이 만들어진다.
4. 최소제곱 — $b|_T = A_T^{+}\,y$, $b|_{T^c} = 0$. 후보 집합 위에서만 최소자승법을 푼다.
5. 절단(prune) — $x^{j+1} = b_k$, 즉 $b$ 에서 크기 상위 $k$ 개만 남기고 나머지는 0으로. 그리고 $r \leftarrow y - Ax^{j+1}$.

핵심은 5번이다. 이 한 줄 때문에 지난 반복에서 잘못 넣은 인덱스가 다음 반복에서 크기가 작다는 이유로 조용히 쫓겨날 수 있다. OMP에는 없는 되돌리기 경로이며, 그래서 CoSaMP는 반복 수가 $k$ 로 고정되지 않고 지지집합이 커졌다 작아졌다 하며 정답을 찾아간다.

$2k$ 와 $3k$ 라는 숫자에도 이유가 있다. $2k$ 를 고르는 것은 “참 지지집합에서 놓친 부분($\le k$)과 현재 추정의 오류($\le k$)를 한 번에 덮기 위해”이고, 병합 후 $3k$ 인 것은 최소제곱을 푸는 부분행렬 $A_T$ 가 잘 조건화돼야 하기 때문이다. 여기서 RIP 차수 $4k$ 가 요구되는 구조가 나온다 — 크기 $3k$ 인 $T$ 와 크기 $k$ 인 참 지지집합을 합친 최대 $4k$ 개 열 위에서 $A$ 가 거의 등거리여야 논증이 굴러간다.

3. 보증 — 오차가 매 반복 반으로 준다[편집]

원 논문의 결과는 반복 불변식의 형태로 진술된다. $A$ 가 $\delta_{4k} \le 0.1$ 을 만족하고 $y = Ax + e$ 일 때

$$\|x - x^{j+1}\|_2 \ \le\ \tfrac12\,\|x - x^{j}\|_2 \;+\; C\,\nu$$

가 성립한다. 여기서 $\nu$ 는 복원 불가능 에너지(unrecoverable energy)로

$$\nu \;=\; \|x - x_k\|_2 \;+\; \frac{1}{\sqrt{k}}\|x - x_k\|_1 \;+\; \|e\|_2$$

이고 $x_k$ 는 $x$ 의 상위 $k$ 성분만 남긴 것, 상수는 원 논문 기준 $C = 10$ 이다. 이 부등식을 풀면

$$\|x - x^{j}\|_2 \ \le\ 2^{-j}\|x\|_2 + 2C\,\nu$$

가 되어, $j \approx \log_2(\|x\|_2/\nu)$ 회 반복이면 잡음·비희소성 수준까지 내려간다. 읽는 법은 이렇다. 신호가 정확히 $k$-희소이고 잡음이 없으면 $\nu = 0$ 이라 오차가 기하급수로 0에 수렴한다. 그렇지 않으면 정확 복원은 애초에 불가능하고, CoSaMP는 가능한 최선(최적 $k$항 근사 + 잡음) 수준까지 상수배 이내로 데려다준다.

여기서 중요한 것은 이 보증이 균일(uniform)하다는 점이다. 행렬 $A$ 가 RIP만 만족하면 모든 희소 신호에 대해 동시에 성립한다. 반면 OMP의 대표적 보증은 신호를 먼저 고정하고 랜덤 행렬을 뽑는 비균일 형태이거나, 균일하게 만들려면 $\delta_{k+1} < 1/(\sqrt{k}+1)$ 처럼 $k$ 에 따라 조여지는 조건이 필요하다. CoSaMP의 조건 $\delta_{4k} \le 0.1$ 은 $k$ 와 무관한 절대 상수이며, 이 차이가 두 알고리즘의 이론적 지위를 가른다.¹

가우시안이나 부분 푸리에 같은 표준 앙상블에서 $\delta_{4k} \le 0.1$ 은 $m \gtrsim k\log(n/k)$ 측정이면 높은 확률로 만족되므로, 표본 복잡도도 $\ell_1$ 최소화와 같은 차수다.

4. 계산량[편집]

반복당 비용은 이렇게 쪼개진다.

• 프록시 $A^\top r$ — 행렬-벡터 곱 한 번. 밀집 행렬이면 $O(mn)$, $A$ 가 고속 푸리에 변환이나 웨이블릿 연산자면 $O(n\log n)$.
• 상위 $2k$ 선택 — 부분 선택 알고리즘으로 $O(n)$.
• 최소제곱 $A_T^{+}y$ — 여기가 유일한 함정이다. 직접 풀면 $O(mk^2)$ 라 $k$ 가 크면 지배적이 된다.
• 절단·잔차 갱신 — $O(n)$ 과 곱 한 번.

원 논문의 요령은 최소제곱을 정확히 풀지 않는 것이다. $A_T$ 가 RIP 덕에 잘 조건화돼 있으므로 켤레기울기법이나 리처드슨 반복 서너 번이면 다음 반복 불변식을 깨지 않을 만큼 정확한 해가 나온다. 그러면 반복당 비용이 행렬-벡터 곱 몇 번으로 줄고, 전체는

$$O\!\left(L \cdot \log\frac{\|x\|_2}{\nu}\right), \qquad L = \text{행렬-벡터 곱 비용}$$

이 된다. 밀집 행렬이면 $O(mn\log(\cdot))$. 이 차수는 신호를 한 번 읽는 비용에 로그 인자만 붙은 것이라 차수 면에서 사실상 최적이며, CoSaMP 논문의 가장 강한 주장이 바로 이것이다. 내점법으로 푸는 기저 추구와 비교하면 자릿수 단위로 싸다.

메모리도 $O(n)$ 이면 되고 $A$ 를 명시적으로 저장할 필요가 없다 — $A$ 와 $A^\top$ 을 벡터에 곱하는 연산자만 있으면 된다는 점이 대규모 영상 복원에서 결정적이다.

5. 사촌들과의 비교[편집]

같은 시기에 거의 같은 아이디어가 여러 이름으로 나왔다. 정직하게 늘어놓으면 이렇다.

알고리즘	한 반복의 골자	지지집합 크기	최소제곱	되돌리기
OMP	상위 1개 추가	매번 +1	매 반복	없음
부분공간 추구 (SP)	상위 k 추가 후 2k에서 절단	항상 k	반복당 2회	있음
CoSaMP	상위 2k 추가 후 3k에서 절단	항상 k	반복당 1회	있음
반복 하드 임계화 (IHT)	경사 한 걸음 + 상위 k 절단	항상 k	없음	있음
기저 추구	볼록 문제 전역 최소화	해당 없음	해당 없음	해당 없음

• 부분공간 추구(Dai–Milenkovic 2009)는 CoSaMP와 사실상 쌍둥이다. 후보를 $2k$ 로 만들고(CoSaMP는 $3k$), 절단 후 한 번 더 최소제곱을 푼다. 그래서 RIP 조건의 차수가 $3k$ 로 한 단계 낮고, 반복당 최소제곱이 두 번이라 조금 비싸다. 성능은 실무에서 구분이 어려울 정도로 비슷하다.
• **반복 하드 임계화**는 최소제곱을 아예 빼고 경사 한 걸음 + 절단만 반복한다. $x^{j+1} = H_k\bigl(x^{j} + A^\top(y - Ax^{j})\bigr)$. 반복당 비용이 가장 싸지만 수렴이 느리고, $A$ 의 스케일에 민감해서 정규화된 변형(NIHT)이 필요하다. 원 논문의 보증 조건은 $\delta_{3k} < 1/\sqrt{32} \approx 0.177$ (Blumensath–Davies 2009). 여기에 “절단으로 고른 지지집합 위에서 최소제곱을 다시 푼다”를 얹으면 하드 임계화 추구(HTP, Foucart 2011)가 되는데, 이건 사실상 CoSaMP에서 후보 확장 폭을 $k$ 로 줄인 것과 같다.
• **기저 추구/라쏘**는 $k$ 를 몰라도 되고 위상 전이가 가장 좋지만, 전역 볼록 문제를 푸는 비용을 낸다. FISTA 같은 1차법을 쓰면 반복당 비용은 CoSaMP와 비슷하지만 반복 수가 수백~수천 회로 늘어난다.

실무 감각으로는 $k$ 를 대충 알고 있고 $A$ 가 빠른 변환으로 주어지면 CoSaMP/SP, $k$ 를 전혀 모르면 $\ell_1$, 극도로 희소하고 코드를 짧게 쓰고 싶으면 OMP다.

6. 함정과 실무 조언[편집]

• $k$ 를 입력으로 요구한다. 이게 가장 큰 실무적 약점이다. $k$ 를 과대 추정하면 잡음을 신호로 주워 담고, 과소 추정하면 참 성분을 영구히 잘라 버린다. 대안은 $k$ 를 늘려 가며 잔차를 보는 바깥 루프인데, 그러면 “빠르다”는 장점이 상당 부분 사라진다. $\ell_1$ 이 여전히 살아남는 이유의 절반이 이것이다.
• $3k \le m$ 은 최소한의 필요조건이다. 후보 집합 크기가 측정 수를 넘으면 최소제곱이 미결정계가 되어 알고리즘이 무의미해진다. 실제로는 RIP 차수 $4k$ 때문에 $m$ 이 $k$ 의 수 배는 되어야 한다.
• 최소제곱을 너무 정확히 풀지 마라. 직관과 반대인데, CG 3~5회면 충분하고 그 이상은 낭비다. 어차피 다음 단계에서 절단해 버릴 값이다. 반대로 너무 대충 풀면 절단 순서가 뒤바뀌어 수렴이 깨지므로, 반복 수를 고정하지 말고 잔차 감소를 확인하는 편이 안전하다.
• 정지 조건. 잔차 노름이 잡음 수준 $\|e\|_2$ 에 도달했을 때, 또는 잔차가 더 이상 줄지 않을 때 멈춘다. 오차 반감 성질 덕에 반복 수 상한을 $\log_2(\|y\|_2/\varepsilon)$ 로 미리 걸어 두는 것도 흔하다. 지지집합이 두 반복 사이에 변하지 않으면 그것도 정지 신호다.
• 수렴이 단조롭지 않다. OMP의 잔차는 단조 감소가 보장되지만 CoSaMP는 아니다. 절단 때문에 한 반복에서 잔차가 튈 수 있다. 로그를 보고 “발산한다”고 놀라기 전에 몇 반복 더 돌려 보는 게 맞다.²
• 열 정규화. $A$ 의 열 노름이 제각각이면 프록시 $A^\top r$ 의 크기 비교가 왜곡되어 상위 $2k$ 선택이 엉뚱해진다. 탐욕 계열 전부가 공유하는 전제이고, 실패 사례의 상당수가 여기서 나온다.

7. 응용에서의 위치[편집]

CoSaMP가 실제로 도는 곳은 대개 $A$ 가 명시적 행렬이 아닌 대규모 문제다. MRI 재구성, 성긴 각도 CT, 레이더 산란점 추정, 채널 추정처럼 $A$ 가 FFT나 부분표본화 연산자로 주어지고 $n$ 이 $10^6$ 을 넘는 상황에서, 행렬-벡터 곱 몇 번으로 한 반복이 끝난다는 성질이 그대로 경쟁력이 된다. 딕셔너리 학습의 희소 코딩 단계에서도 OMP 대신 쓰이는데, 원자 수가 많고 $k$ 가 중간 규모일 때 유리하다.

한편 이론 쪽에서 CoSaMP가 남긴 진짜 유산은 “탐욕법도 균일 보증을 가질 수 있다”는 증명과, 그 증명 틀이 구조적 희소성(블록·트리·그래프 모형)으로 그대로 확장된다는 점이다. 모형 기반 CoSaMP(Baraniuk 외 2010)는 상위 $2k$ 선택과 상위 $k$ 절단을 각각 “모형에 맞는 근사 사영”으로 갈아 끼우기만 하면 되는데, 절단 연산자를 바꿔 끼울 수 있게 설계된 구조 덕분이다.³

8. 관련 문서[편집]

• 압축센싱 · 기저 추구 · 직교 매칭 추구 · 상호간섭성
• 최소자승법 · 켤레기울기법 · QR 분해 · 조건수
• 근접 경사법 · 라쏘 · 볼록 최적화
• 딕셔너리 학습 · 희소행렬 · 역문제
• 고속 푸리에 변환 · 웨이블릿 변환 · 전변분 잡음제거

9. Footnotes[편집]

1. 균일/비균일 구분은 논문을 읽을 때 가장 자주 흐려지는 지점이다. “확률 $1-\epsilon$ 로 복원한다”는 문장에서 확률이 행렬에만 걸려 있으면 균일, 신호와 행렬 둘 다에 걸려 있으면 비균일이다. 후자는 “적대적으로 고른 최악의 신호”를 배제하고 있으므로 훨씬 약한 주장인데, 초록만 읽으면 구분이 안 간다. ↩

2. 잔차가 튀는 걸 버그로 오해해 절단 단계를 빼 버리면 그건 그냥 OMP의 배치 버전이 되고, 되돌리기 능력이 사라져 보증도 같이 사라진다. “이상하게 보이는 부분”이 알고리즘의 존재 이유인 흔한 사례. ↩

3. 이름에 “matching pursuit”가 붙어 있지만 원조 매칭 추구와의 관계는 사실 느슨하다. 잔차와 사전의 상관을 본다는 것 말고는 공통점이 별로 없고, 동작은 오히려 하드 임계화 계열의 사영 경사법에 가깝다. 2008년 무렵 압축센싱 논문 제목에 “pursuit”를 붙이는 것이 일종의 관행이었다는 사정을 감안하는 편이 낫다. ↩