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.

barbara_patches.png

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

Dictionary learning reduced sparse expression errors.

Barbara_K-SVD.png

K-SVD algorithm

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

task:

\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

Initialization:

As $ k = 0 $

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.

Main loop:

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 $.

  1. Define a case set using atom $ a_ {j_ {0}} . $ \ Omega_ {j_ {0}} = \ {i | 1 \ leq i \ leq M, X [j_ {0}, i] \ neq 0 \} $$

  2. Calculate the residual matrix. $ E_ {j_ {0}} = Y-\ Sigma_ {j \ neq j_ {0}} a_ {j} x_ {j} ^ {T} $

  3. Extract only the column corresponding to $ \ Omega_ {j_ {0}} $ from $ E_ {j_ {0}} $ and set it as $ E_ {j_ {0}} ^ {R} $.

  4. 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.

output:

Get the result $ A $.

reference

Recommended Posts

Dictionary learning algorithm
Introduction to dictionary lookup algorithm
Other applications of dictionary learning
Machine learning algorithm (simple perceptron)
Machine learning algorithm (support vector machine)
Machine learning algorithm (logistic regression)
<Course> Machine Learning Chapter 6: Algorithm 2 (k-means)
Machine learning algorithm (support vector machine application)
Machine learning algorithm (multiple regression analysis)
Machine learning algorithm (simple regression analysis)
Machine learning algorithm (gradient descent method)
real-time-Personal-estimation (learning)
Algorithm gymnastics 12
Machine learning algorithm (generalization of linear regression)
Algorithm gymnastics 10
Algorithm exercise 6
Algorithm gymnastics 9
Algorithm gymnastics 14
Algorithm gymnastics 2
Learning record
Algorithm gymnastics 7
Algorithm Gymnastics 15
Python algorithm
Dictionary type 2
Algorithm Gymnastics 16
Dictionary type 1
Learning record # 3
Learning record # 1
Machine learning
Machine learning algorithm (implementation of multi-class classification)
Algorithm gymnastics 8
python learning
Machine learning algorithm classification and implementation summary
Algorithm exercises 13
Algorithm Gymnastics 17
Learning record # 2
Algorithm Gymnastics 18
Python dictionary
6/10 Learning content
Algorithm gymnastics 11
Deep Learning
Algorithm gymnastics 5
Algorithm gymnastics 4
Machine learning algorithm (linear regression summary & regularization)
numpy-sigmoid learning
[Python] dictionary
Python dictionary
Try OpenAI's standard reinforcement learning algorithm PPO
Gaussian mixed model EM algorithm [statistical machine learning]
Learning neural networks using the genetic algorithm (GA)