圧縮センシング の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• 圧縮センシング へ行く。

* 圧縮センシング (compressed sensing, compressive sensing) [#k0067868]

//ここには %項目の説明を書いてください．よろしければ署名しておいてください．

未知の大きさ \(m\) の信号ベクトル \(\mathbf{x}\)，観測される大きさ \(n\) の観測ベクトル \(\mathbf{y}\)，既知の \(n\times m\) の変換行列 \(A\) について，次の関係が成立しているとする
\[\mathbf{y}=A\mathbf{x}\]

\(A\) のランクが \(m\) 未満なら \(\mathbf{x}\) を知ることはできず，よって \(n\lt m\) なら一般には知ることはできない．しかし，信号ベクトルの非0要素の数 \(k\) が \(k \ll m\) なら \(\mathbf{x}\) を高い確率で復元できる．

\(L_0\) 復元法では， \(\mathbf{y}=A\mathbf{x}\) を満たす \(\mathbf{x}\) のうち，その非0要素の数（＝ \(L_0\) ノルム）を最小にする解を選ぶ
\[ \hat{\mathbf{x}}=\arg\min_\mathbf{x} \|\mathbf{x}\|_0 \text{ subject to } \mathbf{y}=A\mathbf{x} \]
ただし，この問題は組み合わせ最適化で解くのが困難．

\(L_1\) 復元法は， \(L_0\) ノルムを \(L_1\) ノルムと置き換えたもの
\[ \hat{\mathbf{x}}=\arg\min_\mathbf{x} \|\mathbf{x}\|_1 \text{ subject to } \mathbf{y}=A\mathbf{x} \]
これは線形計画問題であり，多項式時間で解くことができる．信号ベクトルを復元できる変換行列 \(A\) や非0要素の数 \(k\) に関する条件が知られている．

> -- しましま

** 関連項目 [#d91051b6]

//英語や同義語のあとに，#brで区切って関連する項目をリストしてください．
-[[compressed sensing]]
-[[compressive sensing]]
#br
-[[情報理論]]
-[[線形計画]]
#br
-[[検索:圧縮センシング]]

** リンク集 [#jf7dae20]

//関連するWWW資源があればリンクしてください．
-[[Wikipedia:Compressed_sensing]]

//*** Freeware

//-[[mloss:]] 機械学習レポジトリ mloss

** 関連文献 [#tad0f4be]

//この%項目%に関連する書籍や論文を紹介してください．

- [[和田山 正“圧縮センシングの理論とその展開”第13回情報論的学習理論ワークショップ (2010)>http://ibisml.org/ibis2010/session/ibis2010wadayama.pdf]]
- [[田中 利幸“圧縮センシングの数理”IEICE Fundamentals Review, vol.4, no.1, pp.39-47 (2010)>http://www.jstage.jst.go.jp/article/essfr/4/1/4_39/_article/-char/ja/]]