圧縮センシング(compressed sensing)とは、0 でない成分が $s$ 個以下のベクトル $x\in\mathbb{R}^d$ を、$d$ より少ない $m$ 個の 1 次式の値 $y=Ax$ から、$Av=y$ の下で $\ell^1$ ノルムを最小にすること(線形計画問題)で復元する方法で、撮像などで測定を減らすのに使う。雑音のない測定で全ての $s$ 疎なベクトルが復元されることは、$A$ の核の零でないベクトルが $s$ 個以下の成分に $\ell^1$ ノルムの半分以上を集めないこと(零空間の性質)と同値である。位数 $2s$ の制限等長定数が $\sqrt2-1$ より小さければ、疎でない $x$ でも誤差は最良 $s$ 項近似の誤差で抑えられ、成分が独立な Gauss 分布の行列は $m$ が $s\log d$ に比例する程度で高い確率でこの条件を満たす。
圧縮センシング(compressed sensing)は、未知のベクトル $x\in\mathbb{R}^d$ を、$d$ より少ない $m$ 個の 1 次式の値 $y=Ax$($A$ は $m\times d$ 行列)から復元する方法である。$m< d$ なので連立 1 次方程式 $Av=y$ の解は無数にあり、一般には $x$ を決められない。しかし $x$ の 0 でない成分が少ない(疎 である)と分かっていれば、条件を満たす行列 $A$ について、$\ell^1$ ノルム
$$
\lvert v\rvert_1=\sum_{i=1}^d\lvert v_i\rvert
$$
を $Av=y$ の下で最小にする $v$ が $x$ に一致する。この最小化は 線形計画法 の問題に書き直せるので、多項式時間で解ける。
この記事では、復元が成り立つための必要十分条件(零空間の性質)と、計算しやすい十分条件(制限等長性、RIP)による誤差の評価を証明する。Gauss 乱数の行列が高い確率で RIP を満たし、$m$ が $s\log d$ 程度で足りることは主張として述べる。画像の撮像、医用画像(MRI)などで、測定の回数を減らすのに使われる。
$v\in\mathbb{R}^d$ の 台 を $\operatorname{supp}v=\{i\mid v_i\ne0\}$、その個数を $\lvert v\rvert_0$ と書く。$\lvert v\rvert_0\le s$ のとき $v$ は $s$ 疎 であるという。$S\subset\{1,\dots,d\}$ に対し $v_S$ は、$S$ の上で $v$ と等しく外で $0$ のベクトル、$S^c$ は $S$ の補集合である。$\lvert v\rvert_2$ は Euclid ノルムである。
$A\in\mathbb{R}^{m\times d}$、$y\in\mathbb{R}^m$ に対し、問題
$$
\text{最小化 }\lvert v\rvert_1\qquad\text{条件 }Av=y
$$
を $\ell^1$ 最小化(basis pursuit)という。$x\in\mathbb{R}^d$ に対し $\sigma_s(x)_1=\min\{\lvert x-z\rvert_1\mid z\text{ は }s\text{ 疎}\}$ とおく。最小値は $x$ の絶対値の大きい $s$ 個の成分を残したベクトル $x_s$ でとられ、$\sigma_s(x)_1$ は残りの成分の絶対値の和である。
$\delta_s$ は、$s$ 個以下の列を選んだ部分行列 $A_S$ の全てについて、$A_S^{\mathsf T}A_S$ の固有値が $[1-\delta_s,1+\delta_s]$ に入るような最小の数である。$s$ が増えると $\delta_s$ は増える(減らない)。
この記事の結論を使える条件をまとめる。
次は同値である。
2 を仮定し、$x,z$ を $s$ 疎で $Az=Ax$ とする。$h=x-z$ は $2s$ 疎で $Ah=0$ である。$h$ の台の列は 1 次独立なので $h=0$ である。逆に 2 が成り立たなければ、$2s$ 個以下の列の非自明な 1 次関係があり、$2s$ 疎な $h\ne0$ で $Ah=0$ となるものがある。$h$ の台を $s$ 個以下ずつの 2 つに分けて $h=u-w$($u,w$ は $s$ 疎、$u\ne w$)と書くと $Au=Aw$ で、1 が成り立たない。$\square$
$2s\le d$ で、全ての $s$ 疎なベクトルが $Ax$ から決まるなら $m\ge2s$ である。
$2s$ 個の列は $\mathbb{R}^m$ のベクトルなので、$m< 2s$ なら 1 次従属である。prop-cs-spark の 1 は「$\lvert v\rvert_0$ を最小にする解」として $x$ が決まることを言っているが、$\lvert v\rvert_0$ の最小化は台の候補を全て試す組合せの問題である。そこで $\lvert\cdot\rvert_0$ を凸な $\lvert\cdot\rvert_1$ に替える。
次は同値である。
2 ⇒ 1:$x$ を $s$ 疎、$S=\operatorname{supp}x$ とする。$Av=Ax$ で $v\ne x$ なら $h=v-x\ne0$、$Ah=0$ である。$x$ は $S^c$ で $0$ なので
$$
\lvert v\rvert_1=\lvert x_S+h_S\rvert_1+\lvert h_{S^c}\rvert_1\ge\lvert x\rvert_1-\lvert h_S\rvert_1+\lvert h_{S^c}\rvert_1>\lvert x\rvert_1
$$
である。最後の不等号が NSP である。
1 ⇒ 2:$h\ne0$、$Ah=0$、$\lvert S\rvert\le s$ とする。$x=h_S$ は $s$ 疎で、$Ah=0$ から $A(-h_{S^c})=Ah_S$ である。$h\ne0$ なので $-h_{S^c}\ne h_S$ で、1 により $\lvert h_S\rvert_1< \lvert-h_{S^c}\rvert_1$ である。$\square$
NSP は必要十分だが、全ての $h\in\ker A$ を調べる必要があり、一般には確かめにくい。次の制限等長定数は、部分行列の固有値で決まる量である。
$I,J$ が交わらず $\lvert I\rvert+\lvert J\rvert\le2s$ で、$u,w$ の台がそれぞれ $I,J$ に入るとき
$$
\lvert\langle Au,Aw\rangle\rvert\le\delta_{2s}\lvert u\rvert_2\lvert w\rvert_2
$$
である。
$\lvert u\rvert_2=\lvert w\rvert_2=1$ の場合を示せばよい。$u\pm w$ は $2s$ 疎で、台が交わらないので $\lvert u\pm w\rvert_2^2=2$ である。
$$
\langle Au,Aw\rangle=\frac14\bigl(\lvert A(u+w)\rvert_2^2-\lvert A(u-w)\rvert_2^2\bigr)
$$
に $\delta_{2s}$ の定義を当てると、右辺は $\frac14\bigl(2(1+\delta_{2s})-2(1-\delta_{2s})\bigr)=\delta_{2s}$ 以下、$-\delta_{2s}$ 以上である。$\square$
$\delta=\delta_{2s}<\sqrt2-1$ とし、$\rho=\dfrac{\sqrt2\,\delta}{1-\delta}$ とおく。任意の $x\in\mathbb{R}^d$ について、$y=Ax$ の $\ell^1$ 最小化の任意の最小点 $x^\star$ は
$$
\lvert x^\star-x\rvert_2\le\frac{2(1+\rho)}{1-\rho}\cdot\frac{\sigma_s(x)_1}{\sqrt s}
$$
を満たす。特に $x$ が $s$ 疎なら $x^\star=x$ であり、最小点はただ 1 つである。
$\delta<\sqrt2-1=\frac1{1+\sqrt2}$ は $\rho<1$ と同値である。
$h=x^\star-x$、$\sigma=\sigma_s(x)_1$ とする。添字を $s$ 個ずつの塊に分ける。$T_0$ は $\lvert x_i\rvert$ の大きい $s$ 個の添字、$T_1$ は $T_0^c$ の中で $\lvert h_i\rvert$ の大きい $s$ 個、$T_2$ は残りの中で $\lvert h_i\rvert$ の大きい $s$ 個、と続ける(最後の塊は $s$ 個より少なくてよい)。$T_{01}=T_0\cup T_1$ とおく。$\lvert x_{T_0^c}\rvert_1=\sigma$ である。
段 1:錐の条件。 $x^\star$ は最小点で $x$ は条件を満たすので、$\lvert x\rvert_1\ge\lvert x+h\rvert_1$ である。三角不等式から
$$
\lvert x\rvert_1\ge\lvert x_{T_0}\rvert_1-\lvert h_{T_0}\rvert_1+\lvert h_{T_0^c}\rvert_1-\lvert x_{T_0^c}\rvert_1
$$
で、$\lvert x\rvert_1=\lvert x_{T_0}\rvert_1+\sigma$ を使うと
$$
\lvert h_{T_0^c}\rvert_1\le\lvert h_{T_0}\rvert_1+2\sigma
$$
である。この段では RIP を使わない。
段 2:遠い塊の和。 $j\ge2$ のとき、$T_j$ の成分の絶対値は $T_{j-1}$ のどの成分の絶対値以下でもあるので、$T_{j-1}$ の平均 $\lvert h_{T_{j-1}}\rvert_1/s$ 以下である。よって $\lvert h_{T_j}\rvert_2\le\sqrt s\cdot\lvert h_{T_{j-1}}\rvert_1/s$ で、$j\ge2$ について足すと
$$
\sum_{j\ge2}\lvert h_{T_j}\rvert_2\le\frac{\lvert h_{T_0^c}\rvert_1}{\sqrt s}\le\frac{\lvert h_{T_0}\rvert_1+2\sigma}{\sqrt s}\le\lvert h_{T_0}\rvert_2+\frac{2\sigma}{\sqrt s}
$$
である。最後は Cauchy–Schwarz の不等式 $\lvert h_{T_0}\rvert_1\le\sqrt s\lvert h_{T_0}\rvert_2$ による。
段 3:近い塊を RIP で抑える。 $Ah=Ax^\star-Ax=0$ なので $Ah_{T_{01}}=-\sum_{j\ge2}Ah_{T_j}$ である。$h_{T_{01}}$ は $2s$ 疎なので
$$
(1-\delta)\lvert h_{T_{01}}\rvert_2^2\le\lvert Ah_{T_{01}}\rvert_2^2=-\sum_{j\ge2}\bigl(\langle Ah_{T_0},Ah_{T_j}\rangle+\langle Ah_{T_1},Ah_{T_j}\rangle\bigr)
$$
である。lem-cs-orth と $\lvert h_{T_0}\rvert_2+\lvert h_{T_1}\rvert_2\le\sqrt2\lvert h_{T_{01}}\rvert_2$ から、右辺は $\sqrt2\delta\lvert h_{T_{01}}\rvert_2\sum_{j\ge2}\lvert h_{T_j}\rvert_2$ 以下である。$h_{T_{01}}\ne0$ なら割って、段 2 の 2 番目の不等式までを使うと
$$
\lvert h_{T_{01}}\rvert_2\le\rho\,\frac{\lvert h_{T_0}\rvert_1+2\sigma}{\sqrt s}\le\rho\lvert h_{T_{01}}\rvert_2+\frac{2\rho\sigma}{\sqrt s}
$$
である($\lvert h_{T_0}\rvert_1\le\sqrt s\lvert h_{T_0}\rvert_2\le\sqrt s\lvert h_{T_{01}}\rvert_2$)。$\rho<1$ なので $\lvert h_{T_{01}}\rvert_2\le\frac{2\rho}{1-\rho}\cdot\frac{\sigma}{\sqrt s}$ で、$h_{T_{01}}=0$ のときも成り立つ。
段 4:合わせる。 段 2 から $\lvert h_{T_{01}^c}\rvert_2\le\sum_{j\ge2}\lvert h_{T_j}\rvert_2\le\lvert h_{T_{01}}\rvert_2+\frac{2\sigma}{\sqrt s}$ なので
$$
\lvert h\rvert_2\le\lvert h_{T_{01}}\rvert_2+\lvert h_{T_{01}^c}\rvert_2\le2\lvert h_{T_{01}}\rvert_2+\frac{2\sigma}{\sqrt s}\le\Bigl(\frac{4\rho}{1-\rho}+2\Bigr)\frac{\sigma}{\sqrt s}=\frac{2(1+\rho)}{1-\rho}\cdot\frac{\sigma}{\sqrt s}
$$
である。$x$ が $s$ 疎なら $\sigma=0$ で $h=0$ である。$\square$
証明は SSBD14 Theorem 23.8 の証明(pp. 333–335、Candès による)に従った。段 1・2 は $\ell^1$ の最小性だけ、段 3 は RIP だけを使っている。
$\delta_s$ を定義どおりに計算するには、$\binom ds$ 個の部分行列の固有値を全て調べる必要がある。小さい行列では次の評価が使える。
$A$ の列 $a_1,\dots,a_d$ が全て長さ $1$ のとき、$\mu=\max_{i\ne j}\lvert\langle a_i,a_j\rangle\rvert$(相互コヒーレンス)とおくと $\delta_s\le(s-1)\mu$ である。
$\lvert S\rvert\le s$ とすると、$G=A_S^{\mathsf T}A_S$ の対角成分は $\lvert a_i\rvert_2^2=1$、非対角成分の絶対値は $\mu$ 以下である。Gershgorinの円板定理 により、$G$ の固有値は $\lvert\lambda-1\rvert\le(\lvert S\rvert-1)\mu\le(s-1)\mu$ を満たす。$\lvert A_Sv\rvert_2^2=v^{\mathsf T}Gv$ は最小・最大の固有値の $\lvert v\rvert_2^2$ 倍の間にある。$\square$
したがって $(2s-1)\mu<\sqrt2-1$ なら thm-cs-rip の仮定が成り立つ。一方 $\mu\ge\sqrt{\frac{d-m}{m(d-1)}}$(Welch の下界)なので、$d\ge2m$ ならこの評価で保証できる $s$ は $\sqrt m$ 程度にとどまる。$m$ を $s$ に比例する大きさにできるのは、次の乱数の行列である。
$\varepsilon,\eta\in(0,1)$、$1\le s\le d$ とし、
$$
m\ge\frac{100\,s\log\bigl(40d/(\eta\varepsilon)\bigr)}{\varepsilon^2}
$$
とする。$A\in\mathbb{R}^{m\times d}$ の成分が独立に平均 $0$、分散 $\frac1m$ の正規分布に従うとき、確率 $1-\eta$ 以上で $\delta_s\le3\varepsilon$ である。$d\times d$ の直交行列 $U$ を固定すると、$AU$ についても同じことが成り立つ。
この記事では証明しない。証明は SSBD14 Theorem 23.9(p. 333、証明は pp. 335–337)にある。そこで示されるのは、台が $s$ 個以下の全ての $v\ne0$ について $1-\varepsilon\le\lvert Av\rvert_2/\lvert v\rvert_2\le1+\varepsilon$ であることで、2 乗すると $(1-\varepsilon)^2\ge1-2\varepsilon$、$(1+\varepsilon)^2\le1+3\varepsilon$ から $\delta_s\le3\varepsilon$ を得る。証明は単位球の $\varepsilon$ 網による被覆、固定したベクトルのノルムがよく保たれる確率の評価(Johnson–Lindenstraussの補題)、$\binom ds$ 通りの台の和集合の評価を組み合わせる。定数 $100$ は証明の都合で大きくとったもので、$s=5$、$d=1000$、$\varepsilon=0.3$、$\eta=0.01$ では右辺が約 $9.1\times10^4$ になり $d$ を超える。この定理の価値は $m$ が $s\log d$ に比例する大きさで足りるという増え方にある。thm-cs-rip の仮定 $\delta_{2s}<\sqrt2-1$ を保証するには、$s$ を $2s$ に替えて $3\varepsilon<\sqrt2-1$、たとえば $\varepsilon=0.13$ ととる($\varepsilon=0.3$ では $\delta_s\le0.9$ しか言えず、この仮定には足りない)。
$G=A^{\mathsf T}A$($d\times d$)は階数 $m$ 以下で、跡は $d$ である。固有値の 2 乗和と Cauchy–Schwarz の不等式から $\sum_{i,j}G_{ij}^2\ge(\operatorname{tr}G)^2/m=d^2/m$ で、対角の和は $d$ なので $\sum_{i\ne j}\langle a_i,a_j\rangle^2\ge d^2/m-d$ である。左辺は $d(d-1)\mu^2$ 以下なので $\mu^2\ge\frac{d-m}{m(d-1)}$ である。$d\ge2m$ なら右辺は $\frac1{2m}$ 以上で、$(2s-1)\mu< \sqrt2-1$ には $s< \frac12+\frac{\sqrt2-1}2\sqrt{2m}$ が必要である。
$U$ を付けた形は、$x$ そのものではなく、ある正規直交基底での係数(たとえば ウェーブレット 係数)が疎な場合に使う。$x=U\alpha$ で $\alpha$ が疎なら、$y=Ax=(AU)\alpha$ から $\alpha$ を復元すればよい。
| 内容 | 式 | 使える条件 | 根拠 |
|---|---|---|---|
| 線形計画への書き直し | $\min\sum_it_i$、条件 $-t\le v\le t$、$Av=y$(変数 $v,t\in\mathbb{R}^d$) | $Av=y$ が解をもつ | 下の段落 |
| 疎な解の一意性 | $s$ 疎な解は一意 ⇔ どの $2s$ 列も 1 次独立 | — | prop-cs-spark |
| 測定の数の下限 | $m\ge2s$ | 全ての $s$ 疎なベクトルを区別する、$2s\le d$ | cor-cs-2s |
| ℓ1 での厳密な復元 | $x^\star=x$ | 位数 $s$ の NSP(必要十分)、$x$ は $s$ 疎 | thm-cs-nsp |
| ℓ1 の誤差 | $\lvert x^\star-x\rvert_2\le\frac{2(1+\rho)}{1-\rho}\cdot\frac{\sigma_s(x)_1}{\sqrt s}$、$\rho=\frac{\sqrt2\delta_{2s}}{1-\delta_{2s}}$ | $\delta_{2s}<\sqrt2-1$、雑音なし | thm-cs-rip |
| 近似的な直交性 | $\lvert\langle Au,Aw\rangle\rvert\le\delta_{2s}\lvert u\rvert_2\lvert w\rvert_2$ | 台が交わらず合わせて $2s$ 以下 | lem-cs-orth |
| コヒーレンスの評価 | $\delta_s\le(s-1)\mu$ | 列の長さが $1$ | prop-cs-coherence |
| Gauss 行列 | $\delta_s\le3\varepsilon$(確率 $1-\eta$ 以上) | 成分が独立に $N(0,\frac1m)$、$m\ge100s\log(40d/(\eta\varepsilon))/\varepsilon^2$ | thm-cs-gauss(証明しない) |
$\ell^1$ 最小化は、$\lvert v_i\rvert\le t_i$ を 2 本の 1 次不等式 $v_i\le t_i$、$-v_i\le t_i$ に替えると、最適値の等しい線形計画問題になる。最適解では $t_i=\lvert v_i\rvert$ である。単体法 や 内点法 で解ける。
| 状況 | やること | 結果 |
|---|---|---|
| $x$ が $s$ 疎で行列の条件を満たす | 手順どおり | $x^\star=x$ |
| $x$ が疎に近い | 手順どおり | 誤差は $\sigma_s(x)_1/\sqrt s$ の定数倍 |
| 測定に雑音がある | 制約を $\lvert Av-y\rvert_2\le\eta$ にする(2 次錐計画) | 節「補足」 |
| 復元した $x^\star$ の 0 でない成分が $m$ 個近い | $s$ が大きすぎる | 測定を増やすか表し方を見直す |
$A=\begin{pmatrix}1&0&1\\0&1&1\end{pmatrix}$、$s=1$ とする。
使う公式:thm-cs-nsp。
答え:$\ker A$ は $h=(1,1,-1)$ で張られ、どの成分の絶対値 $1$ もほかの 2 つの和 $2$ より小さいので、位数 1 の NSP が成り立つ。$x=(0,0,2)$ なら $y=(2,2)$ で、$\ell^1$ 最小化の解は $x$ 自身($\lvert x\rvert_1=2$)である。
$Av=y$ の解は $v=x+th=(t,t,2-t)$ で、$\lvert v\rvert_1=2\lvert t\rvert+\lvert2-t\rvert$ である。$t\ge0$ では $2t+\lvert2-t\rvert\ge2$ で等号は $t=0$ だけ、$t<0$ では $-2t+2-t>2$ である。よって最小点は $t=0$ のただ 1 つである。
$A=\begin{pmatrix}1&-\frac12&-\frac12\\0&\frac{\sqrt3}2&-\frac{\sqrt3}2\end{pmatrix}$(長さ $1$ の 3 本の列が $120^\circ$ ずつ開く)とする。
使う公式:prop-cs-coherence、thm-cs-nsp。
答え:$\mu=\frac12$ で、どの 2 列の部分行列でも $A_S^{\mathsf T}A_S$ の固有値は $\frac12,\frac32$ なので $\delta_2=\frac12\approx0.5$ である。これは $\sqrt2-1\approx0.4142$ より大きく、thm-cs-rip は使えない。しかし $\ker A$ は $(1,1,1)$ で張られ、$1<2$ なので位数 1 の NSP が成り立ち、全ての 1 疎なベクトルが $\ell^1$ 最小化で復元される。RIP の条件は十分条件にすぎない。
$d=60$、$m=30$、$s=5$ とし、$A$ の成分を独立に $N(0,\frac1{30})$、$x$ の台を一様に、値を標準正規分布から選んだ 1 回の例である。
使う公式:公式の表の線形計画への書き直し。
答え:$\ell^1$ 最小化の解と $x$ の差は $\lvert x^\star-x\rvert_2\approx2.7\times10^{-13}$ で、台も一致した。同じ $y$ の $\ell^2$ ノルム最小の解 $A^{\mathsf T}(AA^{\mathsf T})^{-1}y$ は 60 成分が全て 0 でなく、相対誤差は約 $0.65$ である。$m$ を変えて 50 回ずつ試すと、復元できた割合は $m=10$ で $0.02$、$m=20$ で $0.90$、$m=30$ 以上で $1$ であった(下の図)。
図: 左は d=60、s=5 の Gauss 行列で、測定の数 m を 10 から 40 まで 5 ずつ変えたときに ℓ1 最小化が x を復元できた割合(各 50 回)。m=10 でほぼ 0、m=20 で 0.9、m=30 以上で 1。右は m=30 の 1 回で、x の 5 個の 0 でない成分と ℓ1 最小化の解が重なり、ℓ2 最小ノルム解は全成分に小さな値が散らばる。
thm-cs-rip の定数 $C=\frac{2(1+\rho)}{1-\rho}$ を $\delta=\delta_{2s}$ ごとに求める。
答え:
| $\delta$ | $0.1$ | $0.2$ | $0.3$ | $0.4$ |
|---|---|---|---|---|
| $\rho$ | $0.1571$ | $0.3536$ | $0.6061$ | $0.9428$ |
| $C$ | $2.746$ | $4.188$ | $8.155$ | $67.94$ |
$\delta=\frac15$ では $\rho=\frac{\sqrt2}4$、$C=\frac{18+8\sqrt2}7\approx4.1877$ である。$x=(1,\frac12,\frac14,\dots,2^{-19})$、$s=3$ なら $\sigma_3(x)_1=\frac14-2^{-19}\approx0.25$ で、誤差は $4.1877\times0.25/\sqrt3\approx0.604$ 以下である。$\delta\to\sqrt2-1$ で $C\to\infty$ となる。
各行は、定理の仮定を 1 つだけ外す。どの行も $d=3$、$m=2$ の行列で確かめられる。
| 外す仮定 | 反例 | 成り立たなくなること |
|---|---|---|
| thm-cs-nsp の NSP($s=1$) | $A=\begin{pmatrix}1&0&0.4\\0&1&0.4\end{pmatrix}$、$x=(0,0,1)$。核は $(0.4,0.4,-1)$ で、$1>0.8$ | $y=(0.4,0.4)$ の $\ell^1$ 最小化の解は $(0.4,0.4,0)$($\lvert\cdot\rvert_1=0.8<1$)で、$x$ でない |
| NSP の不等号が厳密($s=1$) | 第 3 列を $(0.5,0.5)$ にする。核は $(1,1,-2)$ で $2=1+1$ | $x=(0,0,1)$ と $(0.5,0.5,0)$、$(0.25,0.25,0.5)$ がどれも $\lvert\cdot\rvert_1=1$ で、最小点が一意でない |
| $x$ が $s$ 疎(NSP は位数 1) | ex-cs-nsp の $A$ と 2 疎な $x=(1,1,0)$ | $\ell^1$ 最小化の解は $(0,0,1)$($\lvert\cdot\rvert_1=1<2$) |
| $\ell^1$ ノルムで最小化する | ex-cs-nsp の $A$ と $x=(0,0,2)$ で、$\ell^2$ ノルムを最小にする | 解は $(\frac23,\frac23,\frac43)$ で、疎でない |
| prop-cs-spark の 2($s=2$、$2s>d$ なので全ての列の 1 次独立) | ex-cs-nsp の $A$($m=2<4$) | $u=(1,1,0)$ と $w=(0,0,1)$ はともに 2 疎で $Au=Aw=(1,1)$。どの方法でも区別できない |
1 行目の行列は、第 3 列が短いことが原因である。第 3 列を長さ $1$ の $(\frac1{\sqrt2},\frac1{\sqrt2})$ に替えると核は $(1,1,-\sqrt2)$ で張られ、$\sqrt2<2$ なので NSP が成り立つ。NSP も RIP も列の長さに依存するので、prop-cs-coherence を使う前に列を正規化する。
| 誤り | 正しくは | なぜ |
|---|---|---|
| RIP を満たさないから復元できないと判断する | RIP は十分条件で、必要十分なのは NSP | ex-cs-coherence は $\delta_2=\frac12$ でも全ての 1 疎なベクトルを復元する |
| thm-cs-gauss の式で必要な $m$ を見積もる | 式は増え方を示すもので、定数は大きすぎる | $s=5$、$d=1000$ で右辺は $9.1\times10^4$($>d$)。実際は ex-cs-gauss のように $m=30$、$d=60$ で足りる |
| 最小 2 乗($\ell^2$ ノルム最小の解)で疎な解を求める | $\ell^1$ ノルムを最小にする | $\ell^2$ の解は全成分に広がる(反例の表の 4 行目、ex-cs-gauss) |
| $\delta_s<\sqrt2-1$ で十分とする | 必要なのは位数 $2s$ の $\delta_{2s}$ | 証明の段 3 で $2s$ 疎な $h_{T_{01}}$ に RIP を当てる |
| 雑音のある $y$ に $Av=y$ の制約をそのまま使う | 制約を $\lvert Av-y\rvert_2\le\eta$ にゆるめる | $Av=y$ は雑音まで合わせた解を選ぶので、thm-cs-rip の評価は使えない。$A$ の階数が $m$ 未満なら解をもたないこともある |
雑音 $e$ を含む測定 $y=Ax+e$($\lvert e\rvert_2\le\eta$)では、$\lvert Av-y\rvert_2\le\eta$ の下で $\lvert v\rvert_1$ を最小にする(2 次錐計画の問題になる)。この形の誤差の評価はこの記事では扱わない。$\lambda\lvert v\rvert_1+\frac12\lvert Av-y\rvert_2^2$ を最小にする形は統計の LASSO と同じ問題で、勾配の 1 歩と成分ごとの軟しきい値を交互に行う 近接勾配法 で解ける。$\ell^1$ ノルムの代わりに、$\lvert v\rvert_0$ に近い量を、重みを反復で更新しながら最小にする方法や、貪欲法(直交マッチング追跡)も使われる。圧縮センシングは Donoho と Candès–Tao の 2005〜2006 年の論文に始まる(SSBD14 §23.6、p. 339)。
SSBD14 第 23 章 §23.3(pp. 331–337)。定義 23.5(RIP)、Theorem 23.6〜23.9 と Lemma 23.10〜23.12 を使った。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する