Digital Signal Processing Reference
In-Depth Information
Equation (
5.7
) is known as the
normal equation
. It can be shown that the normal
equation always has a solution.
3
Depending on the dimension of
C
,(
5.7
) can have
one or infinite solutions:
•
n
L
:As
C
has more rows than columns, the numbers of equations in (
5.2
)
is greater than the numbers of unknowns in
w
. It is said that the system in (
5.2
)
is a overdetermined one. In this case there will be one or an infinite number of
solutions to (
5.7
), depending on the column rank of
C
.If
C
has full column rank
the solution is unique. If it is column rank deficient there exist an infinite number
of solutions.
≥
•
n
: In this case
C
has more columns than rows. That is, in (
5.2
) there are more
unknowns than equations. It is said that the system in (
5.2
) is an underdetermined
one. In this case, the number of solutions to (
5.7
) is always infinite. This is because
C
would always be column rank deficient.
The most common situation, at least in adaptive filtering,
4
will be the first one, in
which
n
L
<
≥
L
. Suppose then that
C
has full column rank. It can be easily shown that
C
T
C
L
has full rank and is invertible. It is obvious that the solution to (
5.7
)
is unique and:
L
×
∈ R
C
T
C
−
1
C
T
d
w
ˆ
=
.
(5.8)
When
C
has not full column rank, the inverse of
C
T
C
does not exist. In this case,
the number of solutions to (
5.7
) is infinite. It is clear that as
C
T
C
is singular, any
solution to (
5.7
) can be put as:
w
ˆ
= ˆ
w
p
+ ˆ
w
h
,
(5.9)
where
w
p
is any solution to (
5.7
) and
ˆ
w
h
is any solution to:
ˆ
C
T
C
w
h
=
ˆ
0
,
(5.10)
N
C
T
C
,
5
the null space of
C
T
C
, which can be easily
that is,
w
h
is any vector in
ˆ
seen to be equal to
N (
C
)
. It is also clear that the difference between two solutions
w
1
and
.
A natural question when (
5.7
) has multiple solutions is which one would be the
best choice. There is no simple answer to that problem. A common choice would be
the following:
ˆ
w
2
is a vector belonging to
ˆ
N (
C
)
2
C
T
d
C
T
Cw
w
ˆ
=
arg min
w
L
w
subject to
=
.
(5.11)
∈R
3
Notice that
R
C
T
C
=
R
C
T
[
3
], where
R (
denotes the range or column space of the
matrix
A
. This implies that it should exist at least one
w
which satisfies Eq. (
5.7
).
4
In recent years there was a growing interest in underdetermined systems with sparseness conditions
on the solution. This is commonly known as
compressed sensing
or
compressed sampling
.The
interested reader can see [
4
] and the references therein.
5
As
C
T
C
is singular
N
C
T
C
contains others vectors besides the null vector.
A
)