圧縮センシング（少ない測定から画像を戻す）

頭の式の$x$は長さ$n$の未知のベクトル、$y$は$m$回の測定の結果、$A$は$m$行$n$列の行列で、$m<n$とする。$\Vert x{\Vert }_1=|x_1|+\cdots +|x_n|$はL1ノルムと読み、絶対値の和を表す。$\Vert x{\Vert }_2$はふつうの長さで、L2ノルムと呼ぶ。本当の信号を$x^0$とし、0でない成分が$k$個以下の信号を$k$スパースと呼ぶ。

直観は図形にある。平面で$|x_1|+|x_2|=r$を満たす点はひし形を作り、$x_1^2+x_2^2=r^2$は円を作る。$r$を0から大きくしていくと、円は直線に接した点で止まり、その点はふつう軸の上にない。ひし形は、ほとんどの傾きで角から触れる。角は座標軸の上にあるので、片方の成分が0になる。

つまみの$a$を1にすると、ひし形の辺が直線と重なり、解は1つに決まらない。高い次元でも、L1ノルムの球の尖った部分は0の多い点に集まる。では、式ではどう言えるのか。2乗の和は0を作らず、絶対値の和は条件がそろえば$x^0$に戻る。

1. 測定が同じになる解は、$x^0$に$A$の零空間のベクトル$h$を足したものである

   $$x=x^0+h,Ah=0$$

2. 2乗の和が最小の解$\hat{x}$は、どの$h$を足しても長くならない。$\Vert \hat{x}+\epsilon h{\Vert }_2^2$を$\epsilon$で微分すると

   $$⟨\hat{x},h⟩=0$$

3. 零空間に直交するベクトルは、$A$の行の1次結合で書ける。$a_i$を$A$の第$i$列とすると

   $$\hat{x}=A^{\mathsf{T}}w,{\hat{x}}_i=⟨a_i,w⟩$$

4. ${\hat{x}}_i$が0になるのは、$a_i$と$w$がたまたま直交するときだけである。$A$の成分を正規乱数で選ぶと、その確率は0である

   $${\hat{x}}_i\ne 0(i=1,\dots ,n)$$

5. 絶対値の和に移る。$x^0$の0でない場所を$S$、残りを$S^c$として$h$を2つに分ける。$S^c$では$x^0$が0なので

   $$\Vert x^0+h{\Vert }_1=\Vert x^0+h_S{\Vert }_1+\Vert h_{S^c}{\Vert }_1$$

6. 0でない場所の減り方を、三角不等式で抑える

   $$\Vert x^0+h_S{\Vert }_1\ge \Vert x^0{\Vert }_1-\Vert h_S{\Vert }_1$$

7. 2つを合わせる

   $$\Vert x^0+h{\Vert }_1\ge \Vert x^0{\Vert }_1+\Vert h_{S^c}{\Vert }_1-\Vert h_S{\Vert }_1$$

8. 零空間のどのベクトルも少数の場所に固まっていなければ、右辺の差は正になり、$x^0$が唯一の最小解になる。これを零空間性質と呼ぶ

   $$\Vert h_S{\Vert }_1<\Vert h_{S^c}{\Vert }_1(Ah=0,h\ne 0,|S|\le k)$$

9. 逆に、ある$h$と$S$で不等式が破れると、$u=h_S$と$v=-h_{S^c}$は同じ測定を与え、$v$の絶対値の和は$u$より大きくない。$k$スパースな$u$が、唯一の最小解にならない

   $$Au=Av,\Vert v{\Vert }_1\le \Vert u{\Vert }_1$$

つまり「すべての$k$スパースな信号が戻る」ことと零空間性質は同じである。では、零空間性質を保ったまま、$m$はどこまで減らせるのだろうか。

そこでカンデスとタオが立てた物差しが、制限等長性（RIP）である。$2k$スパースなベクトル$z$のどれについても、$A$が長さをほぼ保つという条件を置く。

$\delta$が小さければ、少数の場所に固まった$h$は$Ah$が0にならず、零空間に入れない。トニー・カイとアンル・チャンは2014年に、$\delta <1/\sqrt{2}$ならすべての$k$スパースな信号が戻り、この値を超えると保証できなくなることを示した。測定に大きさ$\epsilon$までの雑音が混じるときも、制約を$\Vert Ax-y{\Vert }_2\le \epsilon$に緩めて解けば、誤差は$\epsilon$の定数倍に収まる。

でたらめな行列がこの条件を満たす理由は、数え上げでつかめる。たとえば$A$の成分を平均0、分散$1/m$の正規乱数にすると、1本のベクトル$z$について$\Vert Az{\Vert }_2^2$は$m$個の独立な項の和になる。$\Vert z{\Vert }_2^2$から外れる確率は$e^{-cm}$の速さで減り、定数$c$は$\delta$で決まる。0でない場所の選び方は$\left(\genfrac{}{}{0ex}{}{n}{2k}\right)$通りあり、それぞれの部分空間を$(12/\delta {)}^{2k}$個の点で代表させると、どこかで外れる確率は次の値を超えない。

対数をとると、これを1より小さくするには$m\ge Ck\log (n/k)$で足りる。完全な証明は、バラニュークらの2008年の論文にある。この$C$は十分条件を保証するための定数で、実際に何回要るかはあとの図で確かめる。

$\log (n/k)$の正体は、場所を言うための情報量である。$\left(\genfrac{}{}{0ex}{}{n}{k}\right)$通りから1つを指すには${\log }_2\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ビット要り、シャノンのエントロピー$H$を使うと、およそ$nH(k/n)$ビットになる。大きさは$k{\log }_2(n/k)$の程度である。

もっとも、場所を総当たりで試せば測定はもっと少なくて済む。長さ$N$が素数のフーリエ測定なら、0でない値の2倍の$|\Omega |$で信号は1つに決まる。ただしタオの2007年の解説にある200万個から10万個を選ぶ例で、組み合わせはおよそ10の17万乗通りになる。だから絶対値の和に置き換え、線形計画法で解ける代わりに$\log$の分だけ測定を増やす。