スパース近似

スパース近似（スパース表現とも呼ばれる）理論は、線形方程式のスパース解を扱います。これらの解を見つけてアプリケーションで活用する手法は、画像処理、信号処理、機械学習、医療用画像処理などで幅広く使用されています。

方程式 の線形システム を考えてみましょう。ここで は劣決定行列で です。行列(通常はフルランクと仮定) は辞書と呼ばれ、 は関心のある信号です。コアとなるスパース表現問題は、を満たす可能な限りスパースな表現を求めることと定義されます。 の劣決定性のため、この線形システムには一般に無限の解が存在し、その中から非ゼロの数が最も少ないものを探します。正式には、次のように解きます。 ${\displaystyle x=D\alpha }$${\displaystyle D}$ ${\displaystyle m\times p}$ ${\displaystyle (m<p)}$${\displaystyle x\in \mathbb {R} ^{m},\alpha \in \mathbb {R} ^{p}}$${\displaystyle D}$${\displaystyle x}$${\displaystyle \alpha}$${\displaystyle x=D\alpha }$${\displaystyle D}$

${\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\|\alpha \|_{0}{\text{ ただし }}x=D\alpha 、}$

ここで、は擬似ノルムであり、の非ゼロ成分の数を数えます。この問題はNP困難であることが知られており、組み合わせ最適化におけるNP完全な部分集合選択問題に還元されます。 ${\displaystyle \|\alpha \|_{0}=\#\{i:\alpha _{i}\neq 0,\,i=1,\ldots ,p\}}$${\displaystyle \ell_{0}}$${\displaystyle \alpha}$

のスパース性は、その中の少数の ( ) 成分だけが非ゼロであることを意味します。このようなスパース分解の根本的な動機は、を、原子とも呼ばれる のできるだけ少ない列の線形結合としてできるだけ簡単に説明したいという願望です。そのため、信号はから取られた少数の基本元素で構成された分子として見ることができます。 ${\displaystyle \alpha}$${\displaystyle k\ll m<p}$${\displaystyle x}$${\displaystyle D}$${\displaystyle x}$${\displaystyle D}$

上で提起された問題は確かに NP 困難ですが、その解は多くの場合、近似アルゴリズムを使用して見つけることができます。そのようなオプションの 1 つは、問題の凸緩和です。これは、の代わりに -ノルムを使用して取得されます。ここで、 は内のエントリの絶対値を単純に合計します。これは、基底追求(BP) アルゴリズムとして知られており、任意の線形計画法ソルバーを使用して処理できます。別の近似方法は、マッチング追求(MP)などの貪欲な手法で、非ゼロの位置を 1 つずつ見つけます。 ${\displaystyle \ell_{1}}$${\displaystyle \ell_{0}}$${\displaystyle \|\alpha \|_{1}}$${\displaystyle \alpha}$

驚くべきことに、（スパーク（数学）、相互コヒーレンス、または制限された等長性特性）と解のスパース性のレベル に関する穏やかな条件下では、スパース表現問題が一意の解を持つことが示され、BPとMPはそれを完璧に見つけることが保証されます。^{[1] [2] [3]}${\displaystyle D}$${\displaystyle k}$

観測信号はノイズが多いことが多い。等式制約を緩和し、データフィッティング項に-ノルムを課すことで、スパース分解問題は次のようになる。 ${\displaystyle x}$${\displaystyle \ell_{2}}$

${\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\|\alpha \|_{0}{\text{ ただし }}\|xD\alpha \|_{2}^{2}\leq \epsilon ^{2},}$

あるいはラグランジアン形式にすると、

${\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\lambda \|\alpha \|_{0}+{\frac {1}{2}}\|xD\alpha \|_{2}^{2},}$

を置き換える場所はどこですか。 ${\displaystyle \lambda}$${\displaystyle \epsilon }$

ノイズがない場合と同様に、これら2つの問題は一般にNP困難ですが、追跡アルゴリズムを使用して近似することができます。より具体的には、を-ノルムに変更すると、次の式が得られます。 ${\displaystyle \ell_{0}}$${\displaystyle \ell_{1}}$

${\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\lambda \|\alpha \|_{1}+{\frac {1}{2}}\|xD\alpha \|_{2}^{2},}$

これは基底追求ノイズ除去として知られています。同様に、マッチング追求は上記の問題の解を近似するために使用でき、エラーしきい値に達するまで非ゼロの位置を1つずつ見つけます。ここでも、理論的な保証は、BPとMPが、 の特性と解の濃度に応じてほぼ最適な解につながることを示唆しています。 ^{[4] [5] [6]}もう1つの興味深い理論的結果は、がユニタリ行列 の場合に関係しています。この仮定の下では、上で提起された問題（または のいずれか）は、非線形収縮の形で閉じた形式の解を許容します。^[4]${\displaystyle D}$${\displaystyle k}$ ${\displaystyle D}$${\displaystyle \ell_{0}}$${\displaystyle \ell_{1}}$

基本的なスパース近似問題にはいくつかのバリエーションがあります。

構造化スパース性: 問題の元のバージョンでは、辞書内の任意の原子を選択できます。構造化（ブロック）スパース性モデルでは、原子を個別に選択するのではなく、それらのグループを選択します。これらのグループは重なり合うことがあり、サイズが異なる場合があります。目的は、このブロック構造を強制しながらスパースになるように表現することです。^[7]${\displaystyle x}$

協調的（ジョイント）スパースコーディング：問題の元のバージョンは、単一の信号に対して定義されています。協調的（ジョイント）スパースコーディングモデルでは、一連の信号が利用可能であり、それぞれが（ほぼ）同じ原子セットから発生すると考えられます。この場合、追跡タスクは、データを最もよく表すスパース表現のセットを回復し、同じ（または近い）サポートを共有するようにすることを目的とします。^[8]${\displaystyle x}$${\displaystyle D}$

その他の構造: より広義には、スパース近似問題は、非ゼロ位置のパターンに特定の望ましい構造を強制しながら投げかけることができます。広く研究されている2つの興味深いケースは、ツリーベースの構造と、より一般的にはボルツマン分散サポートです。^[9]${\displaystyle \alpha}$

すでに述べたように、スパース表現問題に対処するために開発された さまざまな近似（追跡とも呼ばれる）アルゴリズムがあります。

${\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\|\alpha \|_{0}{\text{ ただし }}\|xD\alpha \|_{2}^{2}\leq \epsilon ^{2} とする。}$

以下に、これらの主な方法のいくつかを紹介します。

• マッチング追求は、上記の問題を近似的に解く貪欲な反復アルゴリズムです。これは、 内の非ゼロの位置を 1 つずつ徐々に見つけることで機能します。中心となる考え方は、各ステップで、現在の残差 ( に初期化) と最も相関する 内の列 (原子) を見つけ、次にこの残差を更新して新しい原子とその係数を考慮に入れることです。マッチング追求では、同じ原子が複数回選択される場合があります。${\displaystyle \alpha}$${\displaystyle D}$${\displaystyle x}$
• 直交マッチング追跡はマッチング追跡と非常に似ていますが、大きな違いが 1 つあります。アルゴリズムの各ステップで、すべての非ゼロ係数が最小二乗法によって更新されます。その結果、残差は既に選択された原子に対して直交するため、原子を複数回選択することはできません。
• 段階的貪欲法: 上記の改良版は、貪欲に動作するアルゴリズムであり、2つの重要な機能が追加されている: (i) 一度に非ゼロのグループを追加する機能 (1ラウンドあたり1つの非ゼロではなく)、および (ii) 各ラウンドでいくつかの原子をサポートから破棄するプルーニングステップを含める。このアプローチの代表例は、サブスペース追跡アルゴリズムとCoSaMPです。^[10]

• 基底追求は、を -ノルムに置き換えることで、問題の凸緩和バージョンを解きます。これは新しい目的を定義するだけで、目的の解を得るために使用するアルゴリズムの問​​題は未解決のままであることに注意してください。一般的に考えられているそのようなアルゴリズムには、IRLS、LARS、および反復ソフト収縮法があります。^[11]${\displaystyle \ell_{0}}$${\displaystyle \ell_{1}}$

• スパース分解問題を解決する方法は他にもいくつかあります。ホモトピー法、座標降下法、反復ハード閾値法、上記の反復ソフト収縮アルゴリズムに関連する一次近似法、および Dantzig セレクターなどです。

スパース近似のアイデアとアルゴリズムは、信号処理、画像処理、機械学習、医療用画像処理、アレイ処理、データマイニングなどで広く使用されています。これらのアプリケーションのほとんどでは、対象の未知の信号は、与えられた辞書からのいくつかの原子のスパースな組み合わせとしてモデル化され、これが問題の正規化として使用されます。これらの問題には通常、モデルを与えられたデータに最適に適合させることを目的とした辞書学習メカニズムが伴います。スパース性に触発されたモデルの使用は、幅広いアプリケーションで最先端の結果をもたらしました。^{[12] [13] [14]}最近の研究では、スパース表現モデリングとディープラーニングの間に密接な関係があることが示唆されています。^[15]${\displaystyle D}$

• 圧縮センシング
• スパース辞書学習
• K-SVD
• ラッソ（統計）
• 正則化（数学）と逆問題