📂統計的分析

圧縮センシングとは何か？

定義

$$\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}$を満たせばいいわけではなく、その中で$\left\| \mathbf{s} \right\|_{0}$が最も小さくなる最適解$\hat{\mathbf{s}}$を見つけなければならないということだ。考えられる最も単純な方法は、すべての場合を試すこと、つまり$O \left( 2^{p} \right)$だけの計算をすることで、これはNPハードな問題である。

もちろん、すべての場合を試すよりも、もっと賢く問題を解く必要があるが、そのアイディアの一つは$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年現在でも様々な分野に応用されている独自の地位を確立している。