섀넌-나이키스트 표본화 정리(Shannon-Nyquist sampling theorem)에 의하면, 신호의 최대 주파수가 B일 때 이를 온전히 재구성하려면 2B 이상의 주파수로 표본을 추출해야 한다.그런데 우리가 보는 대부분의 신호는 큰 패턴이 중요한 역할을 하므로 주파수 밀도 측면에서 희박(sparse)하고, 이를 이용하면 섀넌-나이키스트 표본화 정리가 요구하는 것보다 적은 수의 표본으로도 신호를 재구성할 수 있다. 이러한 아이디어는 Candès, Romberg, and Tao (2006)에 의해 정식화되었고 압축 센싱(compressed sensing)이라 불리고 있다.

길이 $N$인 '희박한' 신호 $\mathbf{x}$가 미지수로서 있다. $k\times N$의 '관찰' 행렬 $A$를 곱하자. 이 행렬의 원소는 난수로 주어져 있고 $k \ll N$이라고 가정한다. 그 곱의 결과로 $k$ 차원 벡터 $\mathbf{b} = A \mathbf{x}$를 관찰 결과로 가지고 있다.

$A$와 $\mathbf{b}$만을 가지고 미지수 $\mathbf{x}$를 복원하는 것은 불가능해 보인다. $\mathbf{b}=A\mathbf{x}$를 만족하는 $\mathbf{x}$가 무수히 많기 때문이다. 하지만 그러한 $\mathbf{x}$ 중에서 가장 '희박한' 것, 구체적으로는 $\sum_i |x_i|$를 최소화하는 $\mathbf{x}$를 택하면 원래의 $\mathbf{x}$를 상당히 잘 복원해낼 수 있다.

• https://www.codeproject.com/Articles/852910/Compressed-Sensing-Intro-Tutorial-w-Matlab
• http://www.pyrunner.com/weblog/2016/05/26/compressed-sensing-python/
• https://dilawarnotes.wordpress.com/2017/09/06/compressed-sensing-a-python-demo/