K-SVD : An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation [2006 TSP]


K-SVD는 sparse representation과 함께, 그 representation을 표현하는 dictionary (overcomplete된)를 만드는 알고리즘을 제시함.


1) 고정된 dictionary를 이용하여 sparse representation을 구하는 방법

Sparse coding


 

(in case of p=0) ; NP-hard problem.

MP : dictionary로부터 column을 하나씩 선택하는 방법으로 (greedy하게) target signal과 inner product 값이 최대가 되는 column 을 선택한다.(선택된 column은 제외하고 다음 iteration에서 반복해서 선택한다. 적절한 coefficient 값을 얻어내면 그것이 sparse coding)

OMP : 안찾아봤지만 뭐 비슷하지 않을까 생각한다.


(in case of p=1) ; convex problem.

BP : 

FOCUSS : 



2) 현재의 signal(ex: image)을 표현하는 sparse representation과 함께 dictionary 또한 학습하는 방법 (K-SVD)

Dictionary Learning

K-means : 하나의 data는 하나의 codebook vector와 연결된다


K-SVD :  K-means의 일반적인 버전(?) 으로 하나의 data는 여러 개의(sparse하게) dictionary vector와 연결될 수 있다.


iteration step
step 1) sparse coding X의 update는 D를 고정시키고 진행.
step 2) Dictionary D의 update는 column별로 하는데, update하고자하는 column을 제외한 나머지 column을 고정시키고,
update하려는 column(d_k)과 sparse coding X를 동시에 update한다.

step 2) 에서, error를 minimize 하기 위해서는 d_k와 coefficient x^k_T (X의 k번째 row vector)의 곱(rank-1 행렬)을 정해야 하는데 (이것을 정하는 과정이 update 과정임), SVD를 이용하여 E_k(고정된 나머지 column들)와 가장 오차가 적은 d_k 와 x^k_T 를 찾아낸다.

하지만 이렇게 바로 d_k와 x^k_T를 SVD를 이용하여 업데이트 하는 것에는 한가지 문제가 있다.
-> 바로 x^k_T의 sparsity를 제약해 줄 수 없다는 것이다. 
따라서 x^k_T의 non-zero elements (즉, 현재 coefficient로 d_k atom을 사용하는 index) 를 모아서(shrink) x^k_R로 압축한다. 
같은 방식으로 Y^R_k, E^R_k 와 같은 observation matrix와 error matrix도 d_k atom을 사용하는 column vector들의 집합으로 나타내어진다.

설명은 좀 복잡하지만, 간단하게 정리하자면step 2)에서 d_k 와 x^k_T를 동시에 업데이트 할 때, 

현재 x^k_T의 non-zero element만 사용함으로써 현재 x^k_T의 sparsity를 보존한 채로 그 안의 value만 update하는 것이다.


SVD rank 1 matrix 만들기 : 


Convergence에 대한 내용 : 항상 converge한다고 보장할 수는 없다..만, X를 찾는 pursuit method(step 1) 에서 T_0 의 크기를 feature vector dimension n보다 작게 하면 guaranteed 된다고 한다. (증명은?)




Posted by 헬벨