# Fast Nonnegative Matrix Factorization Algorithms Using Projected

Authors: Rafal Zdunek; Andrzej Cichocki
Journal: Computational Intelligence and Neuroscience
 (2008)

---

## Abstract

Recently, a considerable growth of interest in projected gradient (PG) methods has been
observed due to their high efficiency in solving large-scale convex minimization problems
subject to linear constraints. Since the minimization problems underlying nonnegative
matrix factorization (NMF) of large matrices well matches this class of minimization
problems, we investigate and test some recent PG methods in the context of their applicability
to NMF. In particular, the paper focuses on the following modified methods:
projected Landweber, Barzilai-Borwein gradient projection, projected sequential subspace
optimization (PSESOP), interior-point Newton (IPN), and sequential coordinate-wise.
The proposed and implemented NMF PG algorithms are compared with respect to their
performance in terms of signal-to-interference ratio (SIR) and elapsed time, using a simple
benchmark of mixed partially dependent nonnegative signals.


---

## Body

## 1. Introduction and Problem Statement

Nonnegative
matrix  factorization  (NMF) finds such nonnegative factors (matrices)A=[aij]∈ℝI×J and X=[xjt]∈ℝJ×T with a aij≥0,xjt≥0 that Y≅AX,
given the observation matrix Y=[yit]∈ℝI×T,
the lower-rank J,
and possibly other statistical information on the observed data or
the factors to be estimated.This method has found a variety of real-world
applications in the areas such as blind separation of images and nonnegative
signals [1–6], spectra recovering [7–10], pattern recognition and feature extraction [11–16], dimensionality reduction,
segmentation and clustering [17–32], language modeling, text
mining [25, 33], music transcription
[34], and neurobiology (gene separation) [35, 36].Depending on an application, the estimated factors may
have different interpretation. For example, Lee and Seung [11] introduced NMF as a method
for decomposing an image (face) into parts-based representations (parts
reminiscent of features such as lips, eyes, nose, etc.). In blind source
separation (BSS) [1, 37, 38], the matrix Y represents the observed mixed (superposed)
signals or images, A is a mixing operator, and X is a matrix of true source signals or images.
Each row of Y or X is a signal or 1D image representation, where I is a number of observed mixed signals and J is a number of hidden (source) components. The
index t usually denotes a sample (discrete time
instant), where T is the number of available samples. In BSS, we
usually have T≫I≥J,
and J is known or can be relatively easily estimated
using SVD or PCA.Our objective is to estimate the mixing matrixA and sources X subject to nonnegativity constraints of all
the entries, given Y and possibly the knowledge on a statistical
distribution of noisy disturbances.Obviously, NMF is not unique in general case, and it
is characterized by a scale and permutation indeterminacies. These problems
have been addressed recently by many researchers [39–42], and in this paper, the problems will not be
discussed. However, we have shown by extensive computer simulations that in
practice with overwhelming probability we are able to achieve a unique
nonnegative factorization (neglecting unavoidable scaling and permutation
ambiguities) if data are sufficiently sparse and a suitable NMF algorithm is
applied [43]. This is
consistent with very recent theoretical results [40].The noise distribution is strongly
application-dependent, however, in many BSS applications, a Gaussian noise is
expected. Here our considerations are restricted to this case, however, the
alternative NMF algorithms optimized to different distributions of the noise
exist and can be found, for example, in [37, 44, 45].NMF was proposed by Paatero and Tapper [46, 47] but Lee and Seung [11, 48] highly popularized this
method by using simple multiplicative algorithms to perform NMF. An extensive
study on convergence of multiplicative algorithms for NMF can be found in
[49]. In general, the
multiplicative algorithms are known to be very slowly convergent for
large-scale problems. Due to this reason, there is a need to search more
efficient and fast algorithms for NMF. Many approaches have been proposed in
the literature to relax these problems. One of them is to apply projected
gradient (PG) algorithms [50–53] or projected alternating least-squares (ALS)
algorithms [33, 54, 55] instead of multiplicative ones. Lin [52] suggested applying the
Armijo rule to estimate the learning parameters in projected gradient updates
for NMF. The NMF PG algorithms proposed by us in [53] also address the issue with
selecting such a learning parameter that is the steepest descent and also keeps
some distance to a boundary of the nonnegative orthant (subspace of real
nonnegative numbers). Another very robust technique concerns exploiting the
information from the second-order Taylor expansion term of a cost function to
speed up the convergence. This approach was proposed in [45, 56], where the mixing matrix A is updated with the projected Newton method,
and the sources in X are computed with the projected least-squares
method (the fixed point algorithm).In this paper, we extend our approach to NMF that we
have initialized in [53]. We have investigated, extended, and tested several
recently proposed PG algorithms such as the oblique projected Landweber
[57], Barzilai-Borwein
gradient projection [58], projected sequential subspace optimization [59, 60], interior-point Newton
[61], and sequential
coordinate-wise [62].
All the presented algorithms in this paper are quite efficient for solving
large-scale minimization problems subject to nonnegativity and sparsity
constraints.The main objective of this paper is to develop,
extend, and/or modify some of the most promising PG algorithms to a standard
NMF problem and to find optimal conditions or parameters for such a class of
NMF algorithms. The second objective is to compare the performance and
complexity of these algorithms for NMF problems, and to discover or establish
the most efficient and promising algorithms. We would like to emphasize that
most of the discussed algorithms have not been implemented neither used till
now or even tested before for NMF problems, but they have been rather
considered for solving a standard system of algebraic equations:Ax(k)=y(k) (for only k=1) where the matrix A and the vectors y are known. In this paper, we consider a much
more difficult and complicated problem in which we have two sets of parameters
and additional constraints of nonnegativity and/or sparsity. So it was not
clear till now whether such algorithms would work efficiently for NMF problems,
and if so, what kind of projected algorithms is the
most efficient? To our best knowledge only the Lin-PG NMF algorithm is
widely used and known for NMF problems. We have demonstrated experimentally that there
are several novel PG gradient algorithms which are much
more efficient and consistent than the Lin-PG algorithm.In Section2, we briefly discuss the PG approach to
NMF. Section 3 describes the tested algorithms. The experimental results are
illustrated in Section 4. Finally, some conclusions are given in Section 5.


## 2. Projected Gradient Algorithms

In contrast to the multiplicative algorithms, the
class of PG algorithms has additive updates. The algorithms discussed here
approximately solve nonnegative least squares (NNLS) problems with the basic
alternating minimization technique that is used in NMF:(1)minxt≥0DF(yt||Axt)=12∥yt−Axt∥22,t=1,…,T,(2)mina̲i≥0DF(y̲i||XTa̲i)=12∥y̲i−XTa̲i∥22,i=1,…,Ior in the equivalent matrix form(3)minxjt≥0DF(Y||AX)=12∥Y−AX∥F2,(4)minaij≥0DF(YT||XTAT)=12∥YT−XTAT∥F2,where A=[a1,…,aJ]∈ℝI×J, AT=[a̲1,…,a̲I]∈ℝJ×I, X=[x1,…,xT]∈ℝJ×T, XT=[x̲1,…,x̲J]∈ℝT×J, Y=[y1,…,yT]∈ℝI×T, YT=[y̲1,…,y̲I]∈ℝI×T,
and usually I≥J.
The matrix A is assumed to be a full-rank matrix, so there
exists a unique solution X*∈ℝJ×T for any matrix Y since the NNLS problem is strictly convex
(with respect to one set of variables {X}).The solutionxt* to (1) satisfies the Karush-Kuhn-Tucker (KKT)
conditions:(5)xt*≥0,gX(xt*)≥0,gX(xt*)Txt*=0,or in the matrix notation(6)X*≥0,GX(X*)≥0,tr{GX(X*)TX*}=0,where gX and GX are the corresponding gradient vector and
gradient matrix:(7)gX(xt)=∇xtDF(yt||Axt)=AT(Axt−yt),(8)GX(X)=∇XDF(Y||AX)=AT(AX−Y).Similarly, the KKT conditions for the solutiona̲* to (2), and the solution A* to (4) are as follows:(9)a̲i*≥0,gA(a̲i*)≥0,gA(a̲i*)Ta̲i*=0,or in the matrix notation:(10)A*≥0,GA(A*)≥0,tr{A*GA(A*)T}=0,where gA and GA are the gradient vector and gradient matrix of
the objective function:(11)gA(a̲t)=∇a̲iDF(y̲i||XTa̲i)=(XTa̲i−y̲i),GA(A)=∇ADF(YT||XTAT)=(AX−Y)XT.There are many approaches to solve the problems (1)
and (2), or equivalently (3) and (4). In this paper, we discuss selected
projected gradient methods that can be generally expressed by iterative
updates:(12)X(k+1)=PΩ[X(k)−ηX(k)PX(k)],A(k+1)=PΩ[A(k)−ηA(k)PA(k)], where PΩ[ξ] is a projection of ξ onto a convex feasible set Ω={ξ∈ℝ:ξ≥0},
namely, the nonnegative orthant ℝ+ (the subspace of nonnegative real numbers), PX(k) and PA(k) are descent directions for X and A,
and ηX(k) and ηA(k) are learning rules, respectively.The projectionPΩ[ξ] can be performed in several ways. One of the
simplest techniques is to replace all negative entries in ξ by zero-values, or in practical cases, by a
small positive number ϵ to avoid numerical instabilities. Thus,(13)P[ξ]=max{ϵ,ξ}.However, this is not the only
way to carry out the projection PΩ(ξ).
It is typically more efficient to choose the learning rates ηX(k) and ηA(k) so as to preserve nonnegativity of the
solutions. The nonnegativity can be also maintained by solving least-squares
problems subject to the constraints (6) and (10). Here we present the exemplary
PG methods that work for NMF problems quite efficiently, and we implemented
them in the Matlab toolboxm, NMFLAB/NTFLAB, for signal and image processing
[43]. For simplicity,
we focus our considerations on updating the matrix X,
assuming that the updates for A can be obtained in a similar way. Note that
the updates for A can be readily obtained solving the transposed
system XTAT=YT,
having X fixed (updated in the previous step).


## 3. Algorithms

### 3.1. Oblique Projected Landweber Method

The Landweber method [63] performs gradient-descent
minimization with the following iterative scheme:(14)X(k+1)=X(k)−ηGX(k),where the gradient is given by
(8), and the learning rate η∈(0,ηmax).
The updating formula assures an asymptotical convergence to the minimal-norm
least squares solution for the convergence radius  defined by(15)ηmax=2λmax(ATA),where λmax(ATA) is the maximal eigenvalue of ATA.
Since A is a nonnegative matrix, we have λmax(ATA)≤maxj[ATA1J]j,
where 1J=[1,…,1]T∈ℝJ. Thus the modified Landweber iterations can be expressed by the
formula(16)X(k+1)=PΩ[X(k)−diag{ηj}GX(k)],whereηj=2(ATA1J)j.In the  obliqueprojected
Landweber (OPL) method [57], which can be regarded as a particular case of the PG
iterative formula (12), the solution obtained with (14) in each iterative
step is projected onto the feasible set. Finally, we have Algorithm 1 for
updating X.Algorithm 1:(OPL).
SetA, X, % Initializationηj(X)=2(ATA1J)j,Fork=1,2,…, % Inner iterations for XGX=AT(AX−Y), %
Gradient with respect to XX←PΩ[X−diag{ηj}GX], %
UpdatingEnd


### 3.2. Projected Gradient

One of the fundamental PG algorithms for NMF was
proposed by Lin in [52]. This algorithm, which we refer to as the Lin-PG,
uses the Armijo rule along the projection arc to determine the steplengths ηX(k) and ηA(k) in the iterative updates (12). For the
cost function being the squared Euclidean distance, PX=(A(k))T(A(k)X(k)−Y) and PA=(A(k)X(k+1)−Y)(X(k+1))T.For computation ofX,
such a value of ηX is decided, on which(17)ηX(k)=βmk,where mk is the first nonnegative integer m that satisfies(18)DF(Y||AX(k+1))−DF(Y||AX(k))≤σ∇XDF(Y||AX(k))T(X(k+1)−X(k)). The parameters β∈(0,1) and σ∈(0,1) decide about a convergence speed. In this
algorithm we set σ=0.01, β=0.1 experimentally as default.The Matlab implementation of the Lin-PG algorithm is
given in [52].


### 3.3. Barzilai-Borwein Gradient Projection

The Barzilai-Borwein gradient projection method
[58, 64] is motivated by the
quasi-Newton approach, that is, the inverse of the Hessian is replaced with an
identity matrix Hk=αkI,
where the scalar αk is selected so that the inverse Hessian has
similar behavior as the true Hessian in the recent iteration. Thus,(19)X(k+1)−X(k)≈αk(∇XD(Y∥A(k)X(k+1))−∇XD(Y∥A(k)X(k))).In comparison to, for example,
Lin's method [52],
this method does not ensure that the objective function decreases at every
iteration, but its general convergence has been proven analytically [58]. The general scheme of the
Barzilai-Borwein gradient projection algorithm for updating X is in
Algorithm 2.Algorithm 2:(GPSR-BB).
SetA,X,αmin,αmax,α(0)∈[αmin,αmax]∈ℝT%InitializationFork=1,2,…, % Inner iterationsΔ(k)=PΩ[X(k)−α(k)∇XDF(Y||AX(k))]−X(k),λ(k)=argminλt(k)∈[0,1]DF(Y||A(X+Δ(k)diag{λ})),where λ=[λt]∈ℝT,X(k+1)=X(k)+Δ(k)diag{λ},γ(k)=diag{(Δ(k))TATAΔ(k)},Ifγt(k)=0: αt(k+1)=αmax,Elseαt(k+1)=min{αmax,max{αmin,[(Δ(k))TΔ(k)]tt/γt(k)}},EndEnd%
Inner iterationsSinceDF(Y||AX) is a quadratic function, the line search
parameter λ(k) can be derived in the following closed-form formula:(20)λ(k)=max{0,min{1,diag{(Δ(k))T∇XDF(Y||AX)}diag{(Δ(k))TATAΔ(k)}}}.The Matlab  implementation of the GPSR-BB algorithm,
which solves the systemAX=Y of multiple measurement vectors subject to
nonnegativity constraints, is given in Algorithm 4 (see also NMFLAB).


### 3.4. Projected Sequential Subspace Optimization

The projected
sequential subspace optimization (PSESOP) method [59, 60] carries out a projected
minimization of a smooth objective function over a subspace spanned by several
directions which include the current gradient and gradient from the previous
iterations, and the Nemirovski directions. Nemirovski [65] suggested that convex
smooth unconstrained optimization is optimal if the optimization is performed
over a subspace which includes the current gradient g(x),
the directions d1(k)=x(k)−x(0),
and the linear combination of the previous gradients d2(k)=∑n=0k−1wng(xn) with the coefficients wn,n=0,…,k−1.
The directions should be orthogonal to the current gradient. Narkiss and
Zibulevsky [59] also
suggested to include another direction: p(k)=x(k)−x(k−1),
which is motivated by a natural extension of the conjugate gradient (CG) method
to a nonquadratic case. However, our practical observations showed that this
direction does not have a strong impact on the NMF components, thus we
neglected it in our NMF-PSESOP algorithm. Finally, we have Algorithm 3 for
updating xt which is a single column vector of X.Algorithm 3:(NMF-PSESOP).
SetA, xt(0), p%
InitializationFork=1,2,…, % Inner iterationsd1(k)=x(k)−x(0),g(k)=∇xtDF(yt||Axt),G(p)=[g(k−1),g(k−2),…,g(k−p)]∈ℝJ×p,wk={1ifk=1,1/2+1/4+wk−12ifk>1,w(k)=[wk,wk−1,…,wk−p+1]T∈ℝp,d2(k)=G(p)w(k),D(k)=[d1(k),d2(k),g(k),G(p)],α*(k)=argminαDF(yt||A(xt(k)+D(k)α(k))),x(k+1)=PΩ[x(k)+D(k)α*(k)]End%
Inner iterationsAlgorithm 4
% Barzilai-Borwein gradient projection (GPSR-BB) algorithm%function [X] = nmf_gpsr_bb(A,Y,X,no_iter)%% [X] = nmf_gpsr_bb(A,Y,X,no_iter) finds such matrix X that solves% the equation AX = Y subject to nonnegativity constraints.%% INPUTS:% A - system matrix of dimension [I by J]% Y - matrix of observations [I by T]% X - matrix of initial guess [J by T]% no_iter - maximum number of iterations%% OUTPUTS:% X - matrix of estimated sources [J by T]%% #########################################################################% Parametersalpha_min = 1E-8; alpha_max = 1;alpha = .1*ones(1,size(Y,2));B = A’*A; Yt = A’*Y;for k=1:no_iterG = B*X - Yt;delta = max(eps, X - repmat(alpha,size(G,1),1).*G) - X;deltaB = B*delta;lambda = max(0, min(1, -sum(delta.*G,1)./(sum(delta.*deltaB,1) + eps)));X = max(eps,X + delta.*repmat(lambda,size(delta,1),1));gamma = sum(delta.*deltaB,1) + eps;if gammaalpha = min(alpha_max, max(alpha_min, sum(delta.^2,1)./gamma ));elsealpha = alpha_max;endendThe parameterp denotes the number of previous iterates that
are taken into account to determine the current update.The line search vectorα*(k) derived in a closed form for the objective function DF(yt||Axt) is as follows:(21)α*(k)=−((D(k))TATAD(k)+λI)−1(D(k))T∇xtDF(yt||Axt).The regularization parameter can
be set as a very small constant to avoid instabilities in inverting a
rank-deficient matrix in case that D(k) has zero-value or dependent columns.


### 3.5. Interior Point Newton Algorithm

The interior point Newton (IPN) algorithm [61] solves the NNLS problem (1)
by searching the solution satisfying the KKT conditions (5) which equivalently
can be expressed by the nonlinear equations(22)D(xt)g(xt)=0,where D(xt)=diag{d1(xt),…,dJ(xt)}, xt≥0,
and(23)dj(xt)={xjtifgj(xt)≥0,1otherwise.Applying the Newton method to
(22), we have in the kth iterative step(24)(Dk(xt)ATA+Ek(xt))pk=−Dk(xt)gk(xt),where(25)Ek(xt)=diag{e1(xt),…,eJ(xt)}.In [61], the  entries of the matrix Ek(xt) are defined by(26)ej(xt)={gj(xt)if0≤gj(xt)<xjtγ,or(gj(xt))γ>xjt,1otherwise,for 1<γ≤2.If the solution is degenerate, that is,t=1,…,T,∃j:xjt*=0, and gjt=0,
the matrix Dk(xt)ATA+Ek(xt) may be singular. To avoid such a case, the
system of equations has been rescaled to the following form:(27)Wk(xt)Dk(xt)Mk(xt)pk=−Wk(xt)Dk(xt)gk(xt)with(28)Mk(xt)=ATA+Dk(xt)−1Ek(xt),Wk(xt)=diag{w1(xt),…,wJ(xt)},wj(xt)=(dj(xt)+ej(xt))−1, for xt>0.
In [61], the system
(27) is solved by the inexact Newton method, which leads to the following
updates:(29)Wk(xt)Dk(xt)Mk(xt)pk=−Wk(xt)Dk(xt)gk(xt)+rk(xt),(30)p^k=max{σ,1−∥PΩ[xt(k)+pk]−xt(k)∥2}(PΩ[xt(k)+pk]−xt(k)),(31)xt(k+1)=xt(k)+p^k,where σ∈(0,1), rk(xt)=AT(Axt−yt),
and PΩ[⋅] is a projection onto a  feasible set Ω.The transformation of the normal matrixATA by the matrix Wk(xt)Dk(xt) in (27) means the system matrix Wk(xt)Dk(xt)Mk(xt) is no longer symmetric and positive-definite.
There are many methods for handling such systems of linear equations, like QMR
[66], BiCG [67, 68], BiCGSTAB [69], or GMRES-like methods
[70], however, they
are more complicated and computationally demanding than, for example, the basic
CG algorithm [71]. To
apply the CG algorithm the system matrix in (27) must be converted to a
positive-definite symmetric matrix, which can be easily done with normal
equations. The methods like CGLS [72] or LSQR [73] are therefore suitable for such tasks. The
transformed system has the form(32)Zk(xt)p˜k=−Sk(xt)gk(xt)+r˜k(xt),(33)Sk(xt)=Wk(xt)Dk(xt),(34)Zk(xt)=Sk(xt)Mk(xt)Sk(xt)=Sk(xt)ATASk(xt)+Wk(xt)Ek(xt),with p˜k=Sk−1(xt)pk and r˜k=Sk−1(xt)rk(xt).Since our cost function is quadratic, its minimization
in a single step is performed with combining the projected Newton step with the
constrained scaled Cauchy step that is given in the form(35)pk(C)=−τkDk(xt)gk(xt),τk>0.Assuming xt(k)+pk(C)>0, τk is chosen as being either the unconstrained
minimizer of the quadratic function ψk(−τkDk(xt)gk(xt)) or a scalar proportional to the distance to
the boundary along −Dk(xt)gk(xt),
where(36)ψk(p)=12pTMk(xt)p+pTgk(xt)=12pT(ATA+Dk−1(xt)Ek(xt))p+pTAT(Axt(k)−yt).Thus(37)τk={τ1=argminτψk(−τkDk(xt)gk(xt))ifxt(k)−τ1Dk(xt)gk(xt)>0,τ2=θminj{xjt(k)(Dk(xt)gk(xt))j:(Dk(xt)gk(xt))j>0}otherwise,where ψk(−τkDk(xt)gk(xt))=(gk(xt))TDk(xt)gk(xt)/(Dk(xt)gk(xt))TMk(xt)Dk(xt)gk(xt) with θ∈(0,1).
For ψk(pk(C))<0,
the global convergence is achieved if red(xt(k+1)−xt(k))≥β, β∈(0,1) with(38)red(p)=ψk(p)ψk(pk(C)).The usage of the constrained scaled Cauchy step leads
to the following updates:(39)st(k)=t(pk(C)−p^k)+p^k,xt(k+1)=xt(k)+st(k), with t∈[0,1), p^k and pk(C) are given by (30) and (35), respectively, and t is the smaller square root (laying in (0,1)) of the quadratic equation:(40)π(t)=ψk(t(pk(C)−p^k)+p^k)−βψk(pk(C))=0.The Matlab code of the IPN algorithm, which solves the
systemAxt=yt subject to nonnegativity constraints, is given
in Algorithm 5. To solve the transformed system (32), we use the LSQR method
implemented in Matlab 7.0.Algorithm 5
% Interior Point Newton (IPN) algorithm function%function [x] = nmf_ipn(A,y,x,no_iter)%% [x]=nmf_ipn(A,y,x,no_iter) finds such x that solves the equation Ax = y% subject to nonnegativity constraints.%% INPUTS:% A - system matrix of dimension [I by J]% y - vector of observations [I by 1]% x - vector of initial guess [J by 1]% no_iter - maximum number of iterations%% OUTPUTS:% x - vector of estimated sources [J by 1]%% #########################################################################% Parameterss = 1.8; theta = 0.5; rho = .1; beta = 1;H = A’*A; yt = A’*y; J = size(x,1);% Main loopfor k=1:no_iterg = H*x - yt; d = ones(J,1); d(g >= 0) = x(g >= 0);ek = zeros(J,1); ek(g >=0 & g < x.^s) = g(g >=0 & g < x.^s);M = H + diag(ek./d);dg = d.*g;tau1 = (g’*dg)/(dg’*M*dg); tau_2vec = x./dg;tau2 = theta*min(tau_2vec(dg > 0));tau = tau1*ones(J,1); tau(x - tau1*dg <= 0) = tau2;w = 1./(d + ek); sk = sqrt(w.*d); pc = - tau.*dg;Z = repmat(sk,1,J).*M.*repmat(sk’,J,1);rt = -g./sk;[pt,flag,relres,iter,resvec] = lsqr(Z,rt - g.*sk,1E-8);p = pt.*sk;phx = max(0, x + p) - x;ph = max(rho, 1 - norm(phx))*phx;Phi_pc = .5*pc’*M*pc + pc’*g; Phi_ph = .5*ph’*M*ph + ph’*g;red_p = Phi_ph/Phi_pc; dp = pc - ph;if red_p >= betat = 0;elseax = .5*dp’*M*dp; bx = dp’*(M*ph + g);cx = Phi_ph - beta*Phi_pc;Deltas = sqrt(bx^2 - 4*ax*cx);t1 = .5*(-bx + Deltas)/ax; t2 = .5*(-bx - Deltas)/ax;t1s = t1 > 0 & t1 < 1; t2s = t2 > 0 & t2 < 1; t = min(t1, t2);if (t <= 0)if t1st = t1s;elset = t2s;endendendsk = t*dp + ph;x = x + sk;end % for k


### 3.6. Sequential Coordinate-Wise Algorithm

The NNLS problem (1) can be expressed in terms of the
following quadratic problem (QP) [62]:(41)minxt≥0Ψ(xt),(t=1,…,T),where(42)Ψ(xt)=12xtTHxt+ctTxt,with H=ATA and ct=−ATyt.The sequential coordinate-wise algorithm (SCWA)
proposed first by Franc et al. [62] solves the QP problem given by (41) updating only
single variable xjt in one iterative step. It should be noted that
the sequential updates can be easily done, if the function Ψ(xt) is equivalently rewritten as(43)Ψ(xt)=12∑p∈ℐ∑r∈ℐxptxrt(ATA)pr+∑p∈ℐxpt(ATyt)pt=12xjt2(ATA)jj+xjt(ATyt)jt+xjt∑p∈ℐ∖{j}xpt(ATA)pj+∑p∈ℐ∖{j}xpt(ATyt)pt+12∑p∈ℐ∖{j}∑r∈ℐ∖{j}xptxrt(ATA)pr=12xjt2hjj+xjtβjt+γjt,where ℐ={1,…,J},
and(44)hjj=(ATA)jj,βjt=(ATyt)jt+∑p∈ℐ∖{j}xpt(ATA)pj=[ATAxt+ATyt]jt−(ATA)jjxjt,γjt=∑p∈ℐ∖{j}xpt(ATyt)pt+12∑p∈ℐ∖{j}∑r∈ℐ∖{j}xptxrt(ATA)pr.Considering the optimization of Ψ(xt) with respect to the selected variable xjt,
the following analytical solution can be derived:(45)xjt*=argminΨ([x1t,…,xjt,…,xJt]T)=argmin12xjt2hjj+xjtβjt+γjt=max(0,−βjthjj)=max(0,xjt−[ATAxt]jt+[ATyt]jt(ATA)jj).Updating only single variablexjt in one iterative step, we have(46)xpt(k+1)=xpt(k),∀p∈ℐ∖{j},xjt(k+1)≠xjt(k).Any optimal solution to the QP
(41) satisfies the KKT conditions given by (5) and the stationarity condition
of the following Lagrange function:(47)ℒ(xt,λt)=12xtTHxt+ctTxt−λtTxt,where λt∈ℝJ is a vector of Lagrange multipliers (or dual variables) corresponding
to the vector xt.
Thus, ∇xtℒ(xt,λt)=Hxt+ct−λt=0.
In the SCWA, the Lagrange multipliers are updated in each iteration according
to the formula(48)λt(k+1)=λt(k)+(xjt(k+1)−xjt(k))hj,where hj is the jth column of H,
and λt(0)=ct.Finally, the SCWA can take the following updates:(49)xjt(k+1)=max(0,xjt(k)−λj(k)(ATA)jj),xpt(k+1)=xpt(k),∀p∈ℐ∖{j}λt(k+1)=λt(k)+(xjt(k+1)−xjt(k))hj.


## 3.1. Oblique Projected Landweber Method

The Landweber method [63] performs gradient-descent
minimization with the following iterative scheme:(14)X(k+1)=X(k)−ηGX(k),where the gradient is given by
(8), and the learning rate η∈(0,ηmax).
The updating formula assures an asymptotical convergence to the minimal-norm
least squares solution for the convergence radius  defined by(15)ηmax=2λmax(ATA),where λmax(ATA) is the maximal eigenvalue of ATA.
Since A is a nonnegative matrix, we have λmax(ATA)≤maxj[ATA1J]j,
where 1J=[1,…,1]T∈ℝJ. Thus the modified Landweber iterations can be expressed by the
formula(16)X(k+1)=PΩ[X(k)−diag{ηj}GX(k)],whereηj=2(ATA1J)j.In the  obliqueprojected
Landweber (OPL) method [57], which can be regarded as a particular case of the PG
iterative formula (12), the solution obtained with (14) in each iterative
step is projected onto the feasible set. Finally, we have Algorithm 1 for
updating X.Algorithm 1:(OPL).
SetA, X, % Initializationηj(X)=2(ATA1J)j,Fork=1,2,…, % Inner iterations for XGX=AT(AX−Y), %
Gradient with respect to XX←PΩ[X−diag{ηj}GX], %
UpdatingEnd


## 3.2. Projected Gradient

One of the fundamental PG algorithms for NMF was
proposed by Lin in [52]. This algorithm, which we refer to as the Lin-PG,
uses the Armijo rule along the projection arc to determine the steplengths ηX(k) and ηA(k) in the iterative updates (12). For the
cost function being the squared Euclidean distance, PX=(A(k))T(A(k)X(k)−Y) and PA=(A(k)X(k+1)−Y)(X(k+1))T.For computation ofX,
such a value of ηX is decided, on which(17)ηX(k)=βmk,where mk is the first nonnegative integer m that satisfies(18)DF(Y||AX(k+1))−DF(Y||AX(k))≤σ∇XDF(Y||AX(k))T(X(k+1)−X(k)). The parameters β∈(0,1) and σ∈(0,1) decide about a convergence speed. In this
algorithm we set σ=0.01, β=0.1 experimentally as default.The Matlab implementation of the Lin-PG algorithm is
given in [52].


## 3.3. Barzilai-Borwein Gradient Projection

The Barzilai-Borwein gradient projection method
[58, 64] is motivated by the
quasi-Newton approach, that is, the inverse of the Hessian is replaced with an
identity matrix Hk=αkI,
where the scalar αk is selected so that the inverse Hessian has
similar behavior as the true Hessian in the recent iteration. Thus,(19)X(k+1)−X(k)≈αk(∇XD(Y∥A(k)X(k+1))−∇XD(Y∥A(k)X(k))).In comparison to, for example,
Lin's method [52],
this method does not ensure that the objective function decreases at every
iteration, but its general convergence has been proven analytically [58]. The general scheme of the
Barzilai-Borwein gradient projection algorithm for updating X is in
Algorithm 2.Algorithm 2:(GPSR-BB).
SetA,X,αmin,αmax,α(0)∈[αmin,αmax]∈ℝT%InitializationFork=1,2,…, % Inner iterationsΔ(k)=PΩ[X(k)−α(k)∇XDF(Y||AX(k))]−X(k),λ(k)=argminλt(k)∈[0,1]DF(Y||A(X+Δ(k)diag{λ})),where λ=[λt]∈ℝT,X(k+1)=X(k)+Δ(k)diag{λ},γ(k)=diag{(Δ(k))TATAΔ(k)},Ifγt(k)=0: αt(k+1)=αmax,Elseαt(k+1)=min{αmax,max{αmin,[(Δ(k))TΔ(k)]tt/γt(k)}},EndEnd%
Inner iterationsSinceDF(Y||AX) is a quadratic function, the line search
parameter λ(k) can be derived in the following closed-form formula:(20)λ(k)=max{0,min{1,diag{(Δ(k))T∇XDF(Y||AX)}diag{(Δ(k))TATAΔ(k)}}}.The Matlab  implementation of the GPSR-BB algorithm,
which solves the systemAX=Y of multiple measurement vectors subject to
nonnegativity constraints, is given in Algorithm 4 (see also NMFLAB).


## 3.4. Projected Sequential Subspace Optimization

The projected
sequential subspace optimization (PSESOP) method [59, 60] carries out a projected
minimization of a smooth objective function over a subspace spanned by several
directions which include the current gradient and gradient from the previous
iterations, and the Nemirovski directions. Nemirovski [65] suggested that convex
smooth unconstrained optimization is optimal if the optimization is performed
over a subspace which includes the current gradient g(x),
the directions d1(k)=x(k)−x(0),
and the linear combination of the previous gradients d2(k)=∑n=0k−1wng(xn) with the coefficients wn,n=0,…,k−1.
The directions should be orthogonal to the current gradient. Narkiss and
Zibulevsky [59] also
suggested to include another direction: p(k)=x(k)−x(k−1),
which is motivated by a natural extension of the conjugate gradient (CG) method
to a nonquadratic case. However, our practical observations showed that this
direction does not have a strong impact on the NMF components, thus we
neglected it in our NMF-PSESOP algorithm. Finally, we have Algorithm 3 for
updating xt which is a single column vector of X.Algorithm 3:(NMF-PSESOP).
SetA, xt(0), p%
InitializationFork=1,2,…, % Inner iterationsd1(k)=x(k)−x(0),g(k)=∇xtDF(yt||Axt),G(p)=[g(k−1),g(k−2),…,g(k−p)]∈ℝJ×p,wk={1ifk=1,1/2+1/4+wk−12ifk>1,w(k)=[wk,wk−1,…,wk−p+1]T∈ℝp,d2(k)=G(p)w(k),D(k)=[d1(k),d2(k),g(k),G(p)],α*(k)=argminαDF(yt||A(xt(k)+D(k)α(k))),x(k+1)=PΩ[x(k)+D(k)α*(k)]End%
Inner iterationsAlgorithm 4
% Barzilai-Borwein gradient projection (GPSR-BB) algorithm%function [X] = nmf_gpsr_bb(A,Y,X,no_iter)%% [X] = nmf_gpsr_bb(A,Y,X,no_iter) finds such matrix X that solves% the equation AX = Y subject to nonnegativity constraints.%% INPUTS:% A - system matrix of dimension [I by J]% Y - matrix of observations [I by T]% X - matrix of initial guess [J by T]% no_iter - maximum number of iterations%% OUTPUTS:% X - matrix of estimated sources [J by T]%% #########################################################################% Parametersalpha_min = 1E-8; alpha_max = 1;alpha = .1*ones(1,size(Y,2));B = A’*A; Yt = A’*Y;for k=1:no_iterG = B*X - Yt;delta = max(eps, X - repmat(alpha,size(G,1),1).*G) - X;deltaB = B*delta;lambda = max(0, min(1, -sum(delta.*G,1)./(sum(delta.*deltaB,1) + eps)));X = max(eps,X + delta.*repmat(lambda,size(delta,1),1));gamma = sum(delta.*deltaB,1) + eps;if gammaalpha = min(alpha_max, max(alpha_min, sum(delta.^2,1)./gamma ));elsealpha = alpha_max;endendThe parameterp denotes the number of previous iterates that
are taken into account to determine the current update.The line search vectorα*(k) derived in a closed form for the objective function DF(yt||Axt) is as follows:(21)α*(k)=−((D(k))TATAD(k)+λI)−1(D(k))T∇xtDF(yt||Axt).The regularization parameter can
be set as a very small constant to avoid instabilities in inverting a
rank-deficient matrix in case that D(k) has zero-value or dependent columns.


## 3.5. Interior Point Newton Algorithm

The interior point Newton (IPN) algorithm [61] solves the NNLS problem (1)
by searching the solution satisfying the KKT conditions (5) which equivalently
can be expressed by the nonlinear equations(22)D(xt)g(xt)=0,where D(xt)=diag{d1(xt),…,dJ(xt)}, xt≥0,
and(23)dj(xt)={xjtifgj(xt)≥0,1otherwise.Applying the Newton method to
(22), we have in the kth iterative step(24)(Dk(xt)ATA+Ek(xt))pk=−Dk(xt)gk(xt),where(25)Ek(xt)=diag{e1(xt),…,eJ(xt)}.In [61], the  entries of the matrix Ek(xt) are defined by(26)ej(xt)={gj(xt)if0≤gj(xt)<xjtγ,or(gj(xt))γ>xjt,1otherwise,for 1<γ≤2.If the solution is degenerate, that is,t=1,…,T,∃j:xjt*=0, and gjt=0,
the matrix Dk(xt)ATA+Ek(xt) may be singular. To avoid such a case, the
system of equations has been rescaled to the following form:(27)Wk(xt)Dk(xt)Mk(xt)pk=−Wk(xt)Dk(xt)gk(xt)with(28)Mk(xt)=ATA+Dk(xt)−1Ek(xt),Wk(xt)=diag{w1(xt),…,wJ(xt)},wj(xt)=(dj(xt)+ej(xt))−1, for xt>0.
In [61], the system
(27) is solved by the inexact Newton method, which leads to the following
updates:(29)Wk(xt)Dk(xt)Mk(xt)pk=−Wk(xt)Dk(xt)gk(xt)+rk(xt),(30)p^k=max{σ,1−∥PΩ[xt(k)+pk]−xt(k)∥2}(PΩ[xt(k)+pk]−xt(k)),(31)xt(k+1)=xt(k)+p^k,where σ∈(0,1), rk(xt)=AT(Axt−yt),
and PΩ[⋅] is a projection onto a  feasible set Ω.The transformation of the normal matrixATA by the matrix Wk(xt)Dk(xt) in (27) means the system matrix Wk(xt)Dk(xt)Mk(xt) is no longer symmetric and positive-definite.
There are many methods for handling such systems of linear equations, like QMR
[66], BiCG [67, 68], BiCGSTAB [69], or GMRES-like methods
[70], however, they
are more complicated and computationally demanding than, for example, the basic
CG algorithm [71]. To
apply the CG algorithm the system matrix in (27) must be converted to a
positive-definite symmetric matrix, which can be easily done with normal
equations. The methods like CGLS [72] or LSQR [73] are therefore suitable for such tasks. The
transformed system has the form(32)Zk(xt)p˜k=−Sk(xt)gk(xt)+r˜k(xt),(33)Sk(xt)=Wk(xt)Dk(xt),(34)Zk(xt)=Sk(xt)Mk(xt)Sk(xt)=Sk(xt)ATASk(xt)+Wk(xt)Ek(xt),with p˜k=Sk−1(xt)pk and r˜k=Sk−1(xt)rk(xt).Since our cost function is quadratic, its minimization
in a single step is performed with combining the projected Newton step with the
constrained scaled Cauchy step that is given in the form(35)pk(C)=−τkDk(xt)gk(xt),τk>0.Assuming xt(k)+pk(C)>0, τk is chosen as being either the unconstrained
minimizer of the quadratic function ψk(−τkDk(xt)gk(xt)) or a scalar proportional to the distance to
the boundary along −Dk(xt)gk(xt),
where(36)ψk(p)=12pTMk(xt)p+pTgk(xt)=12pT(ATA+Dk−1(xt)Ek(xt))p+pTAT(Axt(k)−yt).Thus(37)τk={τ1=argminτψk(−τkDk(xt)gk(xt))ifxt(k)−τ1Dk(xt)gk(xt)>0,τ2=θminj{xjt(k)(Dk(xt)gk(xt))j:(Dk(xt)gk(xt))j>0}otherwise,where ψk(−τkDk(xt)gk(xt))=(gk(xt))TDk(xt)gk(xt)/(Dk(xt)gk(xt))TMk(xt)Dk(xt)gk(xt) with θ∈(0,1).
For ψk(pk(C))<0,
the global convergence is achieved if red(xt(k+1)−xt(k))≥β, β∈(0,1) with(38)red(p)=ψk(p)ψk(pk(C)).The usage of the constrained scaled Cauchy step leads
to the following updates:(39)st(k)=t(pk(C)−p^k)+p^k,xt(k+1)=xt(k)+st(k), with t∈[0,1), p^k and pk(C) are given by (30) and (35), respectively, and t is the smaller square root (laying in (0,1)) of the quadratic equation:(40)π(t)=ψk(t(pk(C)−p^k)+p^k)−βψk(pk(C))=0.The Matlab code of the IPN algorithm, which solves the
systemAxt=yt subject to nonnegativity constraints, is given
in Algorithm 5. To solve the transformed system (32), we use the LSQR method
implemented in Matlab 7.0.Algorithm 5
% Interior Point Newton (IPN) algorithm function%function [x] = nmf_ipn(A,y,x,no_iter)%% [x]=nmf_ipn(A,y,x,no_iter) finds such x that solves the equation Ax = y% subject to nonnegativity constraints.%% INPUTS:% A - system matrix of dimension [I by J]% y - vector of observations [I by 1]% x - vector of initial guess [J by 1]% no_iter - maximum number of iterations%% OUTPUTS:% x - vector of estimated sources [J by 1]%% #########################################################################% Parameterss = 1.8; theta = 0.5; rho = .1; beta = 1;H = A’*A; yt = A’*y; J = size(x,1);% Main loopfor k=1:no_iterg = H*x - yt; d = ones(J,1); d(g >= 0) = x(g >= 0);ek = zeros(J,1); ek(g >=0 & g < x.^s) = g(g >=0 & g < x.^s);M = H + diag(ek./d);dg = d.*g;tau1 = (g’*dg)/(dg’*M*dg); tau_2vec = x./dg;tau2 = theta*min(tau_2vec(dg > 0));tau = tau1*ones(J,1); tau(x - tau1*dg <= 0) = tau2;w = 1./(d + ek); sk = sqrt(w.*d); pc = - tau.*dg;Z = repmat(sk,1,J).*M.*repmat(sk’,J,1);rt = -g./sk;[pt,flag,relres,iter,resvec] = lsqr(Z,rt - g.*sk,1E-8);p = pt.*sk;phx = max(0, x + p) - x;ph = max(rho, 1 - norm(phx))*phx;Phi_pc = .5*pc’*M*pc + pc’*g; Phi_ph = .5*ph’*M*ph + ph’*g;red_p = Phi_ph/Phi_pc; dp = pc - ph;if red_p >= betat = 0;elseax = .5*dp’*M*dp; bx = dp’*(M*ph + g);cx = Phi_ph - beta*Phi_pc;Deltas = sqrt(bx^2 - 4*ax*cx);t1 = .5*(-bx + Deltas)/ax; t2 = .5*(-bx - Deltas)/ax;t1s = t1 > 0 & t1 < 1; t2s = t2 > 0 & t2 < 1; t = min(t1, t2);if (t <= 0)if t1st = t1s;elset = t2s;endendendsk = t*dp + ph;x = x + sk;end % for k


## 3.6. Sequential Coordinate-Wise Algorithm

The NNLS problem (1) can be expressed in terms of the
following quadratic problem (QP) [62]:(41)minxt≥0Ψ(xt),(t=1,…,T),where(42)Ψ(xt)=12xtTHxt+ctTxt,with H=ATA and ct=−ATyt.The sequential coordinate-wise algorithm (SCWA)
proposed first by Franc et al. [62] solves the QP problem given by (41) updating only
single variable xjt in one iterative step. It should be noted that
the sequential updates can be easily done, if the function Ψ(xt) is equivalently rewritten as(43)Ψ(xt)=12∑p∈ℐ∑r∈ℐxptxrt(ATA)pr+∑p∈ℐxpt(ATyt)pt=12xjt2(ATA)jj+xjt(ATyt)jt+xjt∑p∈ℐ∖{j}xpt(ATA)pj+∑p∈ℐ∖{j}xpt(ATyt)pt+12∑p∈ℐ∖{j}∑r∈ℐ∖{j}xptxrt(ATA)pr=12xjt2hjj+xjtβjt+γjt,where ℐ={1,…,J},
and(44)hjj=(ATA)jj,βjt=(ATyt)jt+∑p∈ℐ∖{j}xpt(ATA)pj=[ATAxt+ATyt]jt−(ATA)jjxjt,γjt=∑p∈ℐ∖{j}xpt(ATyt)pt+12∑p∈ℐ∖{j}∑r∈ℐ∖{j}xptxrt(ATA)pr.Considering the optimization of Ψ(xt) with respect to the selected variable xjt,
the following analytical solution can be derived:(45)xjt*=argminΨ([x1t,…,xjt,…,xJt]T)=argmin12xjt2hjj+xjtβjt+γjt=max(0,−βjthjj)=max(0,xjt−[ATAxt]jt+[ATyt]jt(ATA)jj).Updating only single variablexjt in one iterative step, we have(46)xpt(k+1)=xpt(k),∀p∈ℐ∖{j},xjt(k+1)≠xjt(k).Any optimal solution to the QP
(41) satisfies the KKT conditions given by (5) and the stationarity condition
of the following Lagrange function:(47)ℒ(xt,λt)=12xtTHxt+ctTxt−λtTxt,where λt∈ℝJ is a vector of Lagrange multipliers (or dual variables) corresponding
to the vector xt.
Thus, ∇xtℒ(xt,λt)=Hxt+ct−λt=0.
In the SCWA, the Lagrange multipliers are updated in each iteration according
to the formula(48)λt(k+1)=λt(k)+(xjt(k+1)−xjt(k))hj,where hj is the jth column of H,
and λt(0)=ct.Finally, the SCWA can take the following updates:(49)xjt(k+1)=max(0,xjt(k)−λj(k)(ATA)jj),xpt(k+1)=xpt(k),∀p∈ℐ∖{j}λt(k+1)=λt(k)+(xjt(k+1)−xjt(k))hj.


## 4. Simulations

All the proposed algorithms were implemented in our
NMFLAB, and evaluated with the numerical tests related to typical BSS problems.
We used the synthetic benchmark of 4 partially dependent nonnegative signals
(with onlyT=1000 samples) which are illustrated in Figure 1(a). The signals are mixed by random, uniformly
distributed nonnegative matrix A∈ℝ8×4 with the condition number cond{A}=4.11.
The matrix A is displayed in(50)A=[0.06310.76660.01740.65960.26420.66610.81940.21410.99950.13090.62110.60210.21200.09540.56020.60490.49840.01490.24400.65950.29050.28820.82200.18340.67280.81670.26320.63650.95800.98550.75360.1703].The mixing signals are shown in
Figure 1(b).Dataset: (a)
original 4 source signals, (b) observed 8 mixed signals.
(a)(b)Because the number of variables inX is much greater than in A,
that is, I×J=32 and J×T=4000,
we test the projected gradient algorithms only for updating A.
The variables in X are updated with the standard projected fixed
point alternating least squares (FP-ALS) algorithm that is extensively analyzed
in [55].In general, the FP-ALS algorithm solves the
least-squares problem(51)X*=argminX{12∥Y−AX∥F2}with the Moore-Penrose
pseudoinverse of a system matrix, that is, in our case, the matrix A.
Since in NMF usually I≥J,
we formulate normal equations as ATAX=ATY,
and the least-squares solution of minimal l2-norm to the normal equations is XLS=(ATA)−1ATY=A+Y, where A+ is the Moore-Penrose pseudoinverse of A.
The projected FP-ALS algorithm is obtained with a simple
“half-rectified” projection, that is,(52)X=PΩ[A+Y].The alternating minimization is nonconvex in spite of
the cost function being convex with respect to one set of variables. Thus, most
NMF algorithms may get stuck in local minima, and hence, the initialization
plays a key role. In the performed tests, we applied the multistart initialization
described in [53] with
the following parameters: N=10 (number of restarts), Ki=30 (number of initial alternating steps), and Kf=1000 (number of final alternating steps). Each
initial sample of A and X has been randomly generated from a uniform
distribution. Each algorithm has been tested for two cases of inner iterations,
that is, with k=1 and k=5.
The inner iterations mean a number of iterative steps that are performed to
update only A (with fixed X,
i.e., before going to the update of X and vice versa). Additionally, the multilayer
technique [53, 54] with 3 layers (L=3) is applied.The multilayer technique can be regarded as multistep
decomposition. In the first step, we perform the basic decompositionY=A1X1 using any available NMF algorithm, where A1∈ℝI×J and X1∈ℝJ×T with I≥J.
In the second stage, the results obtained from the first stage are used to
perform the similar decomposition: X1=A2X2,
where A2∈ℝJ×J and X2∈ℝJ×T,
using the same or different update rules, and so on. We continue our
decomposition taking into account only the last achieved components. The process
can be repeated arbitrary many times until some stopping criteria are
satisfied. In each step, we usually obtain gradual improvements of the
performance. Thus, our model has the form Y=A1A2⋯ALXL with the basis matrix defined as A=A1A2⋯AL∈ℝI×J.
Physically, this means that we build up a system that has many layers or
cascade connection of L mixing subsystems.There are many stopping criteria for terminating the
alternating steps. We stop the iterations ifs≥Kf=1000 or the following condition ∥A(s)−A(s−1)∥F<ϵ is held, where s stands for the number of alternating step, and ϵ=10−5.
Note that the condition (20) can be also used as a stopping criterion,
especially as the gradient is computed in each iteration of the PG algorithms.The algorithms have been evaluated with the
signal-to-interference ratio (SIR) measures, calculated separately for each
source signal and each column in the mixing matrix. Since NMF suffers from
scale and permutation indeterminacies, the estimated components are adequately
permuted and rescaled. First, the source and estimated signals are normalized
to a uniform variance, and then the estimated signals are permuted to keep the
same order as the source signals. In NMFLAB [43], each estimated signal is compared to each source
signal, which results in the performance (SIR) matrix that is involved to make
the permutation matrix. Let xj and x^j be the jth source and its corresponding (reordered)
estimated signal, respectively. Analogically, let aj and a^j be the jth column of the true and its corresponding
estimated mixing matrix, respectively. Thus, the SIRs for the sources are given
by(53)SIRj(X)=−20log{∥x^j−xj∥2∥xj∥2},j=1,…,J,[dB]and similarly for each column in A we have(54)SIRj(A)=−20log{∥a^j−aj∥2∥aj∥2},j=1,…,J,[dB].We test the algorithms with the Monte Carlo (MC)
analysis, running each algorithm 100 times. Each run has been initialized with
the multistart procedure. The algorithms have been evaluated with the mean-SIR
values that are calculated as follows:(55)SIR¯X=1J∑j=1JSIRj(X),SIR¯A=1J∑j=1JSIRj(A),for each MC sample. The
mean-SIRs for the worst (with the lowest mean-SIR values) and best (with the
highest mean-SIR values) samples are given in Table 1. The number k means the number of inner iterations for
updating A,
and L denotes the number of layers in the multilayer
technique [53, 54]. The notation L=1 means that the multilayer technique was not
used. The elapsed time [in seconds] is measured in Matlab, and it informs us in
some sense about a degree of complexity of the algorithm.Table 1
Mean-SIRs [dB] obtained with 100 samples of Monte
Carlo analysis for the estimation of sources and columns of mixing matrix from
noise-free mixtures of signals in Figure1. Sources X are estimated with the projected
pseudoinverse. The number of inner iterations for updating A is denoted by k,
and the number of layers (in the multilayer technique) by L.
The notation best or worst in parenthesis that follows the
algorithm name means that the mean-SIR value is calculated for the best or
worst sample from Monte Carlo analysis, respectively. In the last column, the
elapsed time [in seconds] is given for each algorithm with k=1 and L=1.
AlgorithmMean-SIRA [dB]Mean-SIRX [dB]TimeL=1L=3L=1L=3k=1k=5k=1k=5k=1k=5k=1k=5M-NMF (best)2122.142.637.326.627.344.740.71.9M-NMF
(mean)13.113.826.723.114.715.228.927.6M-NMF
(worst)5.55.75.36.35.86.555.5OPL(best)22.925.346.54223.923.555.8511.9OPL(mean)14.71425.527.215.314.823.925.4OPL(worst)4.84.84.85.04.64.64.64.8Lin-PG(best)36.323.678.6103.734.233.378.592.88.8Lin-PG(mean)19.718.340.961.218.518.238.455.4Lin-PG(worst)14.413.117.540.113.913.818.134.4GPSR-BB(best)18.222.77.3113.822.854.39.4108.12.4GPSR-BB(mean)11.220.2753.11120.55.153.1GPSR-BB(worst)7.417.36.824.94.614.7223PSESOP(best)21.222.671.1132.223.455.556.5137.25.4PSESOP(mean)15.22029.457.315.934.527.465.3PSESOP(worst)8.315.86.928.78.216.67.230.9IPG(best)20.622.252.184.335.728.654.281.42.7IPG(mean)20.118.235.344.119.719.133.836.7IPG(worst)10.513.49.421.210.213.58.915.5IPN(best)20.822.659.965.853.552.468.667.214.2IPN(mean)19.417.338.222.522.819.136.621IPN(worst)11.715.27.57.15.721.52RMRNSD(best)24.721.622.257.930.243.525.562.43.8RMRNSD(mean)14.319.28.333.81721.58.433.4RMRNSD(worst)5.515.93.68.44.713.813.9SCWA(best)12.120.410.624.56.325.611.934.42.5SCWA(mean)11.216.39.320.95.318.69.421.7SCWA(worst)7.311.46.912.83.8103.310.8For comparison, Table1 contains also the results
obtained for the standard multiplicative NMF algorithm (denoted as M-NMF) that
minimizes the squared Euclidean distance. Additionally, the results of testing
the PG algorithms which were proposed in [53] have  been also included. The acronyms Lin-PG, IPG,
RMRNSD refer to the following algorithms: projected gradient proposed by Lin
[52], interior-point
gradient, and regularized minimal residual norm steepest descent (the
regularized version of the MRNSD algorithm that was proposed by Nagy and
Strakos [74]). These
NMF algorithms have been implemented and investigated in [53] in the context of their
usefulness to BSS problems.


## 5. Conclusions

The performance of the proposed NMF algorithms can be
inferred from the results given in Table1. In particular, the results show how
the algorithms are sensitive to initialization, or in other words, how easily
they fall in local minima. Also the complexity of the algorithms can be
estimated from the information on the elapsed time that is measured in Matlab.It is easy to notice that our NMF-PSESOP algorithm
gives the best estimation (the sample which has the highest best-SIR value),
and it gives only slightly lower mean-SIR values than the Lin-PG algorithm.
Considering the elapsed time, the PL, GPSR-BB, SCWA, and IPG belong to the
fastest algorithms, while the Lin-PG and IPN algorithms are the slowest.The multilayer technique generally improves the
performance and consistency of all the tested algorithms if the number of
observation is close to the number of nonnegative components. The highest
improvement can be observed for the NMF-PSESOP algorithm, especially when the
number of inner iterations is greater than one (typically,k=5).In summary, the best and the most promising NMG-PG
algorithms are NMF-PSESOP, GPSR-BB, and IPG algorithms. However, the final
selection of the algorithm depends on a size of the problem to be solved.
Nevertheless, the projected gradient NMF algorithms seem to be much better (in
the sense of speed and performance) in our tests than the multiplicative
algorithms, provided that we can use the squared Euclidean cost function which
is optimal for data with a Gaussian noise.



---

*Source: 939567-2008-07-06.xml*