[PYTHON] Dictionary learning algorithm

Sparse modeling The dictionary learning algorithm of Chapter 12 was implemented in jupyter notebook. Link to jupyter notebook

result

About 25,000 8x8 patches were extracted from Barbara and dictionary learning was performed.

Two-dimensional separable DCT dictionary as the initial value A dictionary learned from patches using the K-SVD method

Dictionary learning reduced sparse expression errors.

Signal case $ Y: n \ times M $ (n is the signal dimension, M is the number of cases)
Sparse representation $ X: m \ times M $ (m is the dimension of the sparse representation vector)
Dictionary $ A: n \ times m $

Sparsely represent $ y_i $ with $ x_i $ where only $ k_0 $ elements are nonzero.

\min_{A,\{x_i\}^{M}_{1}} \Sigma_{i=1}^{M} ||y_i-Ax_i|| \text{ subject to } ||x_{i}||_0 \leq k_{0}, 1 \leq i \leq M

As $ k = 0 $

Initial dictionary: First, an 8 × 11 one-dimensional DCT matrix $ A_ {1D} $ was created. The $ k $ th atom $ (k = 1,2, \ dots, 11) $ is

a^{1D}_{k}=\cos((i-1)(k-1)\pi/11),(i=1,2,\dots,8)

Is. Kronecker product, subtracting the average except for the first atom

A_{2D} = A_{1D} \otimes A_{1D}

An initial dictionary was generated using.

Set $ k \ leftarrow k + 1 $ and perform the following steps.

\hat{x_{i}} = \arg \min_{x} ||y_{i} - Ax||_{2}^{2} \text{ subject to } ||x||_{0} \leq k_{0}

Then we get the sparse representation vector $ \ hat {x} _ {i} $ for $ 1 \ leq i \ leq M $. Use these to construct the matrix $ X $.

Update K-SVD dictionary: Follow the steps below to update the dictionary columns and get $ A $. Iterate over $ j_0 = 1,2, \ dots, m $.

Define a case set using atom $ a_ {j_ {0}} . $ \ Omega_ {j_ {0}} = \ {i | 1 \ leq i \ leq M, X [j_ {0}, i] \ neq 0 \} $$
Calculate the residual matrix. $ E_ {j_ {0}} = Y-\ Sigma_ {j \ neq j_ {0}} a_ {j} x_ {j} ^ {T} $
Extract only the column corresponding to $ \ Omega_ {j_ {0}} $ from $ E_ {j_ {0}} $ and set it as $ E_ {j_ {0}} ^ {R} $.
Apply $ SVD $ and set $ E_ {j_ {0}} ^ {R} = U \ Delta V $. And the dictionary atom $ a_ {j_ {0}} = u_ {1} $, the expression vector is $ x_ {j_ {0}} ^ {R} = \ Delta [1, 1] v_ {1} ^ {T } Update as $.

*Stop condition: If||Y - AX||^{2}_{F}If the change in is small enough, it ends, otherwise it repeats.

Get the result $ A $.