📂統計的分析

均等不確定性原理: 限られた等距離条件

定義

$$\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)$$

これは、数式的には2つの問題が同一であることを意味し、統計学者の用語か信号解析者の用語かの違いで説明できる部分である。⁷ 実践的な領域では、これらが事実上同じであると認識しておけば良いが、これまでの議論で見たように、これらが同一になるためには明確に条件があることを理解する必要がある。もう一度まとめてみると、以下のようになる：

• 制限等距離条件の下で、圧縮センシングはラッソ回帰を通じて実行^performすることができる。
  • しかし、ラッソ回帰が圧縮センシングを行う唯一の方法ではない。
• 厳密に言えば、両者は異なる。
  • しかし、厳密に区別する必要はない。