📂통계적분석

압축 센싱이란?

정의

$$ \mathbf{y} = \Theta \mathbf{s} $$ $\Theta \in \mathbb{R}^{n \times p}$ 에 대해 $n \ll p$ 일 때, 다시 말해 과소결정계라서 위의 행렬방정식을 만족하는 해 $\mathbf{s}$ 가 무수히 많이 존재한다고 하자. 이 행렬방정식을 만족시키는 것을 제약조건으로 가지는 최적화 문제에 대한 스파스 회귀를 압축 센싱^{compressed Sensing}이라 한다. $$ \begin{matrix} \text{Minimize} & \left\| \mathbf{s} \right\|_{0} \\ \text{subject to} & \mathbf{y} = \Theta \mathbf{s} \end{matrix} $$ 여기서 $\left\| \cdot \right\|_{0}$ 은 $0$-놈으로써, 벡터의 $0$ 이 아닌 성분의 갯수로써 정의된다.

설명

압축 센싱에서 압축은 Compressive Sensing이라 적기도 한다.

모티브

압축 센싱의 모티브는 물론 스파스 회귀 그 자체로써, 일반적인 회귀분석에서와 달리 디자인 매트릭스 $\Phi$ 를 측량 행렬^{measurement matrix}, 회귀계수의 벡터 $\mathbf{s}$ 를 시그널^signal이라 부르기도 한다¹.

위의 그림은 일반적인 행렬방정식의 풀이와 압축 센싱을 시각화한 것으로, 픽셀의 색깔은 해당 성분의 크기를 나타낸다². 색이 연할수록 $0$ 에 가깝고, 흰색은 아예 $0$ 을 의미한다. $\mathbf{s}$ 를 찾아내는 거야 어찌어찌 할 수 있더라도, 우리는 왼쪽 그림과 달리 오른쪽 그림처럼 $0$ 을 최대한 많이 포함하는 $\mathbf{s}$ 를 찾고 싶은 것이다.

행렬의 곱을 생각해보면 $\mathbf{s}$ 의 어떤 성분이 $0$ 이라는 것은 데이터를 설명하기 위해 거기에 대응되는 $\Theta$ 의 칼럼이 없이도 $\mathbf{y}$ 를 설명할 수 있다는 의미가 된다. $\mathbf{s}$ 의 $0$ 이 늘어난다는 것은 $\Theta$ 이 가로로 얇아진다는 의미에서 압축, 어떤 성분이 $0$ 이 아니라는 것은 필요한 칼럼을 감지했다는 것이므로 압축 센싱이라는 네이밍은 적절하다고 볼 수 있겠다.

어려움 ³

문제는 앞서 말했듯 그냥 $\mathbf{y} = \Theta \mathbf{s}$ 만 만족시키면 되는 게 아니라 그런 $\mathbf{s}$ 중 $\left\| \mathbf{s} \right\|_{0}$ 이 가장 작아지는 최적해 $\hat{\mathbf{s}}$ 를 찾아야한다는 것이다. 생각할 수 있는 가장 무식한 방법은 모든 경우의 수를 다 시도해보는 것, 즉 $O \left( 2^{p} \right)$ 만큼의 계산을 하는 것이고 이는 NP-하드^nP-hard한 문제다.

당연히 모든 경우의 수를 다 시도하는 것보다는 더 현명하게 문제를 풀 필요가 있고, 그 아이디어 중 하나는 $l_{0}$-놈 $\left\| \cdot \right\|_{0}$ 대신 다른 놈을 사용해보는 것이다. 우선은 가장 만만한 $l_{2}$-놈과 $l_{1}$-놈을 생각해보자.

압축 센싱 문제를 위 그림처럼 기하적으로 생각해보자면, 직선의 방정식 $\mathbf{y} = \Theta \mathbf{s}$ 를 찾되 오른쪽처럼 하나라도 더 많은 성분들을 $0$ 으로 만드는 해를 찾아야 하는 것이다. 이는 라쏘 회귀가 리지회귀와 어떻게 다른지를 기하적으로 설명하는 것과 비슷하다. 적어도 이 둘만 봤을 땐 $l_{2}$-놈보다는 $l_{1}$-놈이 압축 센싱에 더 적합해 보이는데, 그렇다고 $l_{0}$-놈을 타당한 정당화 없이 $l_{1}$-놈으로 대체할 수도 없는 노릇이다.

한편 여러가지 $q \ge 0$ 에 대해 $l_{q}$-놈을 시각화해서 보면, 한 눈에 보아도 대충 $q \le 1$ 일 때 $\left\| \mathbf{s} \right\|_{q}$ 은 $\left\| \mathbf{s} \right\|_{0}$ 과 비슷할 것 같은 느낌이 든다. 굳이 모든 $0 \le q \le 1$ 을 고려할 건 없고, 딱 $l_{0}$-놈과 $l_{1}$-놈 사이의 차이만 잘 좁혀내면 압축 센싱의 문제는 훨씬 수월하게 풀릴 것처럼 보인다.

실제로 압축 센싱 문제는 $\Theta$ 가 제한된 등거리 조건를 따를 때 쉽게 풀 수 있음이 증명되었고, 독보적인 입지를 가진 메소드로써 정착해 2023년 현재까지도 다방면에 응용되고 있다.