기저 추구

1. 개요

기저 추구 Basis Pursuit
약칭	BP, 잡음판은 BPDN
제안	Chen–Donoho–Saunders (1995 기술보고서, 1998 SIAM J. Sci. Comput.)
정식화	min ‖x‖1 s.t. Ax = b
부류	볼록 완화 기반 희소 복원, 선형계획법으로 환원
대표 보증	상호간섭성 조건, RIP, 널공간 성질(NSP)
경쟁자	직교 매칭 추구(탐욕 계열)

기저 추구(basis pursuit)는 미결정 선형계 $Ax = b$ 의 무수한 해 중에서 $\ell_1$ 노름이 가장 작은 것을 고르는 볼록 최적화 문제이자, 그 해가 놀랍게도 가장 희소한 해와 일치한다는 사실을 이용하는 희소 복원 원리다.

$$\min_x \|x\|_1 \quad \text{s.t.}\quad Ax = b, \qquad A \in \mathbb{R}^{m\times n},\; m < n$$

첸·도노호·손더스가 1998년 논문 Atomic Decomposition by Basis Pursuit에서 이름을 붙였다. 원래 문제의식은 “과완비 사전(overcomplete dictionary)에서 신호를 원자들의 합으로 분해하고 싶은데, 표현이 유일하지 않으니 무엇을 골라야 하는가”였다. 답이 $\ell_1$ 이었고, 그 답이 8년 뒤 압축센싱의 핵심 복원기가 됐다.

2. 세 가지 얼굴 — BP, BPDN, LASSO

측정에 잡음이 있으면 등식 제약을 그대로 걸 수 없다. 그래서 실제로 쓰이는 형태는 셋이다.

• BP: $\min \|x\|_1$ s.t. $Ax = b$. 무잡음.
• BPDN(basis pursuit denoising): $\min \|x\|_1$ s.t. $\|Ax-b\|_2 \le \varepsilon$. 잡음 크기 $\varepsilon$ 을 알 때.
• 라그랑주형: $\min \frac12\|Ax-b\|_2^2 + \tau\|x\|_1$. 통계 쪽 이름이 라쏘(LASSO, Tibshirani 1996)다.

셋은 해집합의 의미에서 동치다. 적당한 $\varepsilon$ 마다 대응하는 $\tau$ 가 존재하고 그 역도 마찬가지다. 다만 그 대응 관계는 데이터에 의존하며 사전에 알 수 없다 — $\varepsilon$ 을 0.01로 잡았을 때의 $\tau$ 가 얼마인지는 문제를 풀어 봐야 안다. 실무에서 이 셋을 고르는 기준은 순전히 “무엇을 알고 있느냐”다. 잡음 표준편차를 알면 BPDN, 모르면 $\tau$ 를 교차검증으로 정하는 라쏘, 무잡음 합성 실험이면 BP.

BP는 $x = x^+ - x^-$ ($x^\pm \ge 0$)로 쪼개면 변수 $2n$ 개짜리 선형계획법 문제가 된다. ”$\ell_1$ 최소화는 LP다”라는 한 줄이 이 분야를 열었다고 해도 과언이 아니다. 반면 BPDN은 이차원뿔 제약이 붙어 SOCP, 라그랑주형은 이차계획법이다.

3. ℓ0에서 ℓ1으로 — 왜 볼록 완화가 정당한가

진짜 목표는 0이 아닌 성분 수의 최소화 $\min\|x\|_0$ s.t. $Ax=b$ 인데, 이건 지지집합 조합을 훑는 문제라 NP-난해다(Natarajan 1995). $\|x\|_0$ 은 볼록도 연속도 아니다. 여기서 $p \to 1$ 로 완화하면 $\|x\|_p$ 가 볼록이 되는 최소의 지수가 정확히 $p=1$ 이다. $p<1$ 은 더 희소성을 잘 유도하지만 비볼록이라 전역해 보장이 사라지고, $p=2$ 는 볼록하지만 에너지를 모든 성분에 골고루 퍼뜨려 희소해를 절대 못 찾는다. $\ell_1$ 은 볼록성과 희소성 유도가 동시에 성립하는 유일한 경계선이다.

기하로 보면 즉각 납득된다. 해집합 $\{x : Ax=b\}$ 는 아핀 부분공간이고, $\ell_1$ 최소화는 원점에서 $\ell_1$ 공을 부풀리다가 이 부분공간에 처음 닿는 점을 고르는 일이다. $\ell_2$ 공(구)은 매끈해서 접점이 좌표축과 무관한 일반 위치에 잡히지만, $\ell_1$ 공(교차다포체)은 좌표축 위에 뾰족한 꼭짓점이 있고 그 사이는 평평한 면이다. 뾰족한 곳이 먼저 닿을 확률이 압도적으로 높고, 꼭짓점·저차원 면 위의 점은 정의상 0인 성분을 많이 가진다. 즉 희소성은 $\ell_1$ 공의 모서리 구조가 만들어 낸 기하학적 결과이지 알고리즘의 부산물이 아니다.

4. 언제 정확히 복원되는가

”$\ell_1$ 이 $\ell_0$ 의 해를 준다”는 보증 조건은 강도 순으로 세 갈래다.

상호간섭성(mutual coherence). 열이 단위노름으로 정규화된 $A$ 에 대해

$$\mu(A) = \max_{i \ne j} \bigl| a_i^{T} a_j \bigr|$$

일 때, 참해의 희소도가

$$\|x\|_0 < \tfrac12\left(1 + \frac{1}{\mu(A)}\right)$$

를 만족하면 BP가 그 해를 유일하게 복원한다(Donoho–Elad 2003, Gribonval–Nielsen 2003, Tropp 2004). 계산이 $O(n^2 m)$ 으로 끝나 실제로 확인할 수 있다는 것이 최대 장점. 대신 결과가 보수적이다. 웰치 하한 $\mu \ge \sqrt{(n-m)/(m(n-1))}$ 때문에 $\mu \gtrsim 1/\sqrt{m}$ 을 넘길 수 없고, 따라서 이 조건이 허용하는 희소도는 기껏해야 $O(\sqrt{m})$ 이다. 이른바 제곱근 장벽.

제한등척성(RIP). 모든 $s$-희소 $x$ 에 대해 $(1-\delta_s)\|x\|_2^2 \le \|Ax\|_2^2 \le (1+\delta_s)\|x\|_2^2$ 를 만족하는 최소의 $\delta_s$ 를 등척 상수라 한다. $\delta_{2s} < \sqrt{2}-1 \approx 0.4142$ 이면 BP가 모든 $s$-희소 신호를 정확히 복원하고(Candès 2008), 잡음이 있어도

$$\|x^\star - x\|_2 \le C_0 \frac{\|x - x_s\|_1}{\sqrt{s}} + C_1 \varepsilon$$

라는 안정성 한계가 따라온다($x_s$ 는 상위 $s$ 성분만 남긴 것). 이 부등식이 중요한 이유는 정확히 희소하지 않아도 된다는 점 — 실제 신호처럼 계수가 빠르게 감쇠하기만 해도 보증이 붙는다. 상수는 이후 계속 개선돼 $\delta_{2s} < 1/\sqrt{2}$ 가 최선이자 최적임이 알려져 있다(Cai–Zhang 2013). 함정은 주어진 행렬의 RIP 상수를 계산하는 것 자체가 NP-난해라는 것이다. 그래서 RIP는 “가우시안 랜덤 행렬은 $m \gtrsim s\log(n/s)$ 이면 높은 확률로 RIP를 만족한다” 같은 확률적 진술로만 쓰인다.

널공간 성질(NSP). 사실 BP의 정확 복원과 동치인 조건은 이쪽이다. 모든 $h \in \ker A \setminus \{0\}$ 와 모든 $|S| \le s$ 에 대해 $\|h_S\|_1 < \|h_{S^c}\|_1$ 이면, 그리고 그때만 모든 $s$-희소 신호가 BP로 복원된다. 뜻은 직관적이다 — 영공간 벡터가 어느 $s$ 개 좌표에 에너지를 몰아 놓을 수 없어야 한다. RIP는 NSP의 검증 가능한 충분조건일 뿐이다.

5. 위상 전이 — 실전 성능은 이론보다 훨씬 좋다

위 보증들은 최악의 경우를 다루므로 지나치게 비관적이다. 실제로 실험을 돌리면 성공/실패가 칼같은 문턱을 사이에 두고 갈린다. 도노호와 태너는 $\ell_1$ 복원의 성공 조건이 $\ell_1$ 공(교차다포체)의 랜덤 사영이 이웃성(neighborliness)을 유지하는가라는 볼록기하 문제와 정확히 동치임을 보이고, 언더샘플링 비 $\delta = m/n$ 와 희소도 비 $\rho = s/m$ 평면 위에서 곡선 $\rho_W(\delta)$ 를 닫힌 형태에 가깝게 얻었다. 이 곡선 아래면 거의 항상 성공, 위면 거의 항상 실패다. $n \to \infty$ 에서 전이 폭은 0으로 좁아진다.

더 놀라운 것은 보편성(universality)이다. 가우시안, 베르누이 ±1, 부분 푸리에 등 서로 다른 랜덤 행렬 앙상블이 사실상 같은 전이 곡선을 준다. 그래서 실무 감각으로는 ”$m \approx 2s\log(n/s)$ 정도면 대체로 된다” 혹은 ”$m$ 이 $s$ 의 4~5배면 웬만하면 복원된다”는 경험칙이 통한다.

6. 어떻게 푸는가

• 내부점법. 원 논문의 선택으로, 로그 배리어 기반 원시-쌍대 내점법(PDCO)을 썼다. 반복 수가 문제 크기에 거의 무관하게 수십 회로 끝나 정확도가 매우 높다. 대신 매 반복에서 뉴턴계를 풀어야 해서, $A$ 가 빠른 변환(FFT·웨이블릿)으로만 주어지는 대규모 문제에서는 반복적 선형해법을 끼워야 한다.
• ISTA / FISTA. 라그랑주형에 근접 경사법을 적용하면 $x \leftarrow \mathcal{S}_{\tau/L}(x - \frac1L A^{T}(Ax-b))$ 라는, 행렬-벡터 곱 두 번 + 연성 임계화 한 번짜리 반복이 된다. 네스테로프 가속을 얹은 FISTA는 목적함수 오차가 $O(1/k^2)$ 로 준다(Beck–Teboulle 2009). 코드가 열 줄이고 메모리를 안 먹어서 사실상 기본값.
• 교대방향 승수법(ADMM). $z = x$ 를 분리하면 $x$-갱신은 선형계(고정 행렬이라 인수분해 재사용 가능), $z$-갱신은 연성 임계화로 닫힌 형태다. BPDN처럼 제약형을 다룰 때 특히 편하다.
• 호모토피 / 최소각 회귀(LARS). 라그랑주형의 해 $x(\tau)$ 는 $\tau$ 에 대해 조각별 선형이다. 꺾이는 지점(지지집합이 하나 늘거나 주는 순간)만 따라가면 전체 정규화 경로를 유한 번에 그릴 수 있다(Osborne 외 2000, Efron 외 2004). 해가 매우 희소할 때 압도적으로 빠르며, 덤으로 $\tau$ 선택을 위한 경로 전체를 공짜로 얻는다.

7. 탐욕 계열과의 비교, 그리고 위치

가장 자주 놓이는 대조가 직교 매칭 추구(OMP)다. 요약하면 속도 대 보증의 거래다.

OMP는 $k$-희소 신호에 정확히 $k$ 회 반복하고 매번 작은 최소제곱만 풀므로 $k$ 가 작으면 BP보다 자릿수 단위로 빠르다. 반면 보증은 대체로 더 약하다 — 상호간섭성 기반으로는 $\mu < 1/(2k-1)$ 로 BP와 사실상 같은 문턱이지만, RIP 기반의 균일 보증이나 잡음 아래의 안정성에서는 BP 쪽이 강하다. 결정적으로 OMP는 한 번 잘못 고른 원자를 되돌릴 수 없고, BP는 전역 볼록 문제라 그런 함정이 없다. 반대로 BP는 쌍대성에 기반한 최적성 인증서(쌍대 간극)를 제공하지만 “몇 개를 고를지”를 직접 통제하지 못한다. 실전에서는 $k$ 를 대략 알고 속도가 급하면 OMP, 보증이 필요하고 신호가 압축가능(정확히 희소하지 않음)하면 BP, 둘 다 원하면 CoSaMP·Subspace Pursuit 같은 하이브리드를 쓴다.

기저 추구는 결국 압축센싱의 복원 단계를 담당하는 표준 도구이며, 벌점을 $\|x\|_1$ 에서 $\|Lx\|_1$ 로 바꾸면 전변분 잡음제거가, $\ell_2$ 로 바꾸면 티호노프 정규화가 된다는 점에서 정규화 삼형제의 한 축이다.¹ MRI 가속, 성긴 각도 CT, 전파간섭계 영상화, 딕셔너리 학습의 희소 부호화 단계가 전부 이 문제를 안쪽 루프에서 반복해 푼다.²³

8. 관련 문서

• 압축센싱 · 직교 매칭 추구 · 딕셔너리 학습
• 티호노프 정규화 · 전변분 잡음제거 · 역문제
• 볼록 최적화 · 선형계획법 · 내점법 · 이차계획법
• 근접 경사법 · 교대방향 승수법 · 모로 포락
• 라쏘 · 최소각 회귀 · 쌍대성 · 교차검증
• 최소자승법 · 특이값 분해 · 희소행렬

9. Footnotes

1. 이름이 여러 개인 것도 이 바닥의 특징이다. 신호처리는 basis pursuit, 통계는 LASSO, 최적화는 $\ell_1$ 정규화 최소제곱, 지구물리는 1970년대부터 “최소 $\ell_1$ 디컨볼루션”이라고 불렀다. 실제로 클래어바우트-머프리아(1973)와 테일러-뱅크스-매코이(1979)가 반사계수 추정에 $\ell_1$ 을 쓴 것이 훨씬 앞선다. 도노호 본인도 원 논문에서 이 선행 연구들을 성실히 인용해 뒀다. ↩

2. $\ell_1$ 이 “희소성의 볼록 완화”라는 말은 정확히는 $\ell_0$ 을 단위 $\ell_\infty$ 공 위에서 볼록 포락(convex envelope)한 것이 $\ell_1$ 이라는 뜻이다. 같은 논리를 행렬의 계수(rank)에 적용하면 핵노름(nuclear norm)이 나오고, 그래서 행렬 완성 문제가 기저 추구와 정확히 같은 증명 구조를 갖는다. 넷플릭스 상금 문제와 MRI 가속이 사촌인 이유. ↩

3. 실무에서 가장 자주 나오는 실패는 알고리즘이 아니라 전처리다. $A$ 의 열 노름이 제각각인데 정규화를 안 하면 $\ell_1$ 벌점이 열 크기가 큰 성분에만 유리하게 작용해, 수학적으로 멀쩡한 코드가 엉뚱한 지지집합을 뱉는다. “결과가 이상한데요”의 절반은 열 정규화를 안 한 것이다. ↩