Digital Signal Processing Reference
In-Depth Information
where
y
is an
N
1 signal vector, which can be represented as a linear combi-
nation of the columns (often called basis vectors or atoms) of a dictionary matrix
D
×
,
w
is the representation coefficient vector. When
w
has only
a small number of nonzero elements, this representation is called a sparse represen-
tation. Considering also that the signal vector
y
is the sum of
K
source vectors
s
i
(
i
=[
d
1
,
d
2
,...,
d
M
]
=
1
,
2
...,K
), one has
K
y
=
s
i
.
(14.2)
i
=
1
1
,
2
...,K
) from
y
, methods using sparse representations
assume that these sources can be sparsely represented by different dictionaries
D
To recover
s
i
(
i
=
which can be considered as the subsets of
D
. Then, the sparse
representation
w
of
y
over
D
is estimated and
s
i
is finally approximated by
w
i
D
i
,
where
w
i
is composed of the part of representation coefficients corresponding to
s
i
.
The two keys of this kind of methods are the construction of proper dictionaries
and the estimation of sparse representations over the designed dictionaries. Gen-
erally, dictionaries are designed according to the characters of source signals to
be separated and are overcomplete, meaning that the number of atoms in a con-
structed dictionary is much bigger than the number of sample points of signal vec-
tors (
M>N
). As a result, Eq. (
14.1
) is underdetermined and has infinitely many
solutions. Theoretically, the sparsest representation which has the fewest nonzero
elements is the solution of
=[
d
1
,
d
2
,...,
d
M
]
min
w
w
0
subject to
y
=
Dw
,
(14.3)
where
·
0
is the
l
0
-norm, to count the nonzero entries of a vector. The exact deter-
mination of the sparsest representation proves to be an NP-hard problem [
7
] which
means that the time required to solve the problem using any currently known algo-
rithm increases very quickly as the size of the problem grows. Thus, approximate
solutions are considered instead. In the two following sections, we will describe in
detail dictionary construction approaches and some pursuit algorithms commonly
used for estimating sparse representations.
14.2.1 Dictionary Construction
Dictionaries can be constructed by either selecting one from a prespecified set of
linear transforms or adapting the dictionary to a set of training signals.
Choosing a prespecified transform matrix is usually simpler and in many cases
it also leads to simple and fast algorithms for the evaluation of the sparse repre-
sentation. Short-time discrete Fourier transform (DFT), short-time discrete cosine
transform (DCT), and discrete wavelet transform are three kinds of commonly used
prespecified dictionary matrixes.
Search WWH ::
Custom Search