Dictionary Learning - Sparse Representations and Compressive Sensing for Imaging and Vision - page 83

Chapter 6
Dictionary Learning

Instead of using a pre-determined dictionary B , as in (5.1), one can directly learn
it from the data [99]. Indeed, it has been observed that learning a dictionary
directly from the training data rather than using a predetermined dictionary usually
leads to better representation and hence can provide improved results in many
practical image processing applications such as restoration and classification [121],
[155], [100], ,[40], [107], [131], [133]. In this section, we will highlight some
of the methods for learning dictionaries and present their applications in object
representation and classification.

6.1 Dictionary Learning Algorithms

Several algorithms have been developed for the task of learning a dictionary. Two of
the most well-known algorithms are the Method of Optimal Directions (MOD) [58]
and the KSVD algorithm [2]. Given a set of examples X

, the goal of
the KSVD and MOD algorithms is to find a dictionary B and a sparse matrix

=[ x 1 ,···, x n ]

Γ that

minimize the following representation error

B ˆ

2
F subject to

( , Γ )= arg min

B , Γ

X − B Γ γ i 0 ≤ T 0 ∀ i ,

where and T 0 denotes the sparsity level. Both MOD

and KSVD are iterative methods and alternate between sparse-coding and dictionary
update steps. First, a dictionary B with

γ i represent the columns of Γ

2 normalized columns is initialized. Then,
the main iteration is composed of the following two stages:

• Sparse coding : In this step, B is fixed and the following optimization problem is

solved to compute the representation vector

γ i for each example x i

2
2

i = 1 ,···, n , min

γ i

x i − B γ i s. t. γ i 0 ≤ T 0 .