ARTICLE IN PRESS

Signal Processing 86 (2006) 1157–1167
www.elsevier.com/locate/sigpro

Stereo echo cancellation algorithm using adaptive update on thebasis of enhanced input-signal vector
Satoru Emuraa, Youichi Hanedaa, Akitoshi Kataokaa,, Shoji Makinoba

NTT Cyberspace Laboratories, Musashino-shi, Tokyo, 180-8585, JapanNTT Communication Science Laboratories, Atsugi-shi, Kanagawa, 243-0198, Japanb

Received 1 January 2005; received in revised form 7 April 2005; accepted 4 June 2005
Available online 19 October 2005

Abstract
Stereo echo cancellation requires a fast converging adaptive algorithm because the stereo input signals are highly crosscorrelated and the convergence rate of the misalignment is slow even after preprocessing for unique identiﬁcation of stereo
echo paths. To speed up the convergence, we propose enhancing the contribution of the decorrelated components in the
preprocessed input-signal vector to adaptive updates. The adaptive ﬁlter coefﬁcients are updated on the basis of either asingle or multiple past enhanced input-signal vectors.
For a single-vector update, we show how this enhancement improves the convergence rate by analyzing the behavior of
the ﬁlter coefﬁcient error in the mean. For a two-past-vector update, simulation showed that the proposed enhancement
leads to a faster decrease in misalignment than the corresponding conventional second-order afﬁne projection algorithm
while computational complexities are almost the same.
r 2005 Elsevier B.V. All rights reserved.
Keywords: Stereo echo cancellation; Preprocessing; Increment vector; Enhanced input-signal vector

1. Introduction
Advanced teleconferencing features full duplex
communication and stereophonic sound transfer.
These features lead to a greater sense of presence
and more effective audio/video communication
between participants, but they also make acoustic
stereo echo cancellation indispensable.
The fundamental problem in acoustic stereo echo
cancellation is the unique identiﬁcation of thereceiving room’s impulse responses. Since the signals
reproduced by the two loudspeakers in the receiving
Corresponding author.

E-mail address: emura.satoru@lab.ntt.co.jp (S. Emura).

room are usually linearly related to each other [1–5],
the adaptive ﬁlter for stereo echo cancellation faces
an almost singular normal equation. This problem isof particular concern because lacking proper identiﬁcation, echo cancellation becomes dependent on theimpulse responses of the transmission room. Thisimplies that one must track not only changes in thereceiving room but also changes in the transmissionroom, which can be very rapid (e.g., when one person
stops talking and another starts).
Injection of uncorrelated components into received signals has been proposed as a way ofovercoming this problem [1–9]. Uncorrelated components should be injected at a level low enough sothat they are not noticeable in the speech.

0165-1684/$ - see front matter r 2005 Elsevier B.V. All rights reserved.
doi:10.1016/j.sigpro.2005.06.019

ARTICLE IN PRESS
1158

S. Emura et al. / Signal Processing 86 (2006) 1157–1167

However, this approach is only effective in
combination with a fast converging adaptive algorithm because the adaptive algorithm must stillsolve the ill-conditioned normal equation even after
the preprocessing.
The high computational expense of fast-converging time-domain adaptive algorithms is wellknown. The two-channel fast recursive least-squares(FRLS) algorithm is seven times as computationallyintensive as the conventional two-channel normalized least-mean-square (NLMS) algorithm [10]. The
high-order afﬁne projection algorithm (APA) is also
more computationally intensive than the conventional NLMS: in this case, it is proportional to thesquare of the projection order [11]. The fast
converging sub-band and frequency-domain adaptive algorithms inevitably incur processing delay,
although both are much less computationallycomplex than the NLMS algorithm [12,13].
In this paper, we propose updating the adaptiveﬁlter on the basis of an enhanced input-signal vector
for obtaining a novel fast-converging adaptivealgorithm. The basic idea of the algorithm is togenerate an increment vector, i.e., a vector used to
update the adaptive ﬁlter, with a smaller interchannel cross-correlation than the preprocessed
stereo signal itself [14,15].
The enhanced NLMS is obtained by replacing thegradient vector in the NLMS algorithm with anenhanced input-signal vector in which the uncorrelated component introduced for unique identiﬁcation is enhanced by a simple operation. We extend
the enhanced NLMS to the adaptive update on
multiple bases to improve the convergence rate.
This generalized version of the enhanced NLMS(GENLMS) is obtained from APA in the samemanner. Simulation showed that the second-order
GENLMS decreased the misalignment between theestimated and true echo paths more quickly while
being computationally as efﬁcient as APA with thesame low order.
This paper is organized as follows. In Section 2,
the NLMS and APA are reviewed as two conventional adaptive algorithms for stereo echo cancellation. The enhanced NLMS is presented in Section 3.
The convergence properties of the enhanced NLMS
are discussed in Section 4. In Section 5, theenhanced NLMS is extended to the adaptive updateon multiple bases. Section 6 presents simulation
results that demonstrate the effectiveness of enhancing the injected uncorrelated component in theincrement vector of the ﬁlter coefﬁcients.

2. Conventional adaptive algorithms and theirproblems
Fig. 1 schematically shows a typical system forstereo echo cancellation. In the transmission room,
stereo signals u1 ðkÞ and u2 ðkÞ are picked up by thetwo microphones and transmitted. In the receivingroom, low-level uncorrelated components v1 ðkÞ andv2 ðkÞ are injected into the received stereo signals to
avoid the non-uniqueness problem:x1 ðkÞ ¼ u1 ðkÞ þ v1 ðkÞ;(1)x2 ðkÞ ¼ u2 ðkÞ þ v2 ðkÞ:The signal yðkÞ at the microphone is expressed byyðkÞ ¼ hT xðkÞ,(2)

h ¼ ½hT1 hT2 T

is the concatenation of thewherevectors of the true impulse responses h1 and h2 .
The input-signal vector xðkÞ is deﬁned as
"
# "
# "
#
x1 ðkÞ
u1 ðkÞ
v1 ðkÞ
xðkÞ ¼¼
þ
,(3)
x2 ðkÞ
u2 ðkÞ
v2 ðkÞ
whereui ðkÞ ¼ ½ui ðkÞ    ui ðk  L þ 1ÞT ;i ¼ 1; 2,vi ðkÞ ¼ ½vi ðkÞ    vi ðk  L þ 1ÞT ;i ¼ 1; 2.

Here, L is the length of the impulse-response
vectors.
The error eðkÞ is expressed byeðkÞ ¼ yðkÞ  h^ T ðkÞxðkÞ,(4)^
where hðkÞ
¼ ½h^ T1 ðkÞ h^ T2 ðkÞT is the concatenation of
the vectors of adaptive ﬁlter coefﬁcients h^ 1 ðkÞ andh^ 2 ðkÞ. Note that, for simplicity, we only consider the
acoustic paths to one microphone in the receiving
x2(k)

u2(k)
u1(k)

v2(k)

x1(k)

v1(k)
h1(k)

h2

h2(k)
h1(k)

e(k)

y(k)

Fig. 1. Typical stereo echo cancellation system.

ARTICLE IN PRESS
S. Emura et al. / Signal Processing 86 (2006) 1157–1167

room; a similar analysis will apply to the othermicrophone.
In the stereo echo cancellation system shown in
Fig. 1, the two sides of the original stereo signal
from the transmission room will obviously havestrong inter-channel cross-correlation because bothoriginate from the same source, the single talker.
The preprocessed stereo signal still has strong interchannel cross-correlation since effects of preprocessing must be inaudible and the level of uncorrelated
components is restricted.
In conventional two-channel NLMS, the vectorof adaptive ﬁlter coefﬁcients is updated in thefollowing way:
^ þ 1Þ ¼ hðkÞ^^hðk
þ mDhðkÞ,
^
DhðkÞ
¼

"
#
x1 ðkÞ
eðkÞ.
xT1 ðkÞx1 ðkÞ þ xT2 ðkÞx2 ðkÞ þ d x2 ðkÞ
ð5ÞThe directional component of the increment vector
obviously contains no cross term involving bothx1 ðkÞ and x2 ðkÞ. Since the strong inter-channel
cross-correlation of the preprocessed stereo signal
remains in the increment vector as it is, theconvergence of misalignment is slow [2].
In conventional two-channel APA, the increment
vector consists of multiple input-signal vectors withstrong inter-channel cross-correlation. As with
NLMS, the increment vector’s directional component
contains no cross term involving x1 ðkÞ and x2 ðkÞ:"#x1 ðkÞ
^DhðkÞ¼ c0 ðkÞ
x2 ðkÞ
"#x1 ðk  p þ 1Þ
þ    þ cp1 ðkÞ.
ð6Þ
x2 ðk  p þ 1ÞThe weights c0 ðkÞ; . . . ; cp1 ðkÞ are obtained as23c0 ðkÞ
67..
6
7
6
7 ¼ ½XT ðkÞXðkÞ1.
45cp1 ðkÞ
3
2^
yðkÞ  xT1 ðkÞhðkÞ
7
6
7
6
..
7,
6
.
7
6
5
4
^
yðk  p þ 1Þ  xT ðk  p þ 1ÞhðkÞ
1

whereXðkÞ ¼ ½xðkÞ; . . . ; xðk  p þ 1Þ.

1159

When the projection order p is low, the inter-sample
correlation is largely removed, but the inter-channel
cross-correlation partially remains in the increment
vector. This inter-channel cross-correlation slows theconvergence of misalignment.
3. New adaptive algorithm
We propose an enhanced form of the NLMS
(enhanced NLMS) that overcomes the problem ofslow convergence in this section.
The basic idea of this algorithm is to increase thecontribution of injected components to the increment vector. The injected components v1 ðkÞ andv2 ðkÞ are designed to introduce uncorrelated components into the linearly correlated original input
signals u1 ðkÞ and u2 ðkÞ [1]. This enhancement should
reduce the inter-channel cross-correlation in theincrement vector, and in turn improve the rate ofconvergence.
The enhanced NLMS is derived by replacing theincrement vector for the NLMS algorithm:^mDhðkÞ
¼ mxðkÞ

eðkÞ,xT ðkÞxðkÞ þ d

(7)

where
"
xðkÞ ¼

u1 ðkÞ

#"þu2 ðkÞ

v1 ðkÞ

#v2 ðkÞ

,(8)

with a new increment vector:^mDhðkÞ
¼ mzðkÞ

eðkÞ,xT ðkÞzðkÞ þ d

(9)

where
"
zðkÞ ¼

u1 ðkÞ
u2 ðkÞ

#"þsv1 ðkÞ
v2 ðkÞ

#
ðs41Þ

(10)

and d is a small positive constant used to avoid
division by 0.
An enhancement factor sð41Þ is used tocontrol the contribution of the uncorrelated com^ponents to the increment vector mDhðkÞ,while
keeping their contribution constant in thestereo loudspeaker signal xðkÞ. The larger s in the
new increment vector increases the contributionof the uncorrelated components to adaptive updating. Note that the enhanced NLMS algorithm withs ¼ 1 is identical to the conventional NLMS
algorithm.

ARTICLE IN PRESS
1160

S. Emura et al. / Signal Processing 86 (2006) 1157–1167

Proposed enchanced NLMS

Conventional NLMS algorithm^
Fig. 2. Signal ﬂow in the conventional NLMS algorithm and the proposed enhanced NLMS, where mDhðkÞ==xðkÞ
means that the direction^^of mDhðkÞ
is the same as that of xðkÞ. The increment vector mDhðkÞ
for the enhanced NLMS is generated from enhanced input-signal vector
zðkÞ, where the enhancement factor s controls the contribution of uncorrelated components vðkÞ introduced by preprocessing.

This algorithm can be derived by obtaining theweight c0 ðkÞ for^DhðkÞ
¼ zðkÞc0 ðkÞ(11)error, thus deriving the range where the enhancement is effective.
4.1. Assumptions

that satisﬁesT^^yðkÞ ¼ ½hðkÞ
þ DhðkÞ
xðkÞ.

(12)

Hence, the denominator of (9) is given asxT ðkÞ zðkÞ þ d, whereas that of (7) is xT ðkÞ xðkÞ þ d.
Fig. 2 shows the signal ﬂow of the conventional
NLMS algorithm and the proposed enhanced
NLMS. In both cases, the input to the echo paths
is the same stereo signal. This means that the same
preprocessed stereo sound is reproduced by the
loudspeakers. In addition, the input to the time^varying ﬁlter hðkÞis the same stereo-input signal^
vector, from which echo replica yðkÞis generated.
^
On the other hand, the increment vector mDhðkÞ
ofthe enhanced NLMS is generated not from inputsignal vector xðkÞ but from enhanced input-signal
vector zðkÞ, in which the contribution of theuncorrelated component is enhanced by the enhancement factor s.
In the conventional NLMS algorithm, we canalso enhance the uncorrelated component in theincrement vector (7) by using large v1 ðkÞ and v2 ðkÞ.
However, amplifying these components of thestereo loudspeaker signals degrades the reproduced
speech.
4. Properties of enhanced NLMS
In this section, we validate our idea of enhancing
the injected uncorrelated component in the increment vector. Firstly, we investigate the behavior of
the ﬁlter coefﬁcient error in the mean and show thatthe enhanced NLMS converges and that its
convergence rate is improved. Secondly, we investigate the behavior of the norm of the coefﬁcient

In the following analysis, we use low-level
independent random noise as the uncorrelated
component injected into each channel for correct
identiﬁcation of the echo paths.
We make the following assumptions about the
injected signals v1 ðkÞ and v2 ðkÞ.
(A1) Neither signal is correlated with the original
stereo signal.
(A2) The signal power levels are given by
Efv21 ðkÞg ¼ Efv22 ðkÞg ¼ w,

(13)

where Efg denotes mathematical expectation. We
also assume:(A3) The input signals u1 ðkÞ and u2 ðkÞ are zeromean and wide-sense stationary. The covariancematrix is independent of time k and can be
diagonalized by using the orthogonal matrix A(AT A ¼ AAT ¼ I2L Þ as(")#
u1 ðkÞ
T
T
Ru ¼ E½u1 ðkÞ u2 ðkÞu2 ðkÞ
¼ AT diagðq2L ; . . . ; q1 ÞA
q2L X    Xq1 X0,

ð14Þ

where I2L denotes the 2L  2L identity matrix.
Throughout this section, we assume that 0omp1,
because step size m is usually set smaller than orequal to 1.
4.2. Transition of mean coefficient error
Let us study the behavior of the mean coefﬁcienterror of the adaptive ﬁlter in the transformed space.
Under the above assumptions, this behavior is

ARTICLE IN PRESS
S. Emura et al. / Signal Processing 86 (2006) 1157–1167

determined by a similar transition formula to thatfor the least-mean square (LMS) algorithm. We cananalyze its convergence in the same way as that of
the LMS [16,17].
The coefﬁcient error in the transformed space isdeﬁned as^sðkÞ ¼ ½s1 ðkÞ    s2L ðkÞT ¼ A½h  hðkÞ.

ð15Þ

This vector of the coefﬁcient error is updated by theenhanced NLMS in this way:sðk þ 1Þ ¼ sðkÞ  mA

zðkÞ
eðkÞ,
T
x ðkÞzðkÞ

(16)

where the regularization is omitted for simplicity.
Substituting^eðkÞ ¼ xT ðkÞh  xT ðkÞhðkÞ
¼ xT ðkÞAT sðkÞ(17)

into the update Eq. (16), we get the following
transition formula [16,17].
sðk þ 1Þ ¼ TS ðkÞsðkÞ,

(18)

where
TS ðkÞ ¼ I2L  mA

zðkÞxT ðkÞ TA .
xT ðkÞzðkÞ

(19)

4.3. Convergence in the mean
We can analyze the behavior of the mean
coefﬁcient error EfsðkÞg by analyzing the largest
eigenvalue of EfTS ðkÞg, which determines theconvergence rate of EfsðkÞg.
The largest eigenvalue of EfTS ðkÞg is given bylmax ðEfTS ðkÞgÞ ¼ 1  m

q1 þ sw,
Q þ sW(21)

where q1 is the smallest eigenvalue of the covariancematrix Ru of the stereo input signal before
preprocessing.
This largest eigenvalue lmax ðEfTS ðkÞgÞ satisﬁes
0olmax ðEfTS ðkÞgÞo1,(22)

q1 þswo1.
since 0omp1 and 0o QþsWTherefore, the coefﬁcient error of the adaptiveﬁlter converges in the mean.
For the correlated stereo input signal, the smallest
eigenvalue q1 of the covariance matrix Ru is almost
0 [3]. The following approximation holds for thelargest eigenvalue of EfTS ðkÞg.

sw
Q þ sWw.
¼1m
Q=s þ Wlmax ðEfTS ðkÞgÞ ﬃ 1  m

For large ﬁlter order Lb1, the squared normxT ðkÞxðkÞ of the stationary input-signal vector xðkÞbecomes almost independent of time, and can beapproximated by a constant [18]. Similarly,xT ðkÞzðkÞ can be approximated by a constantQ þ sW , where
Q ¼ trace of diagðq2L ; . . . ; q1 Þ;
W ¼ trace of w I2L :See Appendix for details.
For a sufﬁciently small step size, the variations of
the coefﬁcient error vector are much slower thanthose of the input signal, so zðkÞxT ðkÞ can be
replaced with its ensemble average (‘‘direct averaging’’, [16,18]). The mean transition matrix
EfTS ðkÞg is the following diagonal matrix:mAEfzðkÞxT ðkÞgAT
Q þ sWm¼ I2L Q þ sW2
30
q2L þ sw
6
7
..
6
7
6
7,
.
4
5
0
q1 þ sw

1161

EfTS ðkÞg ¼ I2L 

ð23ÞThis largest eigenvalue is monotonically decreasingfor 1ps. Hence, a larger enhancement factor s can
reduce the largest eigenvalue lmax ðEfTS ðkÞgÞ and
improve the convergence rate of the mean coefﬁcient error.

4.4. Transition of coefficient error norm
Next, we investigate the range of s where theenhancement is effective. For that purpose, we
analyze the behavior of the norm of the coefﬁcienterror vector. This norm must be decreasing for theconvergence of the coefﬁcient error.
The coefﬁcient error vector is deﬁned as^ þ 1Þmðk þ 1Þ ¼ h  hðk(24)

and its evolution is given asð20Þmðk þ 1Þ ¼ mðkÞ  mzðkÞeðkÞ
,xT ðkÞzðkÞ

(25)

where the regularization is omitted for simplicity.

ARTICLE IN PRESS
S. Emura et al. / Signal Processing 86 (2006) 1157–1167

1162

The evolution of its norm kmðkÞk2 is given aszðkÞeðkÞ Tkmðk þ 1Þk2 ¼ mðkÞ  m T
x ðkÞzðkÞ
zðkÞeðkÞ mðkÞ  m T
x ðkÞzðkÞ
zðkÞeðkÞ
¼ mT ðkÞmðkÞ  2m mT ðkÞ
Q þ sW2QþsW
e2 ðkÞ,ð26Þ
þ m2
ðQ þ sW Þ2
where we have used the relationsTzðkÞ xðkÞ ﬃ Q þ sW ,T

For large ﬁlter order Lb1, the squared normxT ðkÞxðkÞ of the stationary input-signal vector xðkÞcan be approximated by a constant [18]. Similarly,zðkÞT zðkÞ and zðkÞT xðkÞ can be approximated by aconstant.
By substituting eðkÞ ¼ xT ðkÞ mðkÞ into the above
equation, we obtain the difference between thenorms of the coefﬁcient error vector as

ð27Þ

By taking the mathematical expectation, we canfurther rewrite the above equation as

ð28Þ

where we resort to the independence assumptions.
That is, we assume that coefﬁcient error vector mðkÞis statistically independent of xðkÞ and zðkÞ [16,17].
We have also used the relationsEfzðkÞxðkÞT g ¼ AT ðQ þ swIÞA,4.5. Contractivity on coefficient error norm
For the coefﬁcient error vector to converge, thenorm of coefﬁcient error vector kmðkÞk2 must
decrease on average for every iteration step.
The difference of the mean norm can be rewritten
as the weighted inner product of ðAmðkÞÞ byEfkmðk þ 1Þk2 g  EfkmðkÞk2 gPTðAmðkÞÞ ,¼ E ðAmðkÞÞ
Q þ sW

ð30Þ

P ¼  2mðQ þ swIÞzðkÞ zðkÞ ﬃ Q þ s W .

Efkmðk þ 1Þk2 g  EfkmðkÞk2 g




2m
E zðkÞxT ðkÞ¼ E mT ðkÞ Q þ sW


2
Q
þ
s
W
T
EfxðkÞx
ðkÞg
mðkÞ
þ m2
ðQ þ sW Þ21ð2mðQ þ swIÞ
¼ E mT ðkÞAT
Q þ sW
Q þ s2 Wþ m2
ðQ þ wIÞÞAmðkÞ ,Q þ sW

(29)

where

2

kmðk þ 1Þk2  kmðkÞk2
2mTzðkÞxT ðkÞ¼ m ðkÞ Q þ sW
22 Qþs W
TþmxðkÞx ðkÞ mðkÞ.
ðQ þ sW Þ2EfxðkÞxðkÞT g ¼ AT ðQ þ wIÞA.

þ m2

Q þ s2 WðQ þ wIÞ.
Q þ sW

ð31Þ

The matrix P is diagonal, and its diagonal elements
are given by
Pjj ¼ 2mðqj þ swÞ þ m2

Q þ s2 Wðq þ wÞ.
Q þ sW j(32)

For EfkmðkÞk2 g to decrease, we must ﬁnd thecondition where all the diagonal elements
Pjj ð1pjp2LÞ must be negative. If there exists Pjj
greater than 0, then EfkmðkÞk2 g is increasing andthe adaptive ﬁltering becomes unstable. The balanceof the ﬁrst and second terms determines whether
Pjj is negative. The ﬁrst term of Pjj is always
negative in 1ps, since 0omp1, qj X0, and w40.
The second term is positive and monotonicallyincreasing for 1ps, since 0omp1, Q40, W 40,
qj X0, w40, andd Q þ s2 W
W 2 s2 þ WQð2s  1Þ40.
¼
ds Q þ sWðQ þ sW Þ2
Fig. 3sketches Pjj =w as a function of the enhancement factor s for qj ¼ w; 10w; 30w; 100w, where step
size m is set to 0.3 and W =Q is set to 25 dB. Thisgraph indicates that there exists a range of s where
Pjj ð1pjp2LÞ is negative and the upper bound of
this range is small for larger qj . Note that q2L =w is
not less than Q=W ¼ 25 dB ’ 316:2, sinceq1 þ    þ q2LQ
and q2L X    Xq1 X0.
¼
W
2Lw
By solving Pjj o0 ð1pjp2LÞ for s, we could
obtain the range of s as complicated functions of
the eigenvalue qj of the covariance matrix Ruof stereo input signal. Instead, we obtain a narrower

ARTICLE IN PRESS
S. Emura et al. / Signal Processing 86 (2006) 1157–1167

We can easily apply this approach to theenhanced NLMS. We can derive a new adaptivealgorithm by replacing the increment vector of
APA, given by a linear combination of
xðkÞ; . . . ; xðk  p þ 1Þ, with a new increment vector
given
by
a
linearcombinationofzðkÞ; . . . ; zðk  p þ 1Þ. Hereafter, we call this algorithm the generalized version of the enhanced
NLMS (GENLMS).
The pth order GENLMS is represented by

60
40

Pjj (σ) / w

200

qj = w
qj = 10w-20

qj = 30w

-40
-60

1163

^ þ 1Þ ¼ hðkÞ^^hðk
þ mDhðkÞ,qj = 100w

100

(36)

where
101

102

^
DhðkÞ
¼ ZðkÞ½XT ðkÞZðkÞ þ dI1 eðkÞ,XðkÞ ¼ ½xðkÞ; . . . ; xðk  p þ 1Þ,Enhancement factor σ
Fig. 3. Pjj =w as a function of the enhancement factor s forvarious qj .

ZðkÞ ¼ ½zðkÞ; . . . ; zðk  p þ 1Þ.
Here, eðkÞ is the error signal vector of dimension p,
deﬁned by(and easy-to-handle) range of s by using theinequality

This algorithm is derived by obtaining weights
c0 ðkÞ; . . . ; cp1 ðkÞ for22Qþs Wðq þ wÞ
Pjj ¼  2mðqj þ swÞ þ m
Q þ sW jQ þ s2 W 2 o0.
o mðqj þ wÞ m
Q þ sW

ð33Þ

From (33), we see that the mean norm ofEfkmðkÞk2 g decreases when s satisﬁesmQ þ s2 W
 2p0.
Q þ sW^eðkÞ ¼ ½yðkÞ; . . . ; yðk  p þ 1ÞT  XT ðkÞhðkÞ.

(34)

This condition is further rewritten in terms of s as
pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ
1 þ 1 þ mð2  mÞ=W =Q
,
(35)
1psp
m
where W =Q is the ratio of the total power of
injected signals to the total power of received
signals.
5. Extension to the update on multiple bases
In this section, we extend the enhanced NLMS to
the adaptive update on multiple bases as in the APA
to improve the convergence rate. APA linearly
combines multiple delayed input signal vectors to
reduce the inter-sample correlation in the increment
vector. Such a decorrelated increment vector improves the convergence rate for colored input
signals [19,20].

^DhðkÞ
¼ zðkÞc0 ðkÞ þ    þ zðk  p þ 1Þcp1 ðkÞ
2
3
c0 ðkÞ
67..
6
7¼ ZðkÞ67.
4
5cp1 ðkÞ

ð37Þ

that satisfy the last p input–output relationships^^yðkÞ ¼ xT ðkÞ½hðkÞ
þ DhðkÞ;...;^^yðk  p þ 1Þ ¼ xT ðk  p þ 1Þ½hðkÞ
þ DhðkÞ:
These p input–output relationships are equivalent to
the following equation:^eðkÞ ¼ XT ðkÞDhðkÞ
2
6
6¼ XT ðkÞZðkÞ64

c0 ðkÞ

3

..
.

7
7
7.
5

cp1 ðkÞ

ð38Þ

Hence, the weights c0 ðkÞ; . . . ; cp1 ðkÞ are obtained as23c0 ðkÞ
67..
6
7 ¼ ½XT ðkÞZðkÞ1 eðkÞ
(39)
.
4
5
cp1 ðkÞARTICLE IN PRESS
S. Emura et al. / Signal Processing 86 (2006) 1157–1167

1164

6.1. Performance of the enhanced NLMS

or, with a regularization constant d, as2
3c0 ðkÞ
67..
6
7 ¼ ½XT ðkÞZðkÞ þ dI1 eðkÞ.
.
4
5

(40)

cp1 ðkÞ

Substituting (40) into (37) yields the increment. As
shown in (37), this vector is a linear combination ofvectors zðkÞ; . . . ; zðk  p þ 1Þ, each of which has low
inter-channel cross-correlation.
The computational complexity of GENLMS isalmost the same as that of the conventional APA
because we can easily generate vector zðkÞ from thesignal samples ui ðkÞ þ svi ðkÞ; i ¼ 1; 2. There is noneed for vector calculation to obtain vector zðkÞ ¼
uðkÞ þ svðkÞ for each sample.
6. Simulation
In this section, we report on our conﬁrmation of
the validity of the proposed idea through computer
simulation. We investigated the behavior of theenhanced NLMS and second-order GENLMS.
We evaluated the performance of the proposed
adaptive algorithm in terms of the misalignment as
deﬁned by2^
kh  hðkÞk
,
khk2

(41)

Misalignment [dB]

Misalignment [dB]

where h is the vector of truncated impulse responsesof the receiving room. It is possible to have goodecho cancellation even when the degree of misalignment is large. In such a case, however, thecancellation will become less effective if the impulse
response in the transmission room changes.

Firstly, we investigated the convergence rate of
the enhanced NLMS. We used samples of the 16
different colored noise sequences speciﬁed in the
P50 recommendations (which are representative of
the speech signal) [21] as the sound source in thetransmission room. The received signals werecorrelated stereo pseudo speech signal followed byuncorrelated stereo white noise signal. The stereo
pseudo speech signal was obtained by convolving
the above sound source signals and transmission
paths measured in a conference room with areverberation time of 200 ms. The true echo paths
were also measured in a conference room and thentruncated to 2048 taps. The sampling frequency was
16 kHz.
We used independent random noises with equal
power as the injected signal for preprocessing as in
the analysis in Section 4. Their total power was set
to –25 dB of the total power of the received signals
ðW =Q ¼ 25 dBÞ. The adaptive ﬁlter had 1536 taps
on each channel. Step size m was set to 0.3.
Fig. 4 shows the behavior of average misalignment for the enhanced NLMS with enhancement
factor s ¼ 1; 2; 4; 10 (note that the enhanced NLMS
with s ¼ 1 is identical to the conventional NLMS
algorithm). We can see that a larger enhancement
factor improved the convergence rate of misalignment in the enhanced NLMS. The dotted line shows
the case of the NLMS algorithm without preprocessing, where the misalignment decreased rapidly inthe ﬁrst second, but approached saturation fromabout –3.5 dB. With preprocessing, the misalignment continued to decrease slowly, reaching around–4 dB at t ¼ 20 s. This was improved to –10.5 dB by

-5

-10

-10
-20
-30
-40

0
(a)

5

10
t [s]

15

20

0
(b)

10

20
t [s]

30

40

Fig. 4. Behavior of average misalignment for the conventional NLMS algorithm without preprocessing (dotted line) and the enhanced
NLMS algorithm with preprocessing and various values of enhancement factor s (the enhanced NLMS algorithm with s ¼ 1 is identicalto the conventional NLMS algorithm). The inputs were (A) correlated stereo pseudo speech signals, (B) correlated stereo pseudo speech
signals (0–20 s) and uncorrelated stereo white noise signal (20–40 s).

ARTICLE IN PRESS
S. Emura et al. / Signal Processing 86 (2006) 1157–1167

increasing s to 10 in the enhanced NLMS. In eachcase, the ﬁnal misalignment was around 40 dB at
t ¼ 30 s.
Next, we experimentally checked the validity of
the convergence properties given in Section 4. For
that purpose, we investigated the convergence
behavior of the enhanced NLMS as a function of
the enhancement factor s when the step size m was
set to 0.1, 0.3, and 0.5. We used one received stereo
signal in the previous simulation.
Fig. 5 shows the misalignment after 20-s adaptation for various values of s. Each curve has a point
where the misalignment was at its minimum. As s
increased from 1 to this point, the misalignment
improved gradually. When s exceeded this point,
the misalignment deteriorated suddenly. The triangles indicate the theoretical upper bounds of therange of s given by (35). We can see that theadaptive estimation did not deteriorate within thisrange. This result indicates that Pjj given by (32)increases rapidly and exceeds 0 when s exceeds theupper bound of (35).
6.2. Performance of the enhanced NLMS for speech
Next, we investigate the convergence rate of theenhanced NLMS for speech and nonlinear preprocessing. The received signals were obtained byconvolving a speech and transmission paths measured in a conference room with a reverberation
time of 200 ms. The true echo paths were also1165

measured in a conference room and then truncatedto 2048 taps. The sampling frequency was 16 kHz.
We used half-wave rectiﬁersuðkÞ þ juðkÞj
,2uðkÞ  juðkÞj
v2 ðkÞ ¼ a
2

v1 ðkÞ ¼ að42Þ

with a ¼ 0:3 as nonlinear functions for preprocessing. For this value, it was reported that there wasno audible degradation of the original signal [22]. A
white-noise signal with 40-dB SNR was added as
ambient noise to the signal arriving at the microphone, which then produced output signal yðkÞ. The
adaptive ﬁlter had 1536 taps on each channel. Step
size m was set to 0.3.
Fig. 6 shows the behavior of misalignment for the
NLMS and enhanced NLMS with enhancement
factor s ¼ 10. We can see that the enhanced NLMS
improved the convergence rate of misalignment.
The dotted line shows the case of the NLMS
algorithm without nonlinear preprocessing, where
the misalignment decreased rapidly in the ﬁrst
second, but approached saturation from about–3.5 dB. With nonlinear preprocessing, the misalignment continued to decrease slowly, reachingaround –6 dB at t ¼ 20 s. This was improved to–9 dB by increasing s to 10 in the enhanced NLMS.

00Misalignment [dB]

NLMS without NP

Misalignment [dB]-5µ = 0.1-10µ = 0.3

NLMS with NP-5

Proposed-10-15µ = 0.5

-15

-20
100

0
101
Enhancement factor σ

102

Fig. 5. Misalignment after 20-s adaptation as a function ofenhancement factor s. The triangles show the upper bounds ofthe range of s for corresponding step sizes.

5

10
t [s]

15

20

Fig. 6. Behavior of misalignment for the conventional NLMS
algorithm with and without nonlinear preprocessing (without
NP: dotted line) and the enhanced NLMS algorithm withenhancement factor s ¼ 10. The input was a correlated stereo
speech signal. The nonlinearity gain a was 0.3.

ARTICLE IN PRESS
S. Emura et al. / Signal Processing 86 (2006) 1157–1167

1166

6.3. Performance of the second-order GENLMS for
speechNext, we investigate the convergence rate of
GENLMS for speech and nonlinear preprocessing.
We used the same simulation settings as in theprevious simulation.
Fig. 7 shows the behavior of misalignment for theconventional second-order APA and the secondorder GENLMS ðp ¼ 2Þ with the enhancement
factor s ¼ 10. We can see that the second-order
GENLMS improved the convergence rate of misalignment. The dotted line shows the case of theconventional second-order APA without nonlinear
preprocessing, where the misalignment again saturated at about –3.5 dB. With nonlinear preprocessing, the misalignment decreased slowly to –8.5 dB
at t ¼ 20 s. This was improved to –15.2 dB by
increasing s to 10 for the second-order GENLMS.
Note that the second-order GENLMS can beexactly implemented with the same computational
complexity as that of NLMS by using the techniqueof the fast APA [23,24].
7. Conclusion
We have proposed updating the adaptive ﬁlter for
stereo echo cancellation on the basis of an enhanced
input-signal vector for obtaining a novel fastconverging adaptive algorithm. The increment0

Misalignment [dB]2ndAppendix
In this appendix, we obtain the statistical properties of the signal vectors that appear in Section 4.
Based on Assumptions (A1), (A2) and (A3), we
obtain(") "##u1 ðkÞ T
0L 0L
T
E
(43)
½v ðkÞ v2 ðkÞ ¼
u2 ðkÞ 1
0L 0L
and
("
E

) "
#
v1 ðkÞ TwILT½v1 ðkÞ v2 ðkÞ ¼
v2 ðkÞ
0L

#
0L
,
wIL

(44)

where IL is the L  L identity matrix, and 0L is the
L  L zero matrix.
In addition, we obtain("#)
v1 ðkÞ
T
T
E ½v1 ðkÞ v2 ðkÞ
¼W
(45)
v2 ðkÞ

2nd order APA without NP-5vector used to update the adaptive ﬁlter enhances
the uncorrelated component injected for unique
identiﬁcation of the echo paths. We showed how
this enhancement is effective by analyzing thestatistical behavior of the enhanced NLMS. Next,
we extended the enhanced NLMS to the generalizedversion of the enhanced NLMS (GENLMS), where
the adaptive ﬁlter is updated on multiple bases as in
the APA to improve the convergence rate.
Simulation demonstrated that the two-channel
second-order GENLMS decreased the misalignment of the adaptive ﬁlter more quickly than theconventional two-channel NLMS algorithm or thesecond-order APA, while having the same computational complexity as the two-channel secondorder APA.

order APA with NP

-10

and
(

Proposed-15

E½uT1 ðkÞ

"uT2 ðkÞv1 ðkÞ
v2 ðkÞ

#)
¼ 0,

(46)

where

-20
0

5

10
t [s]

15

20

Fig. 7. Behavior of misalignment for the conventional secondorder afﬁne projection algorithm with and without nonlinear
preprocessing (without NP: dotted line) and the second-order
generalized version of the enhanced NLMS (GENLMS) withenhancement factor s ¼ 10. The input was a correlated stereo
speech signal. The nonlinearity gain a was 0.3.

W ¼ trace of wI2L .
From the assumptions about the stereo input signalthat lead to (14), we obtain("#)
u1 ðkÞ
T
T
E ½u1 ðkÞ u2 ðkÞ
¼ Q,
(47)
u2 ðkÞARTICLE IN PRESS
S. Emura et al. / Signal Processing 86 (2006) 1157–1167

where
Q ¼ trace of diagðq2L ; . . . ; q1 Þ.
Consequently, for"# "#u1 ðkÞ
v1 ðkÞ
xðkÞ ¼þandu2 ðkÞ
v2 ðkÞ
"#"#v1 ðkÞ
u1 ðkÞþs,¼u2 ðkÞ
v2 ðkÞ

zðkÞ

we obtainAEfxðkÞxT ðkÞgAT
¼ diagðq2L ; . . . ; q1 Þ þ wI2L ,ð48ÞAEfzðkÞzT ðkÞgAT
¼ diagðq2L ; . . . ; q1 Þ þ s2 wI2L ,ð49ÞAEfzðkÞxT ðkÞgAT
¼ diagðq2L ; . . . ; q1 Þ þ swI2L .

ð50Þ

In addition,
EfxT ðkÞzðkÞg ¼ Q þ sW .

(51)

References[1] M.M. Sondhi, D.R. Morgan, J.L. Hall, Stereophonicacoustic echo cancellation—an overview of the fundamental
problem, IEEE Signal Process. Lett. 2 (8) (1995) 148–151.
[2] S. Shimauchi, S. Makino, Stereo projection echo canceller
with true echo path estimation, in: Proceedings of
ICASSP95, 1995, pp. 3059–3062.
[3] J. Benesty, D.R. Morgan, M.M. Sondhi, A better understanding and an improved solution to the problems ofstereophonic acoustic echo cancellation, IEEE Trans.
Speech Audio Process. 6 (2) (March 1998) 156–165.
[4] S. Makino, S. Shimauchi, Stereophonic acoustic echo
cancellation—an overview and recent solutions, in: Proceedings of IWAENC99, 1999, pp. 941–944.
[5] E. Haensler, G. Schmidt, Acoustic Echo and NoiseControl—A Practical Approach, Wiley, New York, 2004.
[6] Y. Joncour, A. Sugiyama, A stereo echo canceller with preprocessing for correct echo-path identiﬁcation, in: Proceedings of ICASSP98, 1998, pp. 3677–3680.
[7] A. Gilloire, V. Turbin, Using auditory properties to improvethe behavior of stereophonic acoustic echo cancellers, in:Proceedings of ICASSP98, 1998, pp. 3681–3683.

1167[8] M. Ali, Stereophonic acoustic echo cancellation system using
time-varying all-pass ﬁltering for signal decorrelation, in:Proceedings of ICASSP98, 1998, pp. 3689–3692.
[9] S. Shimauchi, S. Makino, Y. Haneda, A. Nakagawa, S.
Sakauchi, A stereo echo canceller implemented using astereo shaker and a duo-ﬁlter control system, in: Proceedingsof ICASSP99, 1999, pp. 857–860.
[10] J. Benesty, F. Amand, A. Gilloire, Y. Grenier, Adaptiveﬁltering algorithms for stereophonic acoustic echo cancellation, in: Proceedings of ICASSP95, 1995, pp. 3099–3102.
[11] F. Amand, J. Benesty, A. Gilloire, Y. Grenier, A fast twochannel projection algorithm for stereophonic acoustic echo
cancellation, in: Proceedings of ICASSP96, 1996, pp.
949–952.
[12] S. Makino, K. Strauss, S. Shimauchi, Y. Haneda, A.
Nakagawa, Subband stereo echo canceller using the projection algorithm with fast convergence to the true echo path,in: Proceedings of ICASSP97, 1997, pp. 299–302.
[13] J. Benesty, D.R. Morgan, Frequency domain adaptiveﬁltering revisited, generalization to the multi-channel case,and application to acoustic echo cancellation, in: Proceedings of ICASSP2000, 2000, pp. 789–792.
[14] S. Emura, Y. Haneda, S. Makino, Adaptive algorithm
enhancing decorrelated additive signals for stereo echo
cancellation, in: Proceedings of IWAENC2001, 2001, pp.
67–70.
[15] A.W.H. Khong, P.A. Naylor, Selective-tap adaptive algorithms in solution of the nonuniqueness problem forstereophonic acoustic echo cancellation, IEEE Signal
Process. Lett. 12 (4) (2005) 269–272.
[16] S. Haykin, Adaptive Filter Theory, third ed., Prentice-Hall,
New Jersey, 1995.
[17] B. Widrow, S.D. Stearns, Adaptive Signal Processing,second ed., Prentice-Hall, New Jersey, 1985.
[18] H.J. Butterweck, Traveling-Wave Model of Long LMS
Filters, Least-Mean-Square Algorithm, Wiley, New York,
2003, pp. 35–78.
[19] K. Ozeki, T. Umeda, An adaptive ﬁltering algorithm
using an orthogonal projection to an afﬁne subspace andits properties, Electron. Commun. Jpn. 67-A (5) (1984)
19–27.
[20] S.G. Sankaran, A.A. Beex, Convergence behavior of afﬁneprojection algorithms, IEEE Trans. Signal Process. 48 (4)(2000) 1086–1096.
[21] R.G. 167, Performance of acoustic echo control devices,
Technical Report, CCITT, Blue Book, ITU-TSS, 1992.
[22] P. Eneroth, T. Gänsler, S. Gay, J. Benesty, Studies of a
wideband stereophonic acoustic echo canceller, in: Proceedings of IWAENC99, 1999, pp. 207–210.
[23] M. Tanaka, Y. Kaneda, S. Makino, J. Kojima, Fast
projection algorithm and its step size control, in: Proceedings of ICASSP95, 1995, pp. 945–948.
[24] M. Tanaka, Y. Kaneda, S. Makino, J. Kojima, A fast
projection algorithm for adaptive ﬁltering, IEICE Trans.
Fundamentals E78-A (10) (1995) 1355–1361.