圧縮センシング (compressed sensing, compressive sensing)

未知の大きさ \(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\) に関する条件が知られている.

-- しましま

関連項目

リンク集

関連文献


トップ   編集 凍結 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2012-03-19 (月) 09:27:46