* 圧縮センシング (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/]]

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS