Digital Signal Processing Reference
In-Depth Information
1
2
x
Px
q
x
min
x
+
s.t.
Ax
≤
b
,
(14.9)
where
P
is supposed to be a positive-semidefinite matrix [
10
].
This general form of optimization problem is interesting in our context since a
non-negative decomposition problem with sparsity regularization can be formulated
in a CQP form as follows:
1
2
h
(
)
h
W
W
W
v
min
h
+
λ
2
I
)
h
+
(λ
1
e
−
s.t.
−
Ih
≤
0
,
(14.10)
where
0 are regularization parameters. Indeed, this CQP is equivalent to
the following regularized non-negative least squares problem:
λ
1
, λ
2
≥
1
2
1
+
λ
2
2
2
2
2
+
λ
1
2
arg min
h
v
−
Wh
h
h
.
(14.11)
r
+
∈R
The
2
-norm is a particular case of
Tikhonov regularization
which is often used in CQP because it makes the matrix
P
1
-norm penalizes less sparse vectors, and the
W
W
=
+
λ
2
I
positive-definite at least for any
λ
2
>
0 and thus makes the
problem strictly convex [
10
].
To the best of our knowledge, although similar formulations have been considered
to introduce sparsity penalization in constrained least-squares and NMF problems
(e.g., see [
11
]), there is no such formulation for non-negative decomposition of audio
signals. We are only aware of the system proposed in [
8
,
9
] which addresses sparsity
regularization by different means as discussed previously.
To solve the problem formulated in (
14.11
), we propose to update
h
iteratively by
using a multiplicative update developed in [
12
] for the specific case of non-negative
quadratic programs, i.e., for CQPs where
A
0
in (
14.9
). For a general
non-negative quadratic program, the multiplicative update of [
12
] takes the following
form:
=−
I
and
b
=
q
.
2
P
+
x
P
−
x
⊗
−
q
+
+
4
(
)(
)
x
←
x
,
(14.12)
2
P
+
x
and is proved to make the cost decrease and to converge to the global solution as
soon as
P
is positive-definite,
x
is initialized with positive values, and the problem is
non-degenerate. The problem becomes degenerate when there exists a positive vector
x
and a row
i
such that the update sets
x
i
to zero. Such a case can happen only when
q
i
0 and the
i
-th row of
P
is non-negative. In this situation however, the problem
reduces to a smaller problem since the global solution has its
i
-th coefficient equal to
zero. As a result, if the problem is degenerate, it suffices to solve the corresponding
non-degenerate reduced problem, and then insert back the zero coefficients in the
solution as discussed in [
12
]. We now apply this framework to our specific problem.
Let us first discuss the case when a degeneracy occurs. Since
P
≥
W
W
+
λ
2
I
is
non-negative, all rows of
P
are non-negative and the problem is degenerate as soon
=
