スパースモデリング
上述のように、スパース表現問題
min α ∈ R p ‖ α ‖ 0 subject to ‖ x − D α ‖ 2 2 ≤ ε 2 . {\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\|\alpha \|_{0}{\text{ subject to }}\|x-D\alpha \|_{2}^{2}\leq \epsilon ^{2}.}
を解くために開発されたさまざまな近似(追跡(pursuit)ともいう)アルゴリズムがある。
これらの主な手法のいくつかを以下に示す。
マッチング追跡(英語版)は、上記の問題を近似的に解くための貪欲反復アルゴリズムである。これは、 α {\displaystyle \alpha } 内の非ゼロの位置を一度に1つずつ徐々に見つけてゆく方法である。基本的な考え方は、各ステップで、現在の残余( x {\displaystyle x} に初期化)と最も相関のある D {\displaystyle D} の列(アトム)を見つけ、新しいアトムとその係数を考慮に入れて残余を更新することである。マッチング追跡では、同じアトムが複数回選択される場合がある。
直交マッチング追跡は、マッチング追跡と非常によく似ているて、大きな違いが一つある。アルゴリズムの各ステップで、すべての非ゼロ係数が最小二乗法によって更新される。
線型方程式系 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 }