Digital Signal Processing Reference
In-Depth Information
14.4 Non-Negative Decomposition and Sparsity Regularization
with Convex Quadratic Programming
In this section, we first review the notion of sparsity and its use in combination
with NMF. We then formulate a non-negative decomposition with explicit and flex-
ible sparsity regularization within the framework of convex quadratic programming
and provide a provably convergent multiplicative update to perform the real-time
decomposition.
14.4.1 Definition and Measures of Sparsity
The simplest definition of
sparsity
,or
sparseness
, is that a vector is
sparse
when
most of its elements are null. The sparsity measure that corresponds to this definition
is based on the
0
-norm and just counts the number of non-null coefficients of this
vector. However, it is only applicable in noiseless situations and alternative definitions
and measures have been proposed in the literature to cope with realistic scenarios [
43
].
The idea is that a vector is sparse when it is not dense, i.e., much of its energy is
packed into a few components.
In practice, the
1 are often used directly to measure
sparsity. In the context of NMF, another sparsity measure has also been introduced
in [
44
]:
p
-norms for 0
<
p
≤
√
n
−
x
1
/
x
2
sp
(
x
)
=
√
n
,
(14.8)
−
1
where
n
is the length of the vector
x
. This measure increases as
x
becomes sparser
and is scale-independent. It is comprised between 0 for any vector with all compo-
nents equal up to the signs, and 1 for any vector with a single non-null component,
interpolating smoothly between the two bounds.
14.4.2 Non-Negative Matrix Factorization and Sparsity
In the standard NMF formulation, the sparsity of solutions is implicit. Explicit control
of sparsity becomes however crucial in certain situations, and several NMF extensions
have been proposed to this end. For example, a sparsity penalty is employed in [
45
]
and the problem is solved using ad hoc multiplicative updates. In [
46
], a penalty
term also regularizes sparsity, and the problem is solved with a modified alternating
least squares algorithm. From a theoretical viewpoint however, these schemes do
not guarantee convergence nor monotonic decrease of the cost in general, what is
undesirable to design a robust real-time system.
