압축센싱

수치해석 통계 마지막 수정: 2026-08-04 05:02:24

1. 개요[편집]

압축센싱 Compressed Sensing
다른 이름	압축 표본화(compressive sampling), CS
출발점	Candès–Romberg–Tao, Donoho (2006)
전제	희소성 + 측정-표현 기저의 비간섭성
복원	ℓ₁ 최소화(볼록) 또는 탐욕 알고리즘
대표 응용	MRI 가속, 단일화소 카메라, 레이더, 전파간섭계

압축센싱(compressed sensing)은 신호가 어떤 기저에서 희소(대부분의 계수가 0)하다는 사전 지식이 있을 때, 미지수 개수보다 훨씬 적은 수의 비간섭 선형 측정만으로 그 신호를 정확히 복원할 수 있다는 표본화·복원 이론이다. 2006년 캉데스-롬버그-타오와 도노호의 논문 이후 20년 가까이 신호처리·의료영상·역문제 전반을 다시 쓴 아이디어다.

먼저 오해부터 정리하자. 압축센싱은 표본화 정리를 깨지 않는다. 나이퀴스트 율은 “대역폭 $B$ 이내라는 것 외에는 아무것도 모르는” 신호 전부를 선형 재구성으로 복원하기 위한 최악의 경우 요구조건이다. 압축센싱은 여기에 희소성이라는 사전 가정을 하나 더 추가하고, 대신 균일 표본화를 랜덤 표본화로, 선형 보간 복원을 비선형 최적화로 바꾼다. 가정을 늘렸으니 요구 표본 수가 줄어드는 것은 배신이 아니라 거래다. 신호가 희소하지 않으면 이 이론은 그냥 아무 말도 해 주지 않는다.¹

2. 문제 설정과 ℓ₀/ℓ₁[편집]

미지 신호 $x \in \mathbb{R}^n$ , 측정행렬 $A \in \mathbb{R}^{m \times n}$ , 관측 $y = Ax + e$ 이며 $m \ll n$ 이다. 미지수가 식보다 많으니 해는 무한히 많다. 여기서 어떤 해를 고르느냐가 전부다.

최소자승법식 최소 노름 해 $\min \|x\|_2$ s.t. $Ax=y$ 는 닫힌 형태로 나오지만, 에너지를 모든 성분에 골고루 퍼뜨려 희소해를 절대 찾지 못한다.
진짜 목표는 $\min \|x\|_0$ — 0이 아닌 성분 수의 최소화. 그런데 이건 조합 탐색이라 NP-난해다.
실용해는 $\min \|x\|_1$ . 볼록 완화이며 선형계획법으로 풀린다. 이것이 기저추적(basis pursuit)이다.

한 가지 더 짚을 것은 신호가 원래 좌표에서 희소한 경우가 거의 없다는 점이다. 영상은 픽셀 값이 희소하지 않지만 웨이블릿 계수는 희소하고, 음성은 시간축에서 빽빽하지만 스펙트럼은 성기다. 그래서 실제로는 표현 기저 $\Psi$ 를 두어 $x = \Psi c$ 로 쓰고, 물리 장비가 주는 측정 연산자 $\Phi$ 와 합쳐 $A = \Phi\Psi$ 를 다룬다. 이때 보증 조건은 $\Phi$ 와 $\Psi$ 사이의 비간섭성이 되며, 설계 자유도가 있는 부분은 대개 $\Phi$ 의 표본 위치를 어떻게 무작위화하느냐 하나뿐이다.

$\ell_1$ 이 왜 희소해를 고르는지는 기하로 보는 게 빠르다. $\ell_2$ 공은 매끈해서 아핀 부분공간과 일반적으로 좌표축이 아닌 점에서 만나지만, $\ell_1$ 공은 좌표축 위에 뾰족한 꼭짓점이 있어서 공을 부풀리다 보면 십중팔구 꼭짓점에서 먼저 닿는다. 그 접점이 곧 희소해다.

한 화면에서 세 문제를 실제로 푼다. 상단은 min ½‖Ax−y‖² + τ‖x‖₁ 를 FISTA 로 푼 복원 스템으로, 스텝 1/L 의 L = ‖A‖₂² 는 파워반복으로 매 문제마다 측정하고 τ 는 연속감소로 내린다. 중단은 같은 A·y 에 대한 ℓ2 최소노름해 Aᵀ(AAᵀ)⁻¹y 를 콜레스키로 직접 푼 것이고, 상단과 같은 y축을 쓴다. 하단은 k 를 고정한 채 M = 8..96 을 훑으며 매번 새 A·x₀ 를 뽑아 상대오차 1e−3 미만을 성공으로 세는 위상 전이 곡선이다. N=128, M=48, k=5, 무잡음에서 ℓ1 은 상대오차 2.1e−7 로 참 스파이크 5개를 전부 찾고 가짜 성분이 0인데, 같은 데이터의 ℓ2 최소노름해는 상대오차 0.83 에 에너지의 69%가 참 지지집합 밖에 실린다 — 잔차는 1e−12 수준이라 방정식 자체는 정확히 만족한다. M 을 20 으로 내리면 ℓ1 도 상대오차 0.80 으로 무너진다. k=5 의 성공률 50% 지점은 M* ≈ 21 이고 2k·ln(N/k) = 32 는 그 오른쪽에 선다. 반복 예산을 5.5배로 늘려도 문턱은 한 칸 안쪽으로만 움직인다.

3. 언제 ℓ₁이 ℓ₀과 같아지는가[편집]

핵심 보증 조건이 제한등거리성(restricted isometry property, RIP)이다. 어떤 $\delta_s \in (0,1)$ 에 대해 모든 $s$ -희소 벡터 $x$ 가

(1-\delta_s)\|x\|_2^2 \le \|Ax\|_2^2 \le (1+\delta_s)\|x\|_2^2

를 만족하면 $A$ 는 차수 $s$ 의 RIP를 갖는다. 의미는 “ $A$ 가 희소 벡터들에 대해서는 거의 등거리 사상, 즉 거의 직교행렬처럼 군다”는 것. $\delta_{2s} < \sqrt{2}-1$ 이면 잡음 없는 경우 $\ell_1$ 최소화가 정확한 $s$ -희소 해를 정확히 복원하고, 잡음이 있으면 오차가 잡음 크기와 최적 $s$ 항 근사 오차에 비례하는 안정적 경계가 성립한다.

문제는 주어진 행렬이 RIP를 갖는지 확인하는 것 자체가 NP-난해라는 점이다. 그래서 실무는 두 갈래로 간다.

확률적 보증. 성분이 i.i.d. 가우시안이거나 ±1 랜덤인 행렬은 $m \gtrsim s\log(n/s)$ 이면 높은 확률로 RIP를 만족한다. 랜덤하게 뽑은 푸리에 변환 행(즉 무작위 주파수 측정)도 로그 인자만 조금 더 붙여 성립한다.
상호간섭도(mutual coherence). 열 벡터 사이 최대 정규화 내적 $\mu(A) = \max_{i\ne j} |\langle a_i, a_j\rangle| / (\|a_i\|\|a_j\|)$ 가 작으면 된다. $s < \tfrac{1}{2}(1+1/\mu)$ 이면 유일성과 복원이 보장된다. 계산이 쉬운 대신 조건이 훨씬 보수적( $\sqrt{m}$ 수준의 희소도까지만 커버)이다. 웰치 경계 $\mu \ge \sqrt{(n-m)/(m(n-1))}$ 아래로는 어차피 못 내려간다.

여기서 “비간섭성”이 왜 중요한지가 드러난다. 측정 기저(예: 푸리에)와 표현 기저(예: 웨이블릿 변환)가 서로 최대한 안 닮아야, 한 점에 몰린 계수 정보가 모든 측정에 골고루 번져 몇 개만 봐도 알아볼 수 있다. 반대로 두 기저가 같으면(픽셀을 픽셀로 재면) 안 잰 곳은 영원히 모른다.

4. 복원 알고리즘[편집]

기저추적 / BPDN·LASSO. $\min \tfrac{1}{2}\|Ax-y\|_2^2 + \lambda\|x\|_1$ . 잡음이 있는 실측의 표준형이고 볼록 최적화 문제다. 내점법은 정확하지만 대규모에서 무겁다.
탐욕법(OMP, CoSaMP). 잔차와 가장 상관 큰 열을 하나씩 뽑아 지지집합을 키우고 최소자승으로 계수를 갱신한다. 구현이 짧고 매우 희소한 경우 빠르지만, 보증 조건이 더 빡세다.
ISTA/FISTA. 경사하강법 한 걸음 + 연성 임계화 $S_\lambda(x)=\mathrm{sign}(x)\max(|x|-\lambda,0)$ 를 번갈아 적용하는 근접 경사법. 행렬-벡터 곱만 필요해 $A$ 가 FFT로 구현되는 문제에 딱 맞는다. FISTA는 네스테로프 가속으로 수렴률을 $O(1/k)$ 에서 $O(1/k^2)$ 로 끌어올린다. 실무 MRI 재구성기의 절반은 이 계열이다.
ADMM·분할법. TV 정규화나 여러 정규화항을 섞을 때 각 항을 따로 근접 연산자로 다루려고 쓴다.

5. 위상 전이[편집]

도노호와 태너는 $\ell_1$ 복원의 성공/실패가 날카로운 위상 전이를 보인다는 것을 다면체 조합론으로 보였다. 언더샘플링 비 $\delta = m/n$ 과 희소도 비 $\rho = s/m$ 평면에서, $\rho < \rho^*(\delta)$ 이면 거의 확실히 정확 복원, 넘으면 거의 확실히 실패한다. $n\to\infty$ 에서 경계는 두께 0으로 얇아지며, 이 곡선은 랜덤 다면체의 면 개수 세기에서 유도된 값과 수치 실험이 소수점 몇 자리까지 일치한다.² 실무적 함의도 분명하다 — RIP 기반 상수는 지나치게 보수적이라 설계에 못 쓰지만, 위상 전이 곡선은 “이 희소도에서 몇 배 가속까지 가능한가”를 실제로 예측한다.

6. 실제로 어디에 쓰이나[편집]

MRI 가속. 압축센싱의 킬러 앱. MRI는 원래 k-공간(푸리에 영역)에서 측정하고 촬영 시간이 측정 수에 정비례한다. 러스티그 등(2007)은 가변밀도 랜덤 언더샘플링 + 웨이블릿/TV 희소성 + 비선형 복원으로 2~8배 가속을 보였고, 지금은 주요 제조사 장비에 제품 기능으로 들어가 있다. 랜덤 언더샘플링이 만드는 잡음 같은 앨리어싱이 규칙적 언더샘플링의 겹침 유령보다 훨씬 지우기 쉽다는 것이 요점이다.
단일화소 카메라. 라이스대의 DMD 기반 장치. 픽셀 배열 대신 광소자 하나로 랜덤 마스크를 씌운 총광량을 $m$ 번 재고 영상을 복원한다. 실용 카메라라기보다 검출기가 비싼 파장대(테라헤르츠, 적외선)에서 의미가 있다.
전파간섭계·레이더. 안테나 배열이 성기게 표본화한 가시도로 영상을 만드는 문제 자체가 희소 복원이다. 사건의 지평선 망원경의 정규화 최대우도 재구성도 같은 계보.
분석화학·지진 탐사. NMR 다차원 스펙트럼 획득 시간 단축, 성긴 지오폰 배치 보간 등.

7. 한계와 오해[편집]

과장이 유난히 많았던 주제라 선을 그어 둘 필요가 있다. 첫째, 희소하지 않으면 아무 보증도 없다. 실제 신호는 정확히 희소한 게 아니라 압축가능(계수가 멱법칙으로 감쇠)할 뿐이고, 이때 오차 경계에는 최적 $s$ 항 근사 오차가 그대로 남는다. 둘째, 측정행렬을 마음대로 못 고르는 경우가 대부분이다. 물리 장비가 정해 주는 행렬이 우연히 비간섭적일 이유는 없다. 셋째, 잡음 증폭. 가속률을 올릴수록 조건수가 나빠져 SNR이 떨어지므로, 임상에서 쓰는 가속률은 이론 상한보다 한참 보수적이다. 넷째, 요즘은 손으로 고른 희소 기저 대신 딕셔너리 학습이나 심층 학습 기반 사전(플러그앤플레이 사전, 언롤링 네트워크)이 성능을 앞지르는 경우가 많다. 다만 그 경우 “정확 복원 보증”이라는 압축센싱의 가장 매력적인 부분은 같이 사라진다.³

8. 관련 문서[편집]

“나이퀴스트를 이겼다”는 헤드라인이 2008년쯤 언론에 쏟아졌는데, 정확히 말하면 이긴 게 아니라 다른 게임을 한 것이다. 셰넌은 “대역제한”만 아는 상태에서의 최악 보증을 줬고, 압축센싱은 “희소하다”까지 아는 상태의 보증을 준다. 아는 게 많으면 덜 재도 된다 — 놀랍긴 해도 마법은 아니다. ↩
이 곡선을 처음 볼 때의 감상은 대개 “통계물리 상전이 도표 아닌가?”이다. 실제로 이후 연구는 근사 메시지 전달(AMP)의 상태 진화로 같은 경계를 재유도했고, 스핀글라스 이론의 레플리카 계산과 결과가 일치한다. 서로 다른 동네에서 같은 곡선이 나오면 대개 진짜다. ↩
이 지점이 압축센싱의 매력이자 약점이다. 보증이 있는 알고리즘은 느리고 보수적이며, 빠르고 잘 되는 최신 방법은 보증이 없다. 의료기기 인허가 문서를 쓰는 사람에게는 이 차이가 취향 문제가 아니라 생업 문제다. ↩