k-SVD

応用数学において、k -SVDは、特異値分解アプローチを介してスパース表現の辞書を作成する辞書学習アルゴリズムです。k -SVDはk-平均法クラスタリング法の一般化であり、現在の辞書に基づいて入力データをスパースコーディングすることと、辞書内の原子を更新してデータに適合させることを交互に繰り返します。構造的には期待値最大化（EM）アルゴリズムに関連しています。^{[1] [2]} k -SVDは、画像処理、音声処理、生物学、文書分析などのアプリケーションで広く使用されています。

k -SVDは、次のようにk -meansの一般化の一種です。k - meansクラスタリングは、スパース表現 の手法とも考えられます。つまり、データサンプルを最近傍 で表現するための最適なコードブックを見つけるには、次を解きます。 ${\displaystyle \{y_{i}\}_{i=1}^{M}}$

${\displaystyle \quad \min \limits _{D,X}\{\|Y-DX\|_{F}^{2}\}\qquad {\text{subject to }}\forall i,x_{i}=e_{k}{\text{ for some }}k.}$

これはほぼ

${\displaystyle \quad \min \limits _{D,X}\{\|Y-DX\|_{F}^{2}\}\qquad {\text{subject to }}\quad \forall i,\|x_{i}\|_{0}=1}$

これは「重み」を許可する k-means です。

文字 F はフロベニウスノルムを表します。スパース表現項は、k -means アルゴリズムが辞書 内の 1 つの原子 (列) のみを使用するように強制します。この制約を緩和するために、 k -SVD アルゴリズムのターゲットは、信号を 内の原子の線形結合として表現することです。 ${\displaystyle x_{i}=e_{k}}$${\displaystyle D}$${\displaystyle D}$

k -SVD アルゴリズムは、k -means アルゴリズムの構築フローに従います。ただし、 k -meansとは対照的に、 内の原子の線形結合を実現するために、制約のスパース項が緩和され、各列の非ゼロエントリの数は1 より大きく、数 未満になります。 ${\displaystyle D}$${\displaystyle x_{i}}$${\displaystyle T_{0}}$

したがって、目的関数は

${\displaystyle \quad \min \limits _{D,X}\{\|Y-DX\|_{F}^{2}\}\qquad {\text{subject to }}\quad \forall i\;,\|x_{i}\|_{0}\leq T_{0}.}$

または他の客観的な形で

${\displaystyle \quad \min \limits _{D,X}\sum _{i}\|x_{i}\|_{0}\qquad {\text{subject to }}\quad \forall i\;,\|Y-DX\|_{F}^{2}\leq \epsilon .}$

k -SVD アルゴリズムでは、まず が固定され、最適な係数行列が検索されます。本当に最適な を見つけるのは難しいため、近似追跡法を使用します。OMP、直交マッチング追跡などのアルゴリズムは、固定された所定の数の非ゼロエントリを持つソリューションを提供できる限り、係数の計算に使用できます。 ${\displaystyle D}$${\displaystyle X}$${\displaystyle X}$${\displaystyle T_{0}}$

スパースコーディングタスクの後、次はより良い辞書を探すことです。しかし、辞書全体を一度に見つけることは不可能なので、そのプロセスでは辞書の1列だけを毎回更新し、 を固定します。 -番目の列の更新は、ペナルティ項を次のように書き換えることで行われます 。${\displaystyle D}$${\displaystyle D}$${\displaystyle X}$${\displaystyle k}$

${\displaystyle \|Y-DX\|_{F}^{2}=\left\|Y-\sum _{j=1}^{K}d_{j}x_{j}^{\text{T}}\right\|_{F}^{2}=\left\|\left(Y-\sum _{j\neq k}d_{j}x_{j}^{\text{T}}\right)-d_{k}x_{k}^{\text{T}}\right\|_{F}^{2}=\|E_{k}-d_{k}x_{k}^{\text{T}}\|_{F}^{2}}$

ここで、 はXのk番目の行を表します。 ${\displaystyle x_{k}^{\text{T}}}$

乗算を階数 1 の行列の和に分解することで、他の項は固定され、 - 番目は不明のままであると想定できます。このステップの後、特異値分解を使用して項を行列で 近似し、それを使用して更新することで、最小化問題を解決できます。ただし、ベクトルの新しい解がスパースであるとは限りません。 ${\displaystyle DX}$${\displaystyle K}$${\displaystyle K-1}$${\displaystyle k}$${\displaystyle E_{k}}$${\displaystyle rank-1}$${\displaystyle d_{k}}$${\displaystyle x_{k}^{\text{T}}}$

この問題を解決するには、次のように 定義します。${\displaystyle \omega _{k}}$

${\displaystyle \omega _{k}=\{i\mid 1\leq i\leq N,x_{k}^{\text{T}}(i)\neq 0\},}$

これは、 atom を使用する例を指します( のエントリも非ゼロです)。次に、をサイズ の行列として定義します。この行列では、エントリは 1 で、それ以外は 0 です。 を乗算すると、ゼロ エントリが破棄されて行ベクトルが縮小されます。同様に、乗算は、 atom を使用している現在の例のサブセットです。 でも同じ効果が得られます。 ${\displaystyle \{y_{i}\}_{i=1}^{N}}$${\displaystyle d_{k}}$${\displaystyle x_{i}}$${\displaystyle \Omega _{k}}$${\displaystyle N\times |\omega _{k}|}$${\displaystyle (i,\omega _{k}(i)){\text{th}}}$${\displaystyle {\tilde {x}}_{k}^{\text{T}}=x_{k}^{\text{T}}\Omega _{k}}$${\displaystyle x_{k}^{\text{T}}}$${\displaystyle {\tilde {Y}}_{k}=Y\Omega _{k}}$${\displaystyle d_{k}}$${\displaystyle {\tilde {E}}_{k}=E_{k}\Omega _{k}}$

したがって、前述の最小化問題は、

${\displaystyle \|E_{k}\Omega _{k}-d_{k}x_{k}^{\text{T}}\Omega _{k}\|_{F}^{2}=\|{\tilde {E}}_{k}-d_{k}{\tilde {x}}_{k}^{\text{T}}\|_{F}^{2}}$

SVD を直接使用して実行できます。SVD はに分解されます。 の解はU の最初の列、係数ベクトルはの最初の列です。辞書全体を更新した後、プロセスは X を反復的に解き、次に D を反復的に解きます。 ${\displaystyle {\tilde {E}}_{k}}$${\displaystyle U\Delta V^{\text{T}}}$${\displaystyle d_{k}}$${\displaystyle {\tilde {x}}_{k}^{\text{T}}}$${\displaystyle V\times \Delta (1,1)}$

データセットに適切な「辞書」を選択することは非凸問題であり、k -SVDは反復更新によって動作しますが、これはグローバル最適値を見つけることを保証しません。^[2]ただし、これはこの目的の他のアルゴリズムに共通しており、k -SVDは実際にはかなりうまく機能します。^{[2] [より良いソースが必要]}

• スパース近似
• 特異値分解
• 行列ノルム
• k平均法クラスタリング
• 低ランク近似