K-SVD
応用数学では、K-SVDは、特異値分解アプローチを介して、スパース表現の辞書を作成するための辞書学習アルゴリズムです。K-SVDは、k-meansクラスタリング手法の一般化であり、現在の辞書に基づいて入力データをスパースコーディングすることと、データにさらに適合するように辞書内のアトムを更新することを繰り返し繰り返すことによって機能します。これは、期待値最大化（EM）アルゴリズムに構造的に関連しています。 K-SVDは、画像処理、音声処理、生物学、文書分析などのアプリケーションで広く使用されています。
コンテンツ
1 K-SVDアルゴリズム
2 制限事項
3 も参照してください
4 参考文献
K-SVDアルゴリズム
K-SVDは、次のようにK-meansの一種の一般化です。k-meansクラスタリングは、スパース表現の方法と見なすこともできます。つまり、データサンプルを表すために可能な限り最良のコードブックを見つける
{{y I } I = 1 M
{ {y_ {i} } _ {i = 1} ^ {M}}
最近傍によって、解くことによって分 D X
{{‖ Y − DX
‖ 2 } 対象
∀I X I = e k
いくつかのための
k { quad min limits _ {D、X} { | Y-DX | _ {F} ^ {2} } qquad { text {subject to}} forall i、x_ { i} = e_ {k} { text {forsome}}k。}
分 D X
{{‖ Y − DX
‖ 2 } 対象 ∀ I ‖XI ‖ = 1 { quad min Limits _ {D、X} { | Y-DX | _ {F} ^ {2} } qquad { text {subject to}} quad forall i、 | x_ {i} | _ {0} = 1}
。
文字Fは、フロベニウスの規範を示します。スパース表現用語XI e k
{ x_ {i} = e_ {k}}
辞書で1つのアトム（列）のみを使用するようにK-meansアルゴリズムを適用します D { D}
。この制約を緩和するために、K-SVDアルゴリズムの目標は、信号を原子の線形結合として表すことです。 D { D}
。
K-SVDアルゴリズムは、K-meansアルゴリズムの構築フローに従います。ただし、K-meansとは反対に、原子の線形結合を実現するために D { D}
、制約のスパース項が緩和され、各列の非ゼロエントリの数が緩和されますX I { x_ {i}}
1より大きくても、数より小さくてもかまいませんT 0
{ T_ {0}}
。
したがって、目的関数は次のようになります。分 D X
{{‖ Y − DX
‖ 2 } 対象 ∀ I ‖XI ‖
0≤ T
0 { quad min Limits _ {D、X} { | Y-DX | _ {F} ^ {2} } qquad { text {subject to}} quad forall i ;、 | x_ {i} | _ {0} leqT_{0}。}
または別の客観的な形で分 D X ∑
I‖X I ‖ 0 対象 ∀ I ‖Y − DX
‖ 2 ≤ ϵ { quad min Limits _ {D、X} sum _ {i} | x_ {i} | _ {0} qquad { text {subject to}} quad forall i ; 、 | Y-DX | _ {F} ^ {2} leqepsilon。}
K-SVDアルゴリズムでは、 D { D}
最初に固定され、最良の係数行列X
{ X}
見つかった。本当に最適なものを見つけるようにX
{ X}
不可能な場合は、近似追跡法を使用します。OMP、直交マッチング追跡などの任意のアルゴリズムは、固定された所定の数の非ゼロエントリを持つソリューションを提供できる限り、係数の計算に使用できます。T 0
{ T_ {0}}
。
スパースコーディングタスクの後、次はより良い辞書を検索することです D { D}
。ただし、辞書全体を一度に見つけることは不可能であるため、プロセスは辞書の1つの列のみを更新することです。 D { D}
毎回、修正しながらX
{ X}
。の更新 k { k}
-番目の列は、ペナルティ項を次のように書き換えることによって行われます。‖ Y − DX
‖ 2= ‖
Y− ∑
j= 1 K d jX j T ‖ F =0 =1 =2（（ Y− ∑ j ≠ k d jX j T
）。− d kX k T ‖ F 2 = −0 −1 −2 −3d kX k T ‖ 2 { | Y-DX | _ {F} ^ {2} = left | Y- sum _ {j = 1} ^ {K} d_ {j} x_ {j} ^ {T} right | _ {F} ^ {2} = left | left（Y- sum _ {j neq k} d_ {j} x_ {j} ^ {T} right）-d_ {k} x_ {k} ^ {T} right | _ {F} ^ {2} = | E_ {k} -d_ {k} x_ {k} ^ {T} | _ {F} ^ {2} }
どこXk T
{ x_ {k} ^ {T}}
Xのk番目の行を示します。
乗算を分解することによって DX { DX}
の合計に K { K}
ランク1の行列、他の行列を想定できますK − 1
{ K-1}
用語は固定されていると見なされ、 k { k}
-thは不明のままです。このステップの後、最小化問題を近似することで解決できます。E k
{ E_ {k}}
ra n k − 1
{ランク-1}
特異値分解を使用した行列、次に更新d k
{ d_ {k}}
それと。ただし、ベクトルの新しいソリューションXk T
{ x_ {k} ^ {T}}
スパース性の制約が適用されていないため、いっぱいになる可能性が非常に高くなります。
この問題を解決するには、次のように定義しますω k
{ omega _ {k}}
なので ω k = {{I ∣ 1 ≤ I ≤ N X k T（（ 私
）。≠ 0
} { omega _ {k} = {i mid 1 leq i leq N、x_ {k} ^ {T}（i） neq 0 }、}
例を示しています
{{y I } I = 1 N
{ {y_ {i} } _ {i = 1} ^ {N}}
アトムを使用するd k
{ d_ {k}}
（またのエントリX I { x_ {i}}
それはゼロ以外です）。次に、定義しますΩ k
{ Omega _ {k}}
サイズのマトリックスとして N ×× | ωk |
{ N times | omega _ {k} |}
、上にあるもの（（ I ω k （（ 私 ）。 ）。-番目 {（i、 omega _ {k}（i））{ text {-th}}、}
それ以外の場合はエントリとゼロ。掛けるときX〜 k T X k T Ω k
{ { tilde {x}} _ {k} ^ {T} = x_ {k} ^ {T} Omega _ {k}}
、これは行ベクトルを縮小しますXk T
{ x_ {k} ^ {T}}
ゼロエントリを破棄します。同様に、乗算Y 〜 k=Y Ω k
{ { tilde {Y}} _ {k} = Y Omega _ {k}}
を使用して現在使用されている例のサブセットです。d k
{ d_ {k}}
原子。同じ効果が見られますE 〜 k=E k Ω k
{ { tilde {E}} _ {k} = E_ {k} Omega _ {k}}
。
したがって、前述の最小化問題は次のようになります。‖ E k Ω
k− d kX k T Ω k ‖ 2= ‖ E 〜
k− d kX 〜
k T ‖ 2
{ | E_ {k} Omega _ {k} -d_ {k} x_ {k} ^ {T} Omega _ {k} | _ {F} ^ {2} = | { tilde {E}} _ {k} -d_ {k} { tilde {x}} _ {k} ^ {T} | _ {F} ^ {2}}
SVDを直接使用して実行できます。SVDは分解しますE 〜 k
{ { tilde {E}} _ {k}}
の中へU Δ V T
{ U Delta V ^ {T}}
。の解決策d k
{ d_ {k}}
Uの最初の列、係数ベクトルですX〜 k T
{ { tilde {x}} _ {k} ^ {T}}
の最初の列として V ×× Δ （（ 1 1 ）。 { V times Delta（1，1）}
。辞書全体を更新した後、プロセスはXを繰り返し解き、次にDを繰り返し解きます。
制限事項
データセットに適切な「辞書」を選択することは凸問題ではなく、K-SVDは反復更新によって動作しますが、これはグローバルな最適化を見つけることを保証するものではありません。ただし、これはこの目的のための他のアルゴリズムに共通であり、K-SVDは実際にはかなりうまく機能します。
も参照してください
スパース近似
特異値分解
行列ノルム
K-meansクラスタリング
低ランク近似
参考文献
^ ミハルアハロン; Michael Elad; Alfred Bruckstein（2006）、「K-SVD：スパース表現のための過剰な辞書を設計するためのアルゴリズム」 （PDF）、信号処理に関するIEEEトランザクション、54（11）：4311–4322、Bibcode：2006ITSP … 54.4311A、doi：10.1109 / TSP.2006.881199、S2CID 7477309
^ Rubinstein、R.、Bruckstein、AM、and Elad、M.（2010）、 “”Dictionaries for Sparse Representation Modeling”、Proceedings of the IEEE、98（6）：1045-1057、CiteSeerX 10.1.1.160.527、doi：10.1109 / JPROC.2010.2040551、S2CID 2176046
“