jz_trunkの日記

日記.できるだけ毎日書こうとしている.

圧縮センシングとスパースコーディングを混同していた

しばらく誤解していたのでメモを残しておく.\renewcommand{\bx}{\boldsymbol{x}}\renewcommand{\by}{\boldsymbol{y}}\renewcommand{\bA}{\boldsymbol{A}}\renewcommand{\ba}{\boldsymbol{a}}

参考文献

結論

圧縮センシングとスパースコーディング両方において,スパース推定(スパース制約付誤差最小化)が現れる. 両者は同じ問題を解いているがその意味には違いがある.

  • 圧縮センシングにおいてスパース推定は正則化観測ベクトルからスパースな原信号を復元するためのデコーディングである.
  • スパースコーディングにおいてスパース推定は対象の信号をスパースなベクトルで表現するためのエンコーディングである.

f:id:jz_trunk:20161203233245p:plain
スパースコーディングと圧縮センシングではエンコーディングとデコーディングが逆になる. また,行列 \bA も圧縮センシングでは原信号を変換するベクトルが行ベクトルとして並んだ行列であるのに対して, スパースコーディングでは特徴ベクトルが列方向に並んだベクトルとなる.

以下,少し詳しく.

問題設定

圧縮センシングとは

適当な原信号 \bx\in\mathbb{R}^n を考える. この原信号が適当な行列  \bA\in\mathbb{R}^{m\times n} を用いて  \by=\bA\bx と変換され,この  \by が観測される. 行列 \bA と観測 \by が与えられたとき,原信号 \bx を復元できるかということが圧縮センシングにおける問題である. 圧縮センシングという名の通り,そもそも観測の数を圧縮することを目的としており,通常  m \lt n であるため劣決定系であり, 逆行列を用いた解法は使うことができない.また,一般化逆行列を用いると元のスパースなベクトルは一般に復元できない.

しかし,この問題は条件付きでYesであり,特定の条件下では原信号を復元することができる. \bxがスパースなベクトルであるという仮定がおけるとき \bx のスパース性,原信号の次元 n および観測ベクトルの次元  m に依存して,(高い確率で)復元できるかが定まることが知られている (http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1803-03.pdfや,その参考文献を参照.情報統計力学やランダム高次元幾何学の結果としてそうなっているらしい… が読めていない). この  \bx は何らかのデータを線形変換した後でスパースになるものでもよい(元データの復元のためには少なくとも許容可能な誤差の範囲内で可逆である必要はある). その場合,変換行列を \boldsymbol{\Phi} とすれば  \by=\bA\boldsymbol{\Phi}\bx となり,  \bA^\prime = \bA\boldsymbol{\Phi} と定義すれば,  \by = \bA^\prime \bx と書き換えられ,同じ枠組みで扱うことができる. 例えば,画像のピクセル値はスパースでなくても,ウェーブレット変換後の係数はその絶対値が小さいものを0にしてスパースにしても, 元の画像を良い精度で近似することができる.

ここで用いる \bA は,その各行が原信号  \bx を線形変換するベクトルである(ランダム行列などが使われる). 観測ベクトル \by の第  j 番目の要素は,行列 \bA j 行目のベクトルと, \bx内積となる. つまり,観測データ \by は原信号  \bx に対して  m 種類の異なる線形変換(エンコーディング)をした観測値を記録したものである. なお,  \by にはスパース性の制約はない.

実用上は  \by に相当するデータを直接観測できるような装置を用いる必要がある.そしてその計測値から未知の  \bx を推定する. なので,sparse MRIやsingle pixel cameraのように原理的にそのような計測が可能なものがアプリケーションとなっている.

さて,この  \by \bA から原信号  \bx を復元するためには, スパース推定 \begin{equation} \operatorname*{minimize}_{\bx} f(\by, \bA\bx)\quad\operatorname{such that}\quad sparseness(\bx) \leq k \end{equation} を行う(スパース制約付の誤差最小化問題を解く).ここで  f は適当な誤差関数であり, \ell_2-ノルムの2乗, \|\bx \|_2^2=\sum_{i=1}^n x_i^2などを用いる.また sparseness については, 厳密に非ゼロ要素の個数( \ell_0-ノルムとも呼ばれる)にすると,最適化問題が組み合せ問題になる. なので,組み合わせ問題に対してグリーディな解法(Matching Pursuit, Orthogonal Matching Pursuitなど)を用いるか, あるいは  \ell_0-ノルムを \ell_1-ノルム  \|\bx \|_1=\sum_{i=1}^n |x_i| などに緩和したうえで解くことも多い.

結局,スパース推定を行うことにより  \bA によってエンコーディングされた信号  \by からスパースな原信号  \byが復元(デコーディング)される.

スパースコーディングとは

適当な信号 \by\in\mathbb{R}^m と基底行列  \bA\in\mathbb{R}^{m\times n} が与えられる. このとき,基底行列の列ベクトルのうち少数のベクトルだけを選んで, \by をできるだけよく近似する係数ベクトル  \bx\in\mathbb{R}^n を推定するという問題. この場合は少数の列を選択することが \bx のスパース性に対応する.

ここで基底行列は厳密には線形独立ではない  m\lt nのようなものを考えることが多いが,便宜上基底と呼ばれている. この行列は特徴ベクトル(画像であれば画像の特徴)を列ベクトルとして並べた行列である. そして,これらの特徴ベクトルのもとでデータを表現する係数ベクトル  \bx を推定するために,スパース推定を行う.

スパース推定を行うことにより, \bA のもと信号 \by はスパースなベクトル  \bxエンコーディングされる. 信号  \by をデコーディングする際には  \bA\bx を計算すればよい.

このように,スパースコーディングのエンコーディングは圧縮センシングのデコーディングに, スパースコーディングのデコーディングは圧縮センシングのエンコーディングに対応している.

まとめ

  • 圧縮センシングとスパースコーディングでエンコーディングとデコーディングが逆になる.
  • 圧縮センシングではデコーディングのために,スパースコーディングではエンコーディングのためにスパース推定を行う.
  • 行列 \bA は圧縮センシングではデータの変換ベクトルを行に並べた変換行列,スパースコーディングでは特徴ベクトルを列に並べた基底行列.