マッチング追跡アルゴリズム

冗長なディクショナリとスパース性

信号を特定の基底で表現するには、展開係数の一意なセットをその基底で見つける必要があります。基底 (特に直交基底) での信号表現には多くの利点がありますが、欠点もあります。

基底がスパース表現を提供できるかどうかは、信号特性が基底ベクトルの特性とよく一致するかどうかによります。たとえば、滑らかな連続信号はフーリエ基底でスパース表現になりますが、インパルスはなりません。孤立した不連続点のある滑らかな信号は、ウェーブレット基底でスパース表現になります。しかし、フーリエ変換の高周波数のサポートが狭い信号を表現するにはウェーブレット基底は効率的ではありません。

実際の信号には、ほとんどの場合、どの単一基底でもスパース表現にならない特徴が含まれています。このような信号の場合、単一の基底に限定されない集合からベクトルを選択する必要があります。空間内のすべてのベクトルを確実に表現する必要があるので、選択肢となるベクトルの "ディクショナリ" は、その空間を張らなければなりません。しかし、その集合は単一の基底に限定されないので、ディクショナリは線形独立ではありません。

ディクショナリ内のベクトルは線形独立の集合ではないので、ディクショナリでの信号表現は一意ではありません。しかし、冗長なディクショナリを作成することで、信号の時間-周波数特性または時間-スケール特性に適応したベクトルの集合で信号を展開できます。複数の基底の和集合で構成されるディクショナリを自由に作成できます。たとえば、二乗可積分関数の空間に対して、ウェーブレットパケット基底と局所コサイン基底で構成される基底を形成できます。ウェーブレットパケット基底は、異なる周波数範囲で異なる動きをする信号によく適合します。局所コサイン基底は、異なる時間範囲で異なる動きをする信号によく適合します。これらの各基底からベクトルを選択できると、さまざまな特性を持つ信号に対してスパース表現の実現が大幅に向上します。

ディクショナリでの非線形近似

"ディクショナリ" を信号空間に対する単位ノルムの基本構成ブロックの集合として定義します。このような単位ノルムのベクトルを "原子" と呼びます。ディクショナリの原子が信号空間全体を張る場合、ディクショナリは "完全" となります。

ディクショナリの原子が線形従属の集合を形成する場合、ディクショナリは "冗長" となります。マッチング追跡のほとんどのアプリケーションでは、ディクショナリは完全かつ冗長です。

{φ_k} がディクショナリの原子を表すとします。ディクショナリは完全かつ冗長であるとします。空間の信号を原子の線形結合として表現する方法は 1 つではありません。

$x = \sum_{k} α_{k} ϕ_{k}$

重要なことは、"最適" な方法が存在するかどうかです。"最適" な表現を選択する直感的に十分な方法は、信号との内積が (絶対値で) 最大となる φ_k を選ぶことです。たとえば、最適な 1 つの φ_k は次のようになります。

$max_{k} | < x, ϕ_{k} > |$

これは、単位ノルムの原子の場合、φ_k が張る部分空間上へのスカラー射影の大きさです。

"マッチング追跡" で中心となる問題は、ディクショナリ内で最適な信号の M 項展開を選択する方法です。

基本的なマッチング追跡

Φ が N 行 M 列の行列 (M>N) として原子のディクショナリを示すとします。この完全で冗長なディクショナリが信号空間のフレームを形成する場合、フレーム作用素を使用することで、L2 ノルムが最小の展開係数ベクトルを得ることができます。

$Φ^{†} = Φ^{*} {(Φ Φ^{*})}^{- 1}$

しかし、フレーム作用素が返す係数ベクトルはスパース性を維持しません。信号がディクショナリでスパースな場合、正規のフレーム作用素で得られる展開係数には、一般にそのスパース性が反映されません。ディクショナリでの信号のスパース性は通常、維持したい特性です。マッチング追跡では、スパース性の維持に直接取り組みます。

マッチング追跡は、完全で冗長なディクショナリにおいて信号の最適な非線形近似を計算する貪欲法です。マッチング追跡は、段階的に信号のスパース近似のシーケンスを構築します。Φ= {φ_k} が単位ノルムの原子のディクショナリを示すとします。f を信号とします。

まず、R⁰f = f と定義します。
マッチング追跡を始めるため、R⁰f = f との内積の絶対値が最大となる原子をディクショナリから選択します。その原子を φ_p で示します。
φ_p が張る空間上への R⁰f の直交射影を減算して、残差 R¹f を形成します。

$R^{1} f = R^{0} f - 〈 R^{0} f, ϕ_{p} 〉 ϕ_{p}$
残差に対して手順 2 および 3 を反復することで繰り返します。

$R^{m + 1} f = R^{m} f - 〈 R^{m} f, ϕ_{k} 〉 ϕ_{k}$
指定の停止条件に達したらアルゴリズムを停止します。

"非直交" (または基本的な) マッチング追跡では、ディクショナリの原子が互いに直交なベクトルではありません。そのため、前の残差から次の残差を減算すると、前に含められた原子が張る空間に直交しない成分が生じる場合があります。

これを説明するため、次の例を考えます。この例は、実用的なマッチング追跡アルゴリズムの提示を目的としたものではありません。

2 次元ユークリッド空間に対して次のディクショナリを考えます。このディクショナリは、ノルムの等しいフレームです。

${(\begin{matrix} 1 \\ 0 \end{matrix}), (\begin{matrix} 1 / 2 \\ \sqrt{3} / 2 \end{matrix}), (\begin{matrix} - 1 / \sqrt{2} \\ - 1 / \sqrt{2} \end{matrix})}$

次の信号があるとします。

$(\begin{matrix} 1 \\ 1 / 2 \end{matrix})$

次の図は、この例を示しています。ディクショナリの原子は赤で示しています。信号ベクトルは青で示しています。

このディクショナリと信号を MATLAB^® で作成します。

dictionary = [1 0; 1/2 sqrt(3)/2; -1/sqrt(2) -1/sqrt(2)]';
x = [1 1/2]';

信号とディクショナリの原子との内積 (スカラー積) を計算します。

scalarproducts = dictionary'*x;

絶対値で最大のスカラー積は、信号と [-1/sqrt(2); -1/sqrt(2)] とで発生します。これは、2 つのベクトルの間の角度が約 π ラジアンなので、明らかです。

[-1/sqrt(2); -1/sqrt(2)] への信号の直交射影を信号から減算して、残差を形成します。次に、残差 (新しい信号) とディクショナリの残りの原子との内積を計算します。構成から残差は [-1/sqrt(2); -1/sqrt(2)] に直交するので、このベクトルを含める必要はありません。

residual = x-scalarproducts(3)*dictionary(:,3);
scalarproducts = dictionary(:,1:2)'*residual;

絶対値で最大のスカラー積は [1;0] で得られます。2 回の反復から得られたディクショナリ内の最適な 2 つの原子は、[-1/sqrt(2); -1/sqrt(2)] と [1;0] です。この残差に対して反復を行うと、出力はもはや最初に選択した原子に直交しないことがわかります。つまり、このアルゴリズムによって、最初に選択した原子が張る空間に直交しない成分が生じています。この事実、および関連する収束についての複雑な問題が、直交マッチング追跡 (OMP) を優先する理由となっています。

直交マッチング追跡

直交マッチング追跡 (OMP) では、既に選択した原子が張る空間に残差が必ず直交します。この結果、d 次元ベクトルは最大で d 回のステップの後、収束します。

概念的には、グラム・シュミットを使用して原子の正規直交集合を作成することで、これを実行できます。原子の正規直交集合を使用すると、d 次元ベクトルの場合、最大で d 個の直交方向を見つけられることがわかります。

OMP アルゴリズムは次のとおりです。

信号を f で表します。残差を初期化します (R⁰f = f)。
R⁰f = f との内積の絶対値が最大となる原子を選択します。その原子を φ_p で示します。
既に選択した原子を列として、行列 Φ を形成します。Φ の列が張る空間への直交射影作用素を定義します。

$P = Φ {(Φ^{*} Φ)}^{- 1} Φ^{*}$
直交射影作用素を残差に適用します。
残差を更新します。

$R^{m + 1} f = (I - P) R^{m} f$
I は単位行列です。

直交マッチング追跡では、既に選択した原子が張る空間の成分が、その後のステップで生じることはありません。

弱い直交マッチング追跡

選択した原子が内積の絶対値を最大にするという基準を緩和して、それほど厳密でない基準にすると計算効率が高くなります。

$| 〈 x, ϕ_{p} 〉 | \geq α \max_{k} | 〈 x, ϕ_{k} 〉 |, α \in (0, 1]$

これは "弱い" マッチング追跡と呼ばれます。