📂통계적분석

균등 불확정성 원리: 제한된 등거리 조건

정의

$$ \begin{align*} \left\| \mathbf{v} \right\|_{0} :=& \left| \operatorname{supp} \mathbf{v} \right| \\ =& \operatorname{card} \left\{ k : \left( \mathbf{v} \right) _{k} \ne 0 \right\} \end{align*} $$ 벡터공간 $V$ 의 벡터 $\mathbf{v} \in V$ 에 대해 $l_{0}$-놈 $\left\| \mathbf{v} \right\|_{0} : V \to \mathbb{Z}$ 을 위와 같이 서포트의 카디널러티, 즉 $0$ 이 아닌 성분의 수로써 정의하자. $\left\| \cdot \right\|_{1}$ 는 $l_{1}$-놈, $\left\| \cdot \right\|_{2}$ 는 $l_{2}$-놈이다.

DFT에서의 불확정성 원리 ¹

길이가 $N \in \mathbb{N}$ 인 유한 벡터 $x \in \mathbb{C}^{N}$ 의 이산푸리에변환을 $\hat{x}$ 라고 나타내자. 다음의 진술을 이산푸리에변환에 대한 불확정성 원리라고 부른다. $$ \left\| x \right\|_{0} \left\| \hat{x} \right\|_{0} \ge N $$

제한된 등거리 조건 ²

벡터 $\mathbf{s} \in \mathbb{R}^{p}$ 의 성분과 행렬 $\Theta \in \mathbb{R}^{n \times p}$ 의 칼럼 중 $T \subset \left\{ 1 , \cdots , p \right\}$ 째에 해당하는 것만 남긴 것을 각각 $\mathbf{s}_{T} \in \mathbb{R}^{\left| T \right|}$, $\Theta_{T} \in \mathbb{R}^{n \times \left| T \right|}$ 와 같이 나타내자. 자연수 $S \in \mathbb{N}$ 가 주어져 있을 때, $\left| T \right| \le S$ 를 만족하는 모든 $T$ 와 $\mathbf{s} \in \mathbb{R}^{p}$ 에 대해 $S$-제한된 등거리 상수^{$S$-restricted Isometry Constant} $\delta_{S}$ 가 존재해서 $$ \left( 1 - \delta_{S} \right) \left\| \mathbf{s}_{T} \right\|_{2}^{2} \le \left\| \Theta_{T} \mathbf{s}_{T} \right\|_{2}^{2} \le \left( 1 + \delta_{S} \right) \left\| \mathbf{s}_{T} \right\|_{2}^{2} $$ 을 성립시키면 $\Theta$ 가 제한된 등거리 가정^{restricted Isometry Hypothesis} 혹은 균등 불확정성 원리^{uniform Uncertainty Principle}를 따른다고 한다.

설명

압축 센싱

압축 센싱으로 널리 알려진 최적화 문제를 흔히 다음과 같이 기술하곤 한다. $$ \begin{matrix} \text{Minimize} & \left\| \mathbf{s} \right\|_{0} \\ \text{subject to} & \mathbf{y} = \Theta \mathbf{s} \end{matrix} $$ 푸리에 해석에서의 하이젠베르크 부등식은 특히 양자역학에서 하이젠베르크의 불확정성 원리로도 알려져 있는데, 압축 센싱의 선구자인 도노호^donoho는 1989년 시그널 복원^{signal Recovery}을 키워드로 발표한 논문의 5번째 정리에서 해가 유일하게 존재하는 조건, 9번째 정리에서 $\mathbf{y} = \Theta \mathbf{s}$ 일 때 $$ \argmin \left\| \mathbf{s} \right\|_{0} = \argmin \left\| \mathbf{s} \right\|_{1} $$ 인 조건을 제시할 때 언급되었다³. 다시 말해 원래의 문제를 $$ \begin{matrix} \text{Minimize} & \left\| \mathbf{s} \right\|_{1} \\ \text{subject to} & \mathbf{y} = \Theta \mathbf{s} \end{matrix} $$ 다음과 같이 완화한 것인데, 칸데스^candès와 타오^tao는 여기서 한발 더 나아가 $\Theta$ 가 $S$-제한된 등거리 가정을 따른다는 조건 하에서 해 $\mathbf{s}^{\ast}$ 가 충분히 스파스 할 때, $$ \begin{matrix} \text{Minimize} & \left\| \mathbf{s} \right\|_{1} \\ \text{subject to} & \left\| \mathbf{y} - \Theta \mathbf{s} \right\|_{2} \le \varepsilon \end{matrix} $$ 의 최적해 $\hat{\mathbf{s}}$ 는 어떤 상수 $C > 0$ 에 대해 다음의 부등식을 만족시킴을 보였다. $$ \left\| \hat{\mathbf{s}} - \mathbf{s}^{\ast} \right\|_{2} \le C \varepsilon $$ 이는 다시 말해 NP-하드^nP-hard한 문제인 압축 센싱이 쉽게 풀리는 조건을 제시한 것으로, 현재는 이렇게 밝혀진 조건을 근거로 아주 다양한 분야에서 폭넓게 사용되고 있다.

문제는 푸리에해석과 데이터과학을 동시에 잘 하기가 어렵다보니 불확정성 원리와 제한된 등거리 성질 사이의 관계를 이해하기 어렵다는 것이다. 심지어 도노호의 논문에서는 불확정성 원리라는 워딩만 계속 밀고 나가서 읽는 것 자체가 무척 곤혹스러운데, 그나마 칸데스와 타오 등은 여러 논문에서 비교적 수식적으로 이해하기 쉽게 ‘행렬과 제한된 등거리 조건’으로 설명하고⁴ 이후에 이들을 인용한 다른 논문에서도 비슷한 식으로 설명이 진행되는 편이다.⁵

제한된 등거리 성질과 칼럼별 정규화

우리는 여기서 한 발 더 물러서서, 실전적인 측면에서 $\mathbf{y} = \Theta \mathbf{s}$ 와 같은 꼴의 행렬방정식이 주어졌을 때의 스파스 회귀에서 $\Theta$ 를 칼럼 별로 노멀라이즈^normalize하는 이유라도 직관적으로 납득해보려 한다.

이제와서 다시 제한된 등거리 조건에서 제시된 부등식 $$ \left( 1 - \delta_{S} \right) \left\| \mathbf{s}_{T} \right\|_{2}^{2} \le \left\| \Theta_{T} \mathbf{s}_{T} \right\|_{2}^{2} \le \left( 1 + \delta_{S} \right) \left\| \mathbf{s}_{T} \right\|_{2}^{2} $$ 을 다시 살펴보면, 이는 선형대수에서 배우는 놈의 동치에서 나오는 수식과 유사한 것을 알 수 있다.

놈의 동치: 벡터공간 $V$ 상에서 정의된 두 놈 $\left\| \cdot \right\|_{\alpha}, \left\| \cdot \right\|_{\beta}$과 임의의 벡터 $\mathbf{v} \in V$ 에 대해 $$ c \left\| \mathbf{v} \right\|_{\alpha} \le \left\| \mathbf{v} \right\|_{\beta} \le C \left\| \mathbf{v} \right\|_{\alpha} $$ 를 만족하는 상수 $c , C >0$ 이 존재하면 두 놈은 서로 동치라 정의한다.

그런데 도노호, 칸데스, 타오의 결과들이 쉽게 말해 $\argmin \left\| \cdot \right\|_{1}$ 의 해가 $\argmin \left\| \cdot \right\|_{0}$ 의 해이기도 하다는 것이고, 이러한 의미에서 제한된 등거리 조건과 같은 수식이 나오는 것은 직관적으로 보았을 때 상당히 연관이 있어보인다. 물론 $\left\| \cdot \right\|_{?} = \left\| \Theta_{T} \cdot \right\|_{2}$ 이 정말로 놈인지 체크해볼 수도 있겠지만 당장은 넘어가고, 다음은 힐베르트 공간의 타이트 프레임에 대한 이야기다.

힐베르트 공간의 프레임: 힐베르트 공간 $H$의 시퀀스 $\left\{ \mathbf{v}_{k} \right\}_{k \in \mathbb{N}}$에 대해 다음을 만족하는 $A,B > 0$이 존재하면 $\left\{ \mathbf{v}_{k} \right\}_{k \in \mathbb{N}}$ 을 프레임^frame이라 부르고, 특히 $A = B$일 때 이 프레임이 타이트^tight하다고 말한다. $$ A \left\| \mathbf{v} \right\|^{2} \le \sum_{k \in \mathbb{N}} \left| \left\langle \mathbf{v} , \mathbf{v}_{k} \right\rangle \right|^{2} \le B \left\| \mathbf{v} \right\|^{2} \qquad , \forall \mathbf{v} \in H $$ 특히 $\left\{ \mathbf{v}_{k} \right\}_{k \in \mathbb{N}}$이 $H$의 정규직교 기저면 $A=B=1$인 타이트 프레임인 것과 동치다.

정규직교기저의 동치조건: $H$ 가 힐베르트공간이라고 하자. $H$ 의 정규직교 시스템 $\left\{ \mathbf{e}_{k} \right\}_{k \in \mathbb{N}} \subset H$ 에 대해 다음은 모두 동치다.

• (i): $\left\{ \mathbf{e}_{k} \right\}_{k \in \mathbb{N}} \subset H$ 는 $H$ 의 정규직교 기저다.
• (iv): 모든 $\mathbf{x}\in H$ 에 대해 $$ \sum_{k \in \mathbb{N}} \left| \langle \mathbf{x}, \mathbf{e}_{k} \rangle \right|^{2} = \left\| \mathbf{x}\right\|^{2} $$

프레임이 $A = B = 1$ 이 된다는 것은 $\left\| \Theta_{T} \mathbf{s}_{T} \right\|_{2} \approx \left\| \mathbf{s}_{T} \right\|$, 혹은 어떤 작은 $\delta > 0$ 에 대해 조금 느슨하게 $$ 1 - \delta = A \approx 1 \approx B = 1 + \delta $$ 이 성립한다는 것은 $\Theta_{T}$ 가 ‘완벽하지는 않지만’ 타이트한 프레임을 이룬다는 것이고 그 정규직교성 역시 ‘완벽하지는 않지만’ 필요충분조건으로써 있을 것이라 짐작할 수 있다. 이에 따라 실제 계산에 임할 땐 행렬의 각 칼럼 제곱합이 $1$ 이 되도록 나눠줄 때도 있으며, 이 때 칸데스와 타오의 논문이 인용되기도 한다. ⁶

라쏘와의 관계

$$ \begin{matrix} \text{Minimize} & \left\| \mathbf{s} \right\|_{1} \\ \text{subject to} & \left\| \mathbf{y} - \Theta \mathbf{s} \right\|_{2} \le \varepsilon \end{matrix} $$

위와 같이 압축 센싱은 제한된 등거리 조건 하에서 라그랑주 승수법에 따라 다음의 최적해를 구하는 최적화 문제로 바꿔 적을 수 있다. $$ \argmin \left\| \mathbf{s} \right\|_{1} + \lambda \left\| \mathbf{y} - \Theta \mathbf{s} \right\|_{2} $$

한편 라쏘회귀는 다음과 같은 최적화 문제를 말한다.

라쏘 회귀: 다음의 최적화 문제를 BPDN^{basis Pursuit Denoising}라 하고, BPDN을 푸는 것을 라쏘^{lASSO, Least Absolute Shrinkage and Selection Operator} 혹은 라쏘 회귀^{lASSO Regression}라고 한다. $$ \argmin_{\beta} \left( {{ 1 } \over { 2 }} \left\| Y - X \beta \right\|_{2}^{2} + \lambda \left\| \beta \right\|_{1} \right) $$

이는 수식적으로 두 문제가 서로 같다는 것이고, 통계학자의 용어인가 신호 분석가의 용어인가의 차이로 설명할 수도 있는 부분이긴 하다. ⁷ 실전적인 영역에선 이들이 사실 상 같다는 정도로 알고 넘어가도 되는데, 이제까지의 논의에서 보았듯 이들이 같아지기 위해서는 엄연히 조건이 있다는 것을 숙지해야한다. 다시 한 번 요약해서 적어보면 다음과 같다:

• 제한된 등거리 조건 하에서 압축 센싱은 라쏘 회귀를 통해 수행^perform 할 수 있다.
  • 그러나 라쏘 회귀만이 압축 센싱을 하는 유일한 방법은 아니다.
• 엄밀히 말해 둘은 다르다.
  • 그러나 엄밀하게 구분할 일이 없다.