Digital Signal Processing Reference
In-Depth Information
Algorithm 3:
Kernel Orthogonal Matching Pursuit (KOMP) Algorithm
Input:
N
×
L
dictionary
B
=[
b
1
,···,
b
L
]
,sample
y
, kernel function κ , and stopping
criterion.
Initialize:
Compute kernel matrix
L
×
L
K
BB
∈
R
(
i
,
j
)
κ
(
b
i
,
b
j
)
whose
th entry is
, and vector
L
whose entries are
K
B
∈
R
κ
(
b
i
,
y
)
. Set index set
Λ
0
to be index corresponding to the largest
entry in
1.
While stopping criterion has been been met do
1. Compute the correlation vector
c
K
B
and iteration counter
t
=
T
=[
c
1
,···,
c
L
]
by
= K
B
−
(K
BB
)
:
,
Λ
t
−
1
(K
BB
)
Λ
t
−
1
,
Λ
t
−
1
−
1
c
(K
B
)
Λ
t
−
1
.
2. Select the new index set as
λ
t
=
arg max
i
L
|
c
i
|.
=
1
,···,
3. Update the index set
1
Λ
=
Λ
{
λ
}.
t
t
−
t
4.
t
←
t
+
1.
Output:
Index set Λ
=
Λ
t
−
1
,
the sparse representation
ˆ
α
whose nonzero entries indexed by
α
=
(K
BB
)
Λ
,
Λ
−
1
are
ˆ
(K
B
)
Λ
.
Λ
containing
T
input signals of dimension
N
. Then, the objective is to find a row-
sparse matrix
S
so that
X
BS
,where
B
is the dictionary. One can recover the
row-sparse matrix by solving the following optimization problem [140], [139]
≈
S
=
arg max
X
−
BS
F
subject to
S
row
,
0
≤
C
0
,
(5.17)
where
S
row
,
0
denotes the number of non-ze
ro rows
of
S
and
X
F
is the Frobenius
∑
i
,
j
X
i
,
j
.
norm of matrix
X
defined as
The problem (
5.17
) can be
approximately solved by the Simultaneous Orthogonal Matching Pursuit (SOMP)
algorithm [140].
The above joint sparsity model can be extended to the feature space and the row-
sparse matrix
S
can be recovered by solving the following optimization problem
X
F
=
S
=
S
F
S
row
,
0
≤
arg max
φ
(
X
)
−
φ
(
B
)
subject to
C
0
,
(5.18)
where
. Kernelized SOMP (KSOMP) can be used to solve
the above optimization problem [41]. In KSOMP, at every iteration the dictionary
atom that simultaneously yields the best approximation to all the
T
examples is
selected. Let
C
φ
(
X
)=[
φ
(
x
1
)
,···,
φ
(
x
T
)]
L
×
T
∈
R
be the correlation correlation matrix whose
(
i
,
j
)
th entry
is the correlation between
φ
(
b
i
)
and
φ
(
r
j
)
,where
φ
(
r
j
)
is the residual vector of
φ
(
. The new atom is then selected as the one associated with the row of
C
which
has the maximal
x
j
)
1. The different steps of the algorithm for
approximately solving (
5.18
) is summarized in Algorithm
4
.
p
norm for some
p
≥
Search WWH ::
Custom Search