Digital Signal Processing Reference
In-Depth Information
Algorithm 8:
The MOD and KSVD dictionary learning algorithms
Objective:
Find the best dictionary to represent the samples
X
=[
x
1
,···,
x
n
]
as sparse
compositions, by solving the following optimization problem:
2
F
sub ject to
∀
i
γ
i
0
≤
T
0
.
arg min
B
,
Γ
X
−
B
Γ
Input:
Initial dictionary
B
(
0
)
∈
R
N
×
P
, with normalized columns, signal matrix
X
=[
and sparsity level
T
0
.
1.
Sparse coding stage
:
Use any pursuit algorithm to approximate the solution of
x
1
,···,
x
n
]
2
2
ˆ
γ
i
=
arg min
x
i
−
B
γ
sub ject to
γ
0
≤
T
0
obtaining sparse representation vector
ˆ
γ
i
for 1
≤
ı
≤
n
.
These form the matrix Γ
.
2.
Dictionary update stage
:
MOD:
Update the dictionary by the formula
ΓΓ
−
1
T
T
B
=
X
Γ
.
P
in
B
(
J
−
1
)
update by
- Define the group of examples that use this atom,
KSVD:
For each column
k
=
1
,···,
T
k
ω
k
=
{
i
|
1
≤
i
≤
P
,
γ
(
i
)
=
0
}.
- Compute the overall representation error matrix,
E
k
,
by
−
j
=
k
b
j
γ
j
E
k
=
X
.
ω
k
and obtain
E
k
.
- Restrict
E
k
by choosing only the columns corresponding to
- Apply SVD decomposition
E
k
=
V
T
Select the updated dictionary column
b
k
to be the first column of
U
. Update the coefficient vector
U
Δ
.
k
R
to be the first column
γ
of
V
multiplied by
Δ
(
1
,
1
)
.
1.
Output:
Trained dictionary
B
and sparse coefficient matrix
3. Set
J
=
J
+
Γ
.
wavelet packets [59]. Recently, similar algorithms for simultaneous sparse signal
representation and discrimination have also been proposed in [71, 75, 81, 101, 119].
The basic idea in learning a discriminative dictionary is to add a Linear Discriminant
Analysis (LDA) type of discrimination on the sparse coefficients which essentially
enforces separability among dictionary atoms of different classes. Some of the other
methods for learning discriminative dictionaries include [73,81-84,164]. Additional
techniques may be found within these references.
In particular, a dictionary learning method based on information maximization
principle was proposed in [115] for action recognition. The objective function in
[115] maximizes the mutual information between what has been learned and what
remains to be learned in terms of appearance information and class distribution
Search WWH ::
Custom Search