압축 센싱(Compressed Sensing)이란 무엇인가?

현대 데이터 과학 및 신호 처리에서 가장 혁명적인 패러다임 전환 중 하나가 ‘압축 센싱(Compressed Sensing / Compressive Sensing)‘입니다. 종래에 음성이나 이미지, 전자기파 등의 아날로그 신호를 디지털 데이터로 컴퓨터에 가져올 때 우리는 ‘나이퀴스트-섀넌의 샘플링 정리’라는 절대적인 법칙을 따라왔습니다. 그러나 압축 센싱은 이 상식을 뒤집고, “신호가 특정 조건(희소성)을 만족한다면 샘플링 정리가 요구하는 것보다 훨씬 적은 관측 데이터만으로 원래 신호를 완벽하게 복원할 수 있다"는 놀라운 수학적 보장을 제공합니다.

이 글에서는 샘플링 정리의 기초부터 시작하여 희소성의 수학적 정의, $L_1$ 최적화 문제로의 완화, 그리고 에마뉘엘 캉데스(Emmanuel Candès)와 테렌스 타오(Terence Tao) 등에 의한 이론적 돌파구의 핵심을 수식과 함께 깊이 있게 해설합니다. 나아가 MRI 고속화나 블랙홀 이미지 구축과 같은 응용 사례, Python을 사용한 구체적인 구현 코드까지 망라하여 압축 센싱의 전모를 밝힙니다.

1. 나이퀴스트-섀넌의 샘플링 정리와 그 한계

샘플링 정리의 기초

20세기 중반, 클로드 섀넌(Claude Shannon)과 해리 나이퀴스트(Harry Nyquist)에 의해 확립된 정보 이론의 기초에 ‘샘플링 정리’가 있습니다. 이 정리는 연속적인 아날로그 신호를 이산적인 디지털 신호로 변환할 때의 조건을 다음과 같이 정하고 있습니다.

나이퀴스트-섀넌의 샘플링 정리 대역폭이 $f_{\max}$ 로 제한된 신호를 완전히 재구성하기 위해서는 최소한 $2f_{\max}$ 의 샘플링 주파수(나이퀴스트 레이트)로 신호를 샘플링해야 한다.

예를 들어, 인간의 귀에 들리는 가청역의 상한은 약 20 kHz입니다. 따라서 음악 CD에서는 그 2배 이상인 44.1 kHz로 샘플링이 이루어지고 있습니다. 수식으로 표현하면, 연속 신호 $x(t)$ 가 푸리에 변환 $X(f)$ 를 가지고, $|f| > f_{\max}$ 에서 $X(f) = 0$ 이 되는 경우, $x(t)$ 는 다음의 싱크 함수(sinc 함수)를 사용한 보간 공식에 의해 완전히 복원됩니다.

$$ x(t) = \sum_{n=-\infty}^{\infty} x\left(\frac{n}{2f_{\max}}\right) \operatorname{sinc}\left(2f_{\max}t - n\right) $$

데이터 폭발과 정리의 한계

샘플링 정리는 매우 강력하며 현대 디지털 통신의 초석이 되었습니다. 그러나 기술의 진보와 함께 센서가 포착하는 정보량은 폭발적으로 증가했습니다. 고해상도 의료 영상(MRI나 CT), 천문학의 전파 망원경 배열, 초광대역 레이더 시스템 등에서는 나이퀴스트 레이트에 따라 샘플링을 하면 관측해야 하는 데이터량이 너무 방대해집니다.

결과적으로 다음과 같은 문제가 발생합니다:

스캔 시간의 증가: 예를 들어 MRI에서는 데이터를 수집하는 데 오랜 시간이 걸려 환자에게 육체적 부담을 강요합니다.
하드웨어의 한계: 초고주파 신호를 샘플링하기 위한 A/D 컨버터의 제조가 기술적으로 어렵거나 극히 비싸집니다.
데이터 스토리지와 통신의 압박: 대량의 샘플링 데이터를 저장·전송하기 위한 비용이 부풀어 오릅니다.

기존의 패러다임은 “대량으로 샘플링하고 이후 소프트웨어로 압축(JPEG이나 MP3 등)하여 불필요한 데이터를 버린다"는 것이었습니다. 그러나 “어차피 최종적으로 버릴 것이라면, 처음부터 필요한 정보만 직접 센싱(취득)할 수는 없을까?“라는 의문이 생깁니다. 이를 가능하게 한 것이 압축 센싱입니다.

2. 희소성(Sparsity)의 수학적 정의

압축 센싱이 성립하기 위한 절대 조건이 희소성(Sparsity)입니다. 희소성이란, “신호를 어떤 적절한 기저(표현 방법)로 변환했을 때, 그 성분의 대부분이 0(또는 0에 매우 가까운 값)이 된다"는 성질을 가리킵니다.

희소 벡터의 공식화

길이 $N$ 의 이산 신호(벡터) $\mathbf{x} \in \mathbb{R}^N$ 을 생각해보겠습니다. 이 신호가 어떤 직교 기저 행렬 $\mathbf{\Psi} \in \mathbb{R}^{N \times N}$ (예를 들어, 푸리에 변환 행렬이나 웨이블릿 변환 행렬)을 사용하여 다음과 같이 표현될 수 있다고 가정합니다.

$$ \mathbf{x} = \mathbf{\Psi} \mathbf{s} $$

여기서 $\mathbf{s} \in \mathbb{R}^N$ 은 기저 $\mathbf{\Psi}$ 상에서의 계수 벡터입니다. 이 벡터 $\mathbf{s}$ 중에서 0이 아닌 요소의 수가 $K$ 개일 때($K \ll N$), $\mathbf{x}$ 는 $K$-희소($K$-sparse) 하다고 말합니다. 수학적으로는 $L_0$ 노름(0이 아닌 요소의 수를 세는 함수)을 사용하여 다음과 같이 정의됩니다.

$$ \|\mathbf{s}\|_0 = K $$

실제 세계에서의 희소성

놀랍게도 자연계에 존재하는 많은 신호는 적절한 기저를 선택함으로써 희소해집니다.

이미지: 자연 이미지는 픽셀 공간에서는 희소하지 않지만, 웨이블릿 변환이나 이산 코사인 변환(DCT)을 수행하면 대부분의 고주파 성분이 0에 가까워져 희소해집니다(이것이 JPEG 압축의 원리입니다).
음성: 음성 신호는 시간 영역에서는 연속적이지만, 주파수 영역(푸리에 변환 후)에서는 소수의 주요 주파수 성분(기본 주파수와 배음)만이 큰 값을 가집니다.

압축 센싱은 이 ‘신호에 내재된 중복성’을 이용하여 샘플링 단계에서 데이터 압축을 동시에 수행해버리는 기술입니다.

3. 압축 센싱의 공식화와 관측 행렬

신호가 희소하다는 것을 전제로 할 때, 어떻게 적은 데이터에서 신호를 복원할 수 있을까요? 미지의 신호 $\mathbf{x} \in \mathbb{R}^N$ 에 대해 $M$ 번의 선형 관측을 수행한다고 가정합시다($M < N$). 관측 과정은 관측 행렬 $\mathbf{\Phi} \in \mathbb{R}^{M \times N}$ 을 사용하여 다음과 같이 표현됩니다.

$$ \mathbf{y} = \mathbf{\Phi} \mathbf{x} = \mathbf{\Phi} \mathbf{\Psi} \mathbf{s} = \mathbf{A} \mathbf{s} $$

여기서,

$\mathbf{y} \in \mathbb{R}^M$: 관측 데이터 벡터
$\mathbf{A} = \mathbf{\Phi} \mathbf{\Psi} \in \mathbb{R}^{M \times N}$: 센싱 행렬

우리의 목표는 주어진 관측 데이터 $\mathbf{y}$ 와 행렬 $\mathbf{A}$ 로부터 미지의 계수 벡터 $\mathbf{s}$(그리고 최종적으로 $\mathbf{x}$)를 복원하는 것입니다.

과소결정계 문제

그러나 여기서 수학적인 벽에 부딪힙니다. $M < N$ (방정식의 수보다 미지수의 수가 많음)이기 때문에 이 연립 방정식 $\mathbf{y} = \mathbf{A} \mathbf{s}$ 는 **과소결정계(underdetermined system)**가 되어 해가 무수히 존재하게 됩니다. 일반적인 선형대수에서는 유일한 해를 구하는 것이 불가능합니다.

여기서 “$\mathbf{s}$ 는 희소하다(0이 아닌 성분이 극히 적다)“는 사전 지식을 활용합니다. 무수히 많은 해의 후보 중에서 가장 희소한(0이 아닌 성분이 가장 적은) 해를 찾아내면, 그것이 진짜 신호일 가능성이 높을 것입니다. 이를 최적화 문제로 공식화하면 다음과 같습니다.

$$ (P_0) \quad \min_{\mathbf{s} \in \mathbb{R}^N} \|\mathbf{s}\|_0 \quad \text{subject to} \quad \mathbf{y} = \mathbf{A} \mathbf{s} $$

$L_0$ 최적화의 어려움

이상적으로는 위의 $(P_0)$ 문제를 풀면 되지만, 수학적으로 $\|\mathbf{s}\|_0$ 의 최소화 문제는 NP-난해(NP-hard) 임이 알려져 있습니다. 0이 아닌 성분의 조합을 모든 경우의 수로 조사해야 하며, 차원 $N$ 이 커지면 현대의 슈퍼컴퓨터를 동원해도 우주의 수명보다 긴 시간이 걸려버립니다.

4. $L_1$ 최적화 문제로의 완화: 캉데스와 타오의 돌파구

압축 센싱이 실용적인 기술로서 폭발적으로 보급된 이유는, 이 풀 수 없는 $L_0$ 최적화 문제를 계산 가능한 $L_1$ 최적화 문제 로 치환해도 일정한 조건 하에서는 완전히 똑같은 정답에 도달할 수 있다는 경이로운 수학적 증명이 주어졌기 때문입니다.

2004년부터 2006년까지 에마뉘엘 캉데스(Emmanuel Candès), 테렌스 타오(Terence Tao), 데이비드 도노호(David Donoho) 등은 이 이론의 견고한 기반을 다졌습니다.

$L_1$ 노름 최소화

$L_0$ 노름 대신 벡터의 각 요소의 절댓값의 합인 $L_1$ 노름을 사용합니다.

$$ \|\mathbf{s}\|_1 = \sum_{i=1}^N |s_i| $$

이로써 문제는 다음과 같이 완화(relaxation)됩니다.

$$ (P_1) \quad \min_{\mathbf{s} \in \mathbb{R}^N} \|\mathbf{s}\|_1 \quad \text{subject to} \quad \mathbf{y} = \mathbf{A} \mathbf{s} $$

$L_1$ 최소화 문제는 볼록 최적화 문제의 일종으로, 선형 계획법(Linear Programming)과 같은 기존의 고효율 알고리즘을 사용하여 다항 시간에 엄밀해를 계산할 수 있습니다.

왜 $L_1$ 인가? (기하학적 직관)

왜 $L_2$ 노름(최소제곱법)이 아니라 $L_1$ 노름일까요? 이는 기하학적으로 이해할 수 있습니다. 제약 조건 $\mathbf{y} = \mathbf{A}\mathbf{s}$ 는 고차원 공간 내에서 초평면을 형성합니다. 노름의 최소화란 원점을 중심으로 한 등고면(볼)을 부풀려가며 가장 먼저 이 초평면과 접하는 점을 찾는 조작에 해당합니다.

$L_2$ 볼 ($\|\mathbf{s}\|_2 \le R$): 형태는 매끄러운 구체입니다. 초평면과 접하는 점은 대부분의 경우 모든 좌표축에서 떨어진 장소가 되며, 결과적으로 얻어지는 해는 요소가 모두 0이 아닌 “조밀한(dense)” 벡터가 됩니다.
$L_1$ 볼 ($\|\mathbf{s}\|_1 \le R$): 형태는 다면체(마름모, 팔면체 등)이며 많은 “모서리(꼭짓점)“를 가집니다. 이 모서리는 좌표축 상에 위치해 있습니다. 초평면을 밀어붙였을 때, 높은 확률로 이 “모서리” 부분에서 접하게 됩니다. 모서리에서 접한다는 것은 다른 좌표축의 값이 0이 된다는 것을 의미하며, 결과적으로 희소한 해를 얻을 수 있는 것입니다.

RIP (Restricted Isometry Property: 제한적 등거리성)

캉데스와 타오는 $L_1$ 최소화가 $L_0$ 최소화와 일치하기 위한 충분조건으로 RIP(제한적 등거리성) 라는 개념을 도입했습니다. 센싱 행렬 $\mathbf{A}$ 가 차수 $K$ 의 RIP를 만족한다는 것은 임의의 $K$-희소 벡터 $\mathbf{s}$ 에 대해 다음 부등식이 성립하는 작은 상수 $\delta_K \in (0,1)$ 가 존재한다는 것입니다.

$$ (1 - \delta_K) \|\mathbf{s}\|_2^2 \le \|\mathbf{A}\mathbf{s}\|_2^2 \le (1 + \delta_K) \|\mathbf{s}\|_2^2 $$

직관적으로는 “행렬 $\mathbf{A}$ 가 임의의 희소 벡터의 길이를 (거의) 바꾸지 않고 보존한다"는 성질입니다. 캉데스와 타오는 $\mathbf{A}$ 가 특정한 RIP 조건을 만족하면, 노이즈가 없는 상황에서 $(P_1)$ 의 해가 $(P_0)$ 의 해와 완전히 일치함을 훌륭하게 증명했습니다.

더욱 실용적인 관점에서 관측 행렬 $\mathbf{\Phi}$ 로서 랜덤 행렬(가우스 분포나 베르누이 분포를 따르는 난수 행렬)을 사용하면 높은 확률로 RIP를 만족함이 밝혀졌습니다. 즉, “무작위로 관측하는 것"이 압축 센싱에서 가장 효율적이고 보편적인 샘플링 전략이 되는 것입니다.

필요한 관측 횟수 $M$ 은 신호의 길이 $N$ 과 희소도 $K$ 에 대해 다음과 같은 차수(order)면 충분하다는 것이 증명되어 있습니다.

$$ M \ge C \cdot K \log\left(\frac{N}{K}\right) $$

($C$ 는 상수)

이것은 샘플링 정리가 요구하는 $N$ 번의 관측에 비해 훨씬 적은 횟수($K$ 에 의존)로도 충분함을 의미합니다.

5. 압축 센싱의 응용 사례

압축 센싱 이론은 정보 공학과 물리학의 모든 분야에 혁명을 가져왔습니다.

1. MRI(자기공명영상)의 고속화

가장 성공한 상업적 응용 사례 중 하나가 MRI입니다. MRI는 강력한 자기장을 사용하여 인체의 단층 영상을 취득하지만, 데이터(k-공간이라고 불리는 주파수 영역 데이터) 수집에는 물리적인 한계가 있어 시간이 걸립니다. 소아 환자나 심장처럼 움직이는 장기를 촬영할 때 장시간 정지해 있는 것은 어렵습니다. 압축 센싱을 MRI에 응용함으로써 샘플링하는 k-공간의 데이터를 무작위로 솎아내어 스캔 시간을 기존의 몇 분의 일로 단축하는 데 성공했습니다. 현재는 지멘스나 GE 등 주요 의료기기 제조업체가 압축 센싱 기술을 표준으로 탑재한 MRI를 판매하고 있습니다.

2. 블랙홀의 촬영 (이벤트 호라이즌 망원경)

2019년, 국제 연구팀 ‘이벤트 호라이즌 망원경(EHT)‘이 인류 역사상 최초로 블랙홀 섀도우의 이미지 촬영에 성공했습니다. 지구 크기의 거대한 가상 망원경을 구축하기 위해 전 세계에 흩어져 있는 전파 망원경의 데이터를 통합(초장기선 전파 간섭계: VLBI)했지만, 지구상 망원경 배치에는 한계가 있어 관측 데이터에는 방대한 ‘틈(결측 데이터)‘이 존재했습니다. 이 듬성듬성한 데이터로부터 블랙홀 이미지를 복원하기 위해 CHIRP(Continuous High-resolution Image Reconstruction using Patch priors)라는 알고리즘이 개발되었습니다. 이 역시 우주의 이미지가 가진 희소성이나 구조적인 사전 지식을 활용한 압축 센싱의 응용이라 할 수 있습니다.

3. 단일 픽셀 카메라 (Single-Pixel Camera)

라이스 대학교(Rice University) 연구팀은 수광 소자(픽셀)를 단 하나만 가진 카메라를 개발했습니다. DMD(디지털 마이크로미러 디바이스)를 사용하여 대상물의 빛을 무작위 패턴으로 반사시키고, 그 총합을 하나의 센서로 측정합니다. 이를 수천 번 반복함으로써 수백만 픽셀의 이미지를 재구성합니다. 적외선이나 테라헤르츠파 등 다중 픽셀 센서 제조가 매우 비싼 파장대에서의 영상화에 있어 이 기술은 매우 유용합니다.

6. Python을 이용한 압축 센싱 구현 예시

이론만으로는 실감이 나지 않기 때문에 Python을 사용하여 실제로 압축 센싱 시뮬레이션을 수행해 보겠습니다. 여기서는 1차원의 희소 신호를 생성하고, 소수의 무작위 관측으로부터 $L_1$ 최적화를 사용하여 원래 신호를 복원합니다. 최적화에는 cvxpy 라이브러리를 사용합니다.

필요한 라이브러리 설치

1
pip install numpy matplotlib cvxpy

구현 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import numpy as np
import matplotlib.pyplot as plt
import cvxpy as cp

# 난수 시드 고정
np.random.seed(42)

# --- 1. 문제 설정 ---
N = 1000  # 신호의 차원 (본래 샘플링해야 할 수)
K = 50    # 희소도 (0이 아닌 요소의 수)
M = 250   # 관측 횟수 (N의 단 25%)

# --- 2. 희소한 진짜 신호 생성 ---
# 진짜 신호 x_true 생성 (초깃값은 모두 0)
x_true = np.zeros(N)
# 무작위로 K개의 인덱스를 골라 0이 아닌 값 설정 (가우스 분포)
nonzero_indices = np.random.choice(N, K, replace=False)
x_true[nonzero_indices] = np.random.randn(K)

# --- 3. 관측 과정 시뮬레이션 ---
# 무작위 가우스 관측 행렬 A (M x N) 생성
A = np.random.randn(M, N)
# 열마다 정규화 (노름을 1로 만듦)
A = A / np.linalg.norm(A, axis=0)

# 관측 데이터 y = A * x_true
y = A @ x_true

# --- 4. 압축 센싱에 의한 신호 복원 (L1 최적화) ---
# cvxpy를 사용하여 최적화 문제 정의
x_reconstruct = cp.Variable(N)
# 목적 함수: L1 노름의 최소화
objective = cp.Minimize(cp.norm(x_reconstruct, 1))
# 제약 조건: y = A * x (관측 데이터와 일치)
constraints = [A @ x_reconstruct == y]

# 문제 정의 및 풀이
prob = cp.Problem(objective, constraints)
print("최적화 계산 실행 중...")
prob.solve(solver=cp.ECOS)

# 복원된 신호
x_rec = x_reconstruct.value

# --- 5. 결과 시각화 ---
plt.figure(figsize=(12, 6))

plt.subplot(2, 1, 1)
plt.plot(x_true, label='True Signal', alpha=0.7)
plt.title(f'Original Sparse Signal (N={N}, K={K})')
plt.legend()
plt.grid(True)

plt.subplot(2, 1, 2)
plt.plot(x_rec, color='red', label='Reconstructed Signal', alpha=0.7)
plt.title(f'Reconstructed via L1 Minimization (M={M} measurements)')
plt.legend()
plt.grid(True)

plt.tight_layout()
plt.show()

# 복원 정확도 확인
error = np.linalg.norm(x_true - x_rec)
print(f"복원 오차 (L2 norm): {error:.6e}")

코드 해설

신호 생성: 차원 $N=1000$ 중에서 $K=50$ 군데만 값을 가지는(나머지는 0) 희소 벡터 x_true 를 생성합니다.
관측: 샘플링 정리에 따르면 1000번의 측정이 필요하지만, 여기서는 단 $M=250$ 번(25%)의 무작위 관측 행렬 A 를 사용하여 데이터 y 를 얻습니다.
복원: 관측 데이터 y 와 행렬 A 만을 입력으로 하고, cvxpy 를 사용하여 “$\mathbf{y} = \mathbf{A}\mathbf{x}$ 를 만족하는 것 중에서 가장 $L_1$ 노름이 작은 $\mathbf{x}$” 를 찾아냅니다.
결과: 계산이 완료되면 복원 오차는 1e-9 이하의 극히 작은 값이 되며, 불과 25%의 관측 데이터로부터 진짜 신호가 완벽하게(Exact) 복원되었음을 확인할 수 있습니다.

  flowchart LR
    X["미지의 희소 신호\nx (N차원)"] -->|"무작위 관측\n행렬 A"| Y["관측 데이터\ny (M차원, M < N)"]
    Y -->|"L1 최적화\n(볼록 최적화 알고리즘)"| X_hat["복원된 신호\nx^"]
    X -. "완전 일치 보장" .-> X_hat

7. 요약 및 향후 전망

압축 센싱은 신호 처리의 역사에서 패러다임을 근본적으로 바꾼 것이었습니다. “대량으로 측정하고 나서 버린다"가 아니라, “처음부터 필요한 만큼만 똑똑하게 측정한다"는 접근 방식은 수학의 심오한 이론(볼록 최적화, 랜덤 행렬 이론, 고차원 기하학)이 뒷받침하고 있습니다.

현재는 딥러닝과 압축 센싱을 결합한 연구가 활발히 진행되고 있습니다. 기존의 $L_1$ 최적화 알고리즘 대신, 신경망을 사용하여 더욱 빠르고 정확하게 역문제를 푸는 접근법(Deep Unfolding / Algorithm Unrolling)이 주류가 되어가고 있습니다. 이를 통해 관측 행렬의 설계 자체도 데이터 기반으로 학습하는 것이 가능해져, MRI의 추가적인 고속화나 노이즈에 강한 이미지 재구성 등에 응용이 진행되고 있습니다.

적은 정보에서 전체를 정확하게 꿰뚫어 보는 압축 센싱의 수학적 마법은 앞으로도 자율주행, IoT 센서 네트워크, 우주 탐사 등 데이터 폭발이 과제가 되는 모든 분야에서 우리에게 새로운 ‘눈’을 계속해서 제공할 것입니다.

압축 센싱: 적은 관측으로 원래 신호를 복원할 수 있는 이유

의료 영상, 천문학, 이미지 압축으로 이어지는 현대적 주제.