ノイズのない観測
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/18 07:58 UTC 版)
「スパースモデリング」の記事における「ノイズのない観測」の解説
線型方程式系 x = D α {\displaystyle x=D\alpha } を考える。ここで、 D {\displaystyle D} は劣決定（英語版） m × p {\displaystyle m\times p} 行列 ( m < p ) {\displaystyle (m<p)} であり、 x ∈ R m , α ∈ R p {\displaystyle x\in \mathbb {R} ^{m},\alpha \in \mathbb {R} ^{p}} である。ここで、行列 D {\displaystyle D} （通常、最大階数と仮定される）は「辞書」と呼ばれ、 x {\displaystyle x} は関心のある信号である。基本的なスパース表現問題は、 x = D α {\displaystyle x=D\alpha } を満たす最もスパースな表現 α {\displaystyle \alpha } を求めることと定義される。 D {\displaystyle D} の列決定性により、この線形システムは一般的に無限に多くの可能な解が認められ、これらの中から非ゼロの数が最も少ないものを探す。形式的に言えば、 min α ∈ R p ‖ α ‖ 0 subject to x = D α {\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\|\alpha \|_{0}{\text{ subject to }}x=D\alpha } を解く。ここで ‖ α ‖ 0 = # { i : α i ≠ 0 , i = 1 , … , p } {\displaystyle \|\alpha \|_{0}=\#\{i:\alpha _{i}\neq 0,\,i=1,\ldots ,p\}} は ℓ 0 {\displaystyle \ell _{0}} 半ノルムで、 α {\displaystyle \alpha } の非ゼロ成分の数を数える。この問題は、組合せ最適化におけるNP完全な部分集合選択問題への還元を伴うNP困難であることが知られている。 α {\displaystyle \alpha } のスパース性とは、その中で少数の成分（ k ≪ m < p {\displaystyle k\ll m<p} ）だけが非ゼロであることを意味する。このようなスパース分解（sparse decomposition）を行う潜在的な動機は、 x {\displaystyle x} を D {\displaystyle D} のできるだけ少ない列（アトムとも呼ばれる）の線形結合として、可能な限り単純に説明したいという欲求にある。このように、信号 x {\displaystyle x} は、 D {\displaystyle D} から取り出したいくつかの基本要素（アトム）から構成される分子と見なすことができる。 上記の問題は確かにNP困難であるが、近似アルゴリズムを用いてその解を見つけることができる。そのような選択肢の一つは、 ℓ 0 {\displaystyle \ell _{0}} の代わりに ℓ 1 {\displaystyle \ell _{1}} ノルムを用いて問題を凸緩和 (en:英語版) することで得られる。ここで、 ‖ α ‖ 1 {\displaystyle \|\alpha \|_{1}} は α {\displaystyle \alpha } 内の要素の絶対値を単純に合計したものである。これは基底追跡（英語版）（basis pursuit、BP）アルゴリズムとして知られており、任意の線型計画法ソルバーを用いて処理することができる。もう一つの近似法は、マッチング追跡（英語版）（matching pursuit、MP）のような貪欲法で、非ゼロの位置を一度に一つずつ見つけてゆくものである。 驚くべきことに、 D {\displaystyle D} に関する穏やかな条件（Spark (数学)（英語版）、相互コヒーレンス（英語版）または制限付等長性（英語版））と、解のスパース性のレベル k {\displaystyle k} の下で、スパース表現問題は一意の解を持つことが示され、BPとMPはそれを完全に見つけることが保証されている。
※この「ノイズのない観測」の解説は、「スパースモデリング」の解説の一部です。
「ノイズのない観測」を含む「スパースモデリング」の記事については、「スパースモデリング」の概要を参照ください。
- ノイズのない観測のページへのリンク
