K-SVD

응용수학에서 K-SVD는 단수 값 분해 접근방식을 통해 희박한 표현을 위한 사전을 만들기 위한 사전 학습 알고리즘이다. K-SVD는 k-평균 군집화 방법을 일반화한 것으로, 현재 사전을 바탕으로 입력 데이터를 희소 코딩하고, 사전에 있는 원자를 업데이트해 데이터를 더 잘 맞히는 방식으로 동작한다. 구조적으로 기대 최대화(EM) 알고리즘과 관련이 있다.^[1]^[2] K-SVD는 영상 처리, 오디오 처리, 생물학, 문서 분석과 같은 애플리케이션에서 광범위하게 사용되고 있는 것을 발견할 수 있다.

문제 설명

사전 학습의 목표는 $K$ $K$ 신호 아톰 $K$ (이 표기법에서 $D$ ${\$ displaystyle $D}$ 열) $D$ 을 $D\in \mathbb {R} ^{n\times K}$ 포함하는 과완전한 사전 매트릭스 $D\in \mathbb {R} ^{n\times K}$ $D\in \mathbb {R} ^{n\times K}$ $D\in \mathbb {R} ^{n\times K}$ $×$ $D\in \mathbb {R} ^{n\times K}$ ${\$ K $}{n\time K}$ 를 배우는 것이다. 신호 벡터 $y\in \mathbb {R} ^{n}$ $y=Dx$ $y\in \mathbb {R} ^{n}$ $y\in \mathbb {R} ^{n}$ $y\in \mathbb {R} ^{n}$ ${\$ ^{ $n}}$ 은 $($ 는) 이러한 원자의 선형 결합으로 희박하게 나타낼 수 있다 $y\in \mathbb {R} ^{n}$ . $y$ $y$ 을(를 $y$ 나타내려면 표현 $벡터$ x ${\displaystyle$ y $}$ $y=Dx$ 대략적인 $y\approx Dx$ 를 충족해야 한다 $x$ $y=Dx$ $y\approx Dx$ $y\approx Dx$ $y\approx Dx$ ${\displaystyle y\$ 약 $Dx}$ 은 $y\approx Dx$ 는) 일부 작은 값 $ε$ 과 L 표준에_p 대해 $\|y-Dx\|_{p}\leq \epsilon$ y - $\|y-Dx\|_{p}\leq \epsilon$ $\|y-Dx\|_{p}\leq \epsilon$ $\|y-Dx\|_{p}\leq \epsilon$ p $\|y-Dx\|_{p}\leq \epsilon$ $\y-Dx\ _{p}\leq \epsilon$ 을(를) 요구하여 정밀하게 했다. 벡터 $x\in \mathbb {R} ^{K}$ $x\in \mathbb {R} ^{K}$ $x\in \mathbb {R} ^{K}$ K ${\$ 는 $신호$ y $y$ 의 표현 계수를 포함하고 $x\in \mathbb {R} ^{K}$ 있으며 $y$ 일반적으로 $표준$ p $p$ 은 $L 1$ , $L$ 로₂_∞ 선택된다 $p$ .

$n<K$ < $n<K$ $n<K$ 과 $n<K$ D가 전체 순위 매트릭스인 경우 표현 문제에 대해 무한히 많은 해결책을 사용할 수 있다. 따라서 제약을 용액에 설정해야 한다. 또한 첨사성을 보장하기 위해 0이 아닌 계수가 가장 적은 용액을 선호한다. 따라서 첨사성 표현은 다음 중 하나의 해결책이다.

{\displaystyle (P_{0})\quad \min \limits _{x}\x\ _{0}\qquad {\text{{}}}}}}}}}}}}}y=Dx}의 대상

또는

(P_{0,\epsilon })\quad \min \limits _{x}\x\ _{0}\qquad {\text{{}}}}\y-Dx\ _{2}\leq \epsilon}}}}

여기서 $\|x\|_{0}$ $\|x\|_{0}$ $\|x\|_{0}$ 0 ${\$ \ $x\ _{0}$ 은(는) 벡터 $x$ $x$ 에서 0이 아닌 항목을 카운트한다 $\|x\|_{0}$ $x$ 영점 "norm" 참조).

K-SVD 알고리즘

K-SVD는 K-Means의 일종으로 다음과 같다. k-평균 군집화는 또한 희박한 표현 방법으로 간주될 수 있다. 즉, 데이터 샘플 $\{y_{i}\}_{i=1}^{M}$ { $\{y_{i}\}_{i=1}^{M}$ i $\{y_{i}\}_{i=1}^{M}$ i $\{y_{i}\}_{i=1}^{M}$ = $\{y_{i}\}_{i=1}^{M}$ ${\$ 을(를) 가장 가까운 이웃에 의해 $\{y_{i}\}_{i=1}^{M}$ 나타낼 수 있는 최선의 코드북을 찾는 것이다.

\quad \min \limits _{D,X}\{\Y-DX\_{F}^{2}\}\qquad {\text{}}}}}}}}\{x_{i}=e_{k}{}}}}}}}}}}}}{{{{}}}}텍스트 텍스트{}}}}}}}}}}}}}}}}}}}}}}{{{{{{{{}}}}}}}}}}}}}}}}

에 해당하는

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

.

F라는 글자는 프로베니우스 규범을 나타낸다. 희소 표현 용어 $x_{i}=e_{k}$ $x_{i}=e_{k}$ = $x_{i}=e_{k}$ $x_{i}=e_{k}$ ${\$ 는 사전 $D$ ${\displaystyle$ D $}$ 에서 K-평균 알고리즘이 하나의 원자(열)만을 사용하도록 강제하고 $x_{i}=e_{k}$ 있다 $D$ 이 제약을 완화하기 위해 K-SVD 알고리즘의 대상은 $D$ ${\displaystystyle D$ 에서 원자의 선형 조합으로 신호를 나타내는 것이다.

K-SVD 알고리즘은 K-평균 알고리즘의 구성 흐름을 따른다. 그러나 K-평균과는 반대로 $D$ $D$ 에서 원자의 선형 결합을 달성하기 위해 각 열 $x_{i}$ $x_{i}$ ${\$ 의 0이 아닌 항목 수가 $T_{0}$ 보다 많으나 $x_{i}$ 숫자 T $T_{0}$ ${\$ 보다 작을 수 있도록 제약조건의 첨사성 항을 완화한다 $T_{0}$

그래서 객관적 기능은

\quad \min \limits _{D,X}\{\Y-DX\ _{F}^{2}\}\qquad {\}}}\text{{quad 대상 }}}}\cH00\{i}\{0}leq T_{0}}}}}}}}

또는 다른 목적의 형태로

\quad \min \limits _{D,X}\sum _{i}\{0}\qquad {\text{{text}}}}}}}}}}모든 i\에 대한 \quad \;,\Y-DX\{F}^}\leq \epsilon.}}}

K-SVD 알고리즘에서는 $D$ $D$ 이(가) 먼저 고정되고 최상의 $D$ 계수 행렬 $X$ ${\displaystyle$ X $}$ 이 $X$ (가) 발견된다. 진정으로 최적의 $X$ $X$ 을(를) 찾는 것은 불가능하므로 $X$ 근사추구법을 사용한다. OMP와 같은 알고리즘은 0이 아닌 입력 $T_{0}$ ${\$ 의 고정되고 미리 결정된 수의 비제로 항목으로 솔루션을 공급할 수 있는 한 계수의 계산에 사용할 수 있다 $T_{0}$

희소 코딩 작업 후 다음이 더 나은 사전 $D$ $D$ 을 검색하는 것이다 $D$ 다만, 한 번에 전체 사전을 찾는 것은 불가능하기 때문에 $X$ $X$ 을 $X$ 를) 수정하면서 $사전$ D ${\displaystyle$ D}의 열 하나만 업데이트하는 $D$ 과정이다. $k$ $k$ -th $k$ 열 업데이트는 패널티 용어를 다음과 같이 다시 작성함으로써 이루어진다.

\ Y-DX\ _{F}^{2}=\left\Y-\sum _{j=1}{j=1}^{K}d_{j}x_{j}^{j}^{j}^{j}}^{}^}}T}\\right\ _{F}^{2}=\left\\\ \left(Y-\sum _{j\neq k}d_{j}x_{j}^){{{j}^{{}^T}\\오른쪽)-d_{k}x_{k}^{T}\right\_{F}^{2}=\ E_{k}-d_{k}x_{k}^{T}\{F}^{{F}^{2}

여기서 $x_{k}^{T}$ $x_{k}^{T}$ $x_{k}^{T}$ ${\$ 는 X의 k번째 행을 나타낸다 $x_{k}^{T}$ .

곱셈 $D$ $X$ $DX$ 을(를) $K$ $K$ 순위 $K$ 1 행렬의 합으로 $DX$ 분해하면 다른 $K-1$ - 1 ${\displaysty K-1}$ 항이 $K-1$ 고정된 것으로 가정할 수 $있으며$ ,k {\ $displaysty k$ } -th는 $k$ 알 수 없는 상태로 남아 있다. 이 단계 후에는 단수 값 분해를 사용하여 r $rank-1$ $rank-1$ - $rank-1$ $순위-1$ 행렬로 $rank-1$ $E_{k}$ k ${\$ 항을 $E_{k}$ 근사하게 해결한 후 d $d_{k}$ $d_{k}$ ${\$ 를 업데이트하면 된다. 단, 첨사성 제약이 시행되지 않기 때문에 벡터 $x_{k}^{T}$ $x_{k}^{T}$ $x_{k}^{T}$ ${\$ 의 새로운 용액은 채울 가능성이 매우 높다 $x_{k}^{T}$ .

이 문제를 해결하려면 $\omega _{k}$ $\omega _{k}$ ${\$ 를 다음과 같이 $\omega _{k}$ 정의하십시오.

\omega_{k}=\{i\mid 1\leq i,x_{k}^{T}(i)\neq 0\}

$\{y_{i}\}_{i=1}^{N}$ 예제는 $d_{k}$ $d_{k}$ k $d_{k}$ {\ $displaystyle d_{$ k}}}을 $\{y_{i}\}_{i=1}^{N}$ (를 $x_{i}$ ) 사용하는 $\{y_{i}\}_{i=1}^{N}$ ${$ $y_{i}\}_{i=1}^{N}$ 을(를) 가리킨다( $d_{k}$ $x_{i}$ x i {\ $displaystyle$ x_ ${i},$ nonzero)). $(i,\omega _{k}(i)){\text{-th}},$ 다음 $(i,\omega _{k}(i)){\text{-th}},$ $\Omega _{k}$ ${\$ ${$ $k}$ 를 ( $N\times |\omega _{k}|$ , $(i,\omega _{k}(i)){\text{-th}},$ k $(i,\omega _{k}(i)){\text{-th}},$ ( $(i,\omega _{k}(i)){\text{-th}},$ ) $-th$ , {\ $displaystyle$ $_{k}}$ 크기의 $N\times |\omega _{k}|$ 행렬로 $\Omega _{k}$ 정의하십시오 $.$ ${\text{-th},$ 그 외의 항목과 $(i,\omega _{k}(i)){\text{-th}},$ 0. ${\tilde {x}}_{k}^{T}=x_{k}^{T}\Omega _{k}$ ~ ${\tilde {x}}_{k}^{T}=x_{k}^{T}\Omega _{k}$ T ${\tilde {x}}_{k}^{T}=x_{k}^{T}\Omega _{k}$ = x ${\tilde {x}}_{k}^{T}=x_{k}^{T}\Omega _{k}$ ${\tilde {x}}_{k}^{T}=x_{k}^{T}\Omega _{k}$ ${\tilde {x}}_{k}^{T}=x_{k}^{T}\Omega _{k}$ k ${\$ 을 곱하면 ${\tilde {x}}_{k}^{T}=x_{k}^{T}\Omega _{k}$ 0개의 항목을 삭제하여 $x_{k}^{T}$ 행 벡터 x $x_{k}^{T}$ ${\$ T}}}}}}}}}}}}}}}}}}}}. 마찬가지로 ${\tilde {Y}}_{k}=Y\Omega _{k}$ ${\tilde {Y}}_{k}=Y\Omega _{k}$ ~ k ${\tilde {Y}}_{k}=Y\Omega _{k}$ = ${\tilde {Y}}_{k}=Y\Omega _{k}$ ${\tilde {Y}}_{k}=Y\Omega _{k}$ k ${\tilde {Y}}_{k}=Y\Omega _{k}$ {\ $displaystyle$ {\ $tilde {\Y}_{k}=Y\Oomega_{k}}$ 는 $d_{k}$ $d_{k}$ ${\$ 원자를 $d_{k}$ 사용하여 현재에 존재하는 예제의 하위 집합이다 ${\tilde {Y}}_{k}=Y\Omega _{k}$ . ${\tilde {E}}_{k}=E_{k}\Omega _{k}$ ~ ${\tilde {E}}_{k}=E_{k}\Omega _{k}$ = ${\tilde {E}}_{k}=E_{k}\Omega _{k}$ ${\tilde {E}}_{k}=E_{k}\Omega _{k}$ ${\tilde {E}}_{k}=E_{k}\Omega _{k}$ k ${\$ 에서도 동일한 효과를 볼 수 있다 ${\tilde {E}}_{k}=E_{k}\Omega _{k}$

따라서 앞에서 언급한 최소화의 문제가

{\displaystyle \ E_{k}\Oomega_{k}-d_{k}x_{k}^{T}\Oomega _{k}\{F}^{2}=\\\\tilde{E}-d_{x}-{k}^{F}}^{{T}}}}}}}}}2}}:

그리고 SVD를 직접 사용함으로써 이루어질 수 있다. SVD decomposes ${\tilde {E}}_{k}$ into $U\Delta V^{T}$ . The solution for $d_{k}$ is the first column of U, the coefficient vector ${\tilde {x}}_{k}^{T}$ as the first column of ${\disp$ $레이스타일 V\times \Delta ($ 1 $,1$ 전체 사전을 업데이트한 후 반복적으로 X를 풀고 D를 반복적으로 해결한다.

제한 사항

데이터 집합에 적합한 "사전"을 선택하는 것은 비구체적인 문제이며, K-SVD는 글로벌 최적화를 보장하지 않는 반복적인 업데이트에 의해 작동된다.^[2] 그러나 이러한 목적을 위한 다른 알고리즘에는 흔히 있는 일이며, K-SVD는 실제로 상당히 잘 작동한다.^[2]^{[better source needed]}

참고 항목

참조

^ Michal Aharon; Michael Elad; Alfred Bruckstein (2006), "K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation" (PDF), IEEE Transactions on Signal Processing, 54 (11): 4311–4322, Bibcode:2006ITSP...54.4311A, doi:10.1109/TSP.2006.881199, S2CID 7477309
^ Jump up to: ^a ^b ^c Rubinstein, R., Bruckstein, A.M., 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 2176046CS1 maint: 여러 이름: 작성자 목록(링크)

[aharon2006-1] Michal Aharon; Michael Elad; Alfred Bruckstein (2006), "K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation" (PDF), IEEE Transactions on Signal Processing, 54 (11): 4311–4322, Bibcode:2006ITSP...54.4311A, doi:10.1109/TSP.2006.881199, S2CID 7477309

[rubinstein2010-2] Jump up to: ^a ^b ^c Rubinstein, R., Bruckstein, A.M., 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 2176046CS1 maint: 여러 이름: 작성자 목록(링크)

[1]

[2]

Search

K-SVD

네임스페이스

더

목차

문제 설명

K-SVD 알고리즘

제한 사항

참고 항목

참조