ADAPTIVE FILTERING ALGORITHM ENHANCING DECORRELATED ADDITIVE
SIGNALS FOR STEREO ECHO CANCELLATION
Satoru Emura*

Yoichi Haneda*

Shoji Makino***NTT Cyber Space Laboratories**NTT Communication Science Laboratories
3-9-11, Midori-cho, Musashino-shi, Tokyo 180-8585, Japan 2-4, Hikaridai, Seika-cho, Kyoto, 619-0237, Japanemura.satoru@lab.ntt.co.jp haneda.yoichi@lab.ntt.co.jp maki@cslab.kecl.ntt.co.jp
ABSTRACTThe strong inter-channel cross correlation between
stereo received signals creates a problem of non-uniquesolutions for stereo echo cancellation. To avoid thisproblem, the addition of inaudible non-linearly filteredreceived signals to themselves was proposed. However, theconvergence of misalignment is still slow even when theaffine projection algorithm is used, since strong
inter-channel cross correlation remains in the adjustment
vector. We propose an enhanced affine projection
algorithm in which the adjustment vector is welldecorrelated by enhancing non-linearly filtered received
signals. Computer simulation demonstrated that theenhanced affine projection algorithm can decrease
misalignment much faster than the conventional affine
projection algorithm.
1. INTRODUCTION
In a stereo teleconferencing system, a stereo acoustic
echo cancellation is required to reduce echoes that result
from coupling between loudspeakers and microphones.
Since stereo received signals usually come from theindividual speaker via two acoustic paths, inter-channel
cross correlation is strong. This causes the problem of
non-unique solutions to the normal equation for estimating
unknown echo paths. Misalignment between the estimatedand actual impulse responses usually remains even if
echoes are cancelled [1].
The addition of non-linearly filtered received signals tothe original received signals [2], [3] has been proposed to
avoid this non-uniqueness problem. Such a non-linear
filtering approach must have no audible effects and musthave no effect on stereo perception.
Since the amount of non-linearity is restricted, theconvergence of misalignment is slow when the NLMS
algorithm is used. The affine projection algorithm [2] andthe combination of inter-channel decorrelation and affine
projection [4] have been proposed to improve theconvergence speed. However, strong inter-channel crosscorrelation still remains in the adjustment vector. The
improvement in convergence speed is thus insufficient [5].
We propose an enhanced affine projection algorithm that
improves the convergence of misalignment with theadjustment vector decorrelated by enhancing non-linearly
filtered received signals.

f2

u2 (k )x2 (k )

f1

x1(k)

u1(k)

hˆ 1 (k) hˆ 2 (k)h1Speaker

h2

+ +
－
e(k )

y(k)

+
Transmission room

Receiving room

Fig. 1 Diagram of system for stereo echo cancellation.
2.

CONFIGURATION FOR STEREO ECHOCANCELLATION

Figure 1 shows a diagram of a typical system for stereo
echo cancellation. Stereo signals u1 ( k ) and u2 (k ) , picked
up by two microphones in the transmission room, aretransformed as

x1 (k ) = u1 (k ) + f1[ u1 (k ) ] ,(1)x2 (k ) = u2 (k ) + f 2 [ u2 (k ) ] ,where f1[·] and f 2 [·] are non-linear functions used to
avoid the non-uniqueness problem [3]. We hereafter referto f1[u1 (k ) ] and f 2 [u 2 (k ) ] as additive signals.
The echo signal y (k ) is expressed as(2)y ( k ) = hT x( k ) ,where h = [ h1T h T2 ]T is the concatenation of true impulse
response vectors h 1 and h 2 , and x(k ) is the input signal
vector defined asé x (k ) ù é u (k ) ù éu (k ) ùx( k ) = ê 1 ú = ê 1 ú + ê f 1 ú ,ëx 2 ( k )û ëu 2 (k )û ëu f 2 ( k ) ûu i ( k ) = [ ui ( k ) L ui (k - L + 1) ] (i = 1, 2) ,Tu f i ( k ) = [ f i [ui ( k )] L f i [ui ( k - L + 1) ] ] (i = 1, 2),T

where L is the length of impulse response vectors. The
error e(k ) is expressed as(3)e( k ) = y ( k ) - hˆ T ( k ) x(k ) ,where hˆ (k ) = [ hˆ T (k ) hˆ T (k ) ]T is the concatenation of12adaptive-filter-coefficient vector hˆ 1 (k ) and hˆ 2 ( k ) .

Shimauchi et al. [2] proposed updating of the adaptive
filter coefficients by the p-th order affine projection
algorithm ashˆ ( k + 1) = hˆ ( k ) + m Dhˆ ( k ),Dhˆ ( k ) = X( k ) [ XT (k ) X( k ) + d I ]-1 e(k ),(4)e( k ) = [ y (k ) L y ( k - p + 1)] - X ( k ) hˆ (k ),X( k ) = [ x( k ) L x(k - p + 1) ],T

Twhere m is the step-size and δ is a small positive
constant. We hereafter refer to ,hˆ (k ) as the adjustment
vector.
The adjustment vector can be treated as the sum of two
components, a component that is effective for convergence
and a redundant component. The p-th order affine
projection algorithm tries to reduce the redundantcomponent by removing the correlation between theconsecutive input signal vectors x ( k ), L , x ( k - p + 1) . The
achievement of faster convergence by using a moredecorrelated adjustment vector with a higher-orderprojection has been reported [2].
Benesty et al. [4] pointed out that, after the above
straightforward affine projection, the adjustment vector
still contains the redundant component caused byinter-channel cross correlation, that is, the correlation
between x1 ( k ) and x 2 ( k ) in input signal vector x(k ) .
They proposed the introduction of inter-channel
decorrelation in the affine projection algorithm. They
added the constraints that the adjustment weight of eachchannel must be orthogonal to the input signal vectors of
the other channels. However, for the projection order p = 2,
these constraints more than triple the amount ofcomputation required, as compared with the NLMS
algorithm.
These multi-channel adaptive algorithms use a linear
combination of input signal vectors with high inter-channel
cross correlation as the adjustment vector. Even after
non-linear preprocessing, the inter-channel crosscorrelation remains in the adjustment vector when the
projection order is low. This limits the convergence speed.
3.

NEW ADAPTIVE ALGORITHM

We propose a new method of obtaining a welldecorrelated adjustment vector that has a low level ofcomputational complexity. It is obvious that the additive
signals f1[u1 ( k ) ] and f 2 [u 2 (k ) ] in Fig. 1 should bedesigned to have a much lower inter-channel crosscorrelation than the original input signals x1 (k ) andx2 (k ) [5]. Increasing the contribution of these decorrelated
additive signals in the adjustment vector should improvethe convergence speed. This is our basic idea.
In order to achieve this, we propose that the adjustment
vector be obtained as a linear combination of vectorsz (k ), L , z ( k - p + 1) , whereé u (k ) ù é u ( k ) ùz (k ) = a ê 1 ú + ê f 1 ú .
ëu 2 ( k ) û ëu f 2 ( k ) û(5)Here, a (0 < a < 1) is a pre-determined attenuation factor.
The enhanced affine projection algorithm determines theweights of the linear combination of z (k ), L , z ( k - p + 1)
by forcing the filter coefficient vector hˆ (k ) + Dhˆ (k ) tosatisfy the last p input-output relationships, as in theconventional affine projection algorithm. As a result, theproposed algorithm is represented byhˆ ( k + 1) = hˆ ( k ) + m Dhˆ ( k ),Dhˆ ( k ) = Z(k ) [ XT ( k ) Z( k ) + d I ]-1 e( k ),Te( k ) = [ y (k ) L y ( k - p + 1)] - XT ( k ) hˆ (k ),(6)

X( k ) = [ x( k ) L x(k - p + 1) ],Z( k ) = [ z (k ) L z ( k - p + 1) ],where m is the step-size and δ is a small positive
constant. The sound reproduced by loudspeakers after the
proposed algorithm has been applied is the same as for theconventional affine projection algorithm.
The amount of computation is almost the same for the
proposed algorithm as for the affine projection algorithm
because the vector z (k ) can be generated from signal
samples a ui (k ) + f i [u i (k )] (i = 1,2) and there is no needfor the vector calculation of (5) for each sample. Note that,with the projection order p = 2, the amount of computation
required to apply the proposed algorithm can be reduced to
be almost the same as is required to apply the NLMS
algorithm. This is achieved by the technique used in thefast affine projection algorithm [6].
４. CONVERGENCE ANALYSISThe first-order statistical behavior of the LMS algorithm[7] shows that the convergence speed of the coefficienterror hˆ ( k ) - h is primarily limited by the eigenvalue
spread of the correlation matrix of input signals, that is, theratio of the largest eigenvalue to the smallest eigenvalues.
A broad spread of eigenvalues is known to make theconvergence slow. In this section, we show that the same
analysis can explain the improvement achieved by the
proposed algorithm for the projection order p = 1 .
To make the analysis easier, we use white-noise signalsthat satisfyééu (k ) ùùE ê ê f 1 ú uTf 1 (k ) uTf 2 (k ) ú = q I ,u(k)ëë f 2 û
û

[

]

(7)

[
]
E [u (k )u (k )] = 0

E u f 1 (k )u1T (k ) = 0,f2

T2

as the additive signals.
We may rewrite the proposed algorithm in terms of thecoefficient error hˆ ( k ) - h by substituting(8)e(k ) = xT ( k ) h - xT (k ) hˆ ( k )into the update equation (6) and by subtracting h fromboth sides of (6). Taking the mathematical expectations
yields the following sample-by-sample transition formulafor the mean coefficient error [8],E[hˆ (k + 1) - h] = E[I - m P(k )] E[hˆ (k ) - h]P( k ) =z ( k ) xT ( k ),xT (k ) z(k )(9)where I is a 2 L ´ 2 L identity matrix. The correlation
matrix of stereo input signal is diagonalized by using
orthogonal matrix C as0ùél 2 Lé é u1 ( k ) ù T
ù
T
ú,
ê
O
C E êê
u1 (k ) u 2 (k ) ú C =ê 0ë ëu 2 (k )úû
û
l 1 úû
ël 2L ³L ³ l 1 ³ 0 ,
T

[

]

(10)

CT C = CCT = I,
So the matrix E[ P (k )] can be diagonalized asì él 2 L
0 ù éq0ù ü1ï
ú+ê O ú ï
CT E[P (k )] C = ía êOý
ú ê0gï ê 0
úï
q
l
1
ë
û
û
î ë
þ
T
T
g = a E u1 (k )u1 (k ) + u 2 (k )u 2 (k )

[

]

(11)

by convolving an input speech signal and transmission
paths measured in a conference room with a reverberation
time of 200 ms. The true echo paths were also measured ina conference room and were truncated to 700 taps. The
sampling frequency was 8 kHz. A white- noise signal with
40dB SNR was added to y (k ) as ambient noise. The
adaptive filter had 600 taps on each channel. Step-size mwas set to 0.5．We used
f1[u ] == (u + | u |)= (u - | u |), f 2 [u ] =
2
2

(12)

with = = 0.26 as non-linear functions [9].
We evaluated the performance of the adaptive filter interms of the misalignment defined by || h - hˆ ' ( k ) ||2 / || h || 2 ,where hˆ ' ( k ) was the filter coefficient vector of theadaptive filter expanded to the same size as h by padding
with zeros.
Figure 2 shows the behavior of misalignment for theconventional NLMS algorithm (the first-order affine
projection algorithm, p=1) (A) without and (B) withadditive signals, and for (C) the proposed enhanced affine
projection algorithm with p=1 and attenuation factor
a=0.06. In (A), the misalignment of the filter coefficient
vector decreased rapidly in the first 1s, but soon saturated
at about - 4.5 dB. When non-linear transformation wasapplied (B), the misalignment continued to decrease
slowly and reached around - 5.2 dB at t = 10 s. This could
be improved to –7.9 dB by the proposed enhanced affine
projection algorithm (C).
Figure 3 shows the behavior of misalignment for thesecond-order affine projection algorithm (p=2) (A) withoutand (B) with additive signals, (C) the second-order affine
projection algorithm with inter-channel decorrelation [4],and (D) the proposed enhanced affine projection algorithm+ E[uTf 1 (k )u f 1 (k ) + uTf 2 (k )u f 2 (k )].

5.

SIMULATION

We confirmed the validity of the proposed algorithm bycomputer simulation. The received signals were obtained

Misalignment [dB]0

When stereo input signals are correlated, the smallest
eigenvalue l 1 is almost 0 compared with the largest
eigenvalue l 2 L , and the eigenvalue spread of
E[ P ( k )] can be approximated by ( al 2 L + q) / q . This
relationship shows that the eigenvalue spread can be madenarrower by setting the attenuation factor a (0 < a < 1)small. This tendency is reflected in the matrix
E[I - m P (k )] , and improves the convergence speed of thecoefficient error. Finding the optimum attenuation factor isa problem for future work.
This discussion of convergence is not specific to thecase of two input channels, but is applicable to any numberof input channels.

A
-5

B
C
-10
0

2

4

6

8

10

t [s]
Fig. 2 Behavior of misalignment for the conventional NLMS
algorithm (the first-order affine projection algorithm) (A) withoutand (B) with additive signals, and (C) the proposed first-orderenhanced affine projection algorithm.

with p=2 and attenuation factor a=0.06.
In (A), the misalignment of the filter coefficient vector
decreased rapidly in the first 1s, but soon saturated atabout - 4.5 dB. When non-linear transformation wasapplied (B), the misalignment continued to decrease
slowly and reached around - 7.0 dB at t = 10 s. When thesecond-order affine projection was combined withinter-channel decorrelation, the misalignment reachedaround - 7.7 dB at t = 10 s. This could be improved to–14.2 dB by the proposed enhanced affine projection
algorithm (D).
Figure 4 shows the behavior of misalignment when thestereo received signals were speech signals made bysimulating two people speaking alternately.

Misalignment [dB]

0

A
-5

B

The second-order affine projection algorithm (p=2) withadditive signals (B) and the proposed enhanced affine
projection algorithm (p=2, a=0.06) (D) were used. We seethat the convergence of misalignment for the proposed
algorithm (D) was achieved more quickly than for thesecond-order affine projection algorithm (B).
The proposed enhanced affine projection algorithm can
improve the convergence speed drastically.
4.

CONCLUSION

We propose modifying the affine projection algorithm(including the NLMS algorithm) by enhancing additive
signals in the adjustment vector. Computer simulation
demonstrated that this method decreased the misalignmentof the adaptive filter for stereo echo cancellation much
faster than the conventional first- and second-order affine
projection algorithms, with almost the same amount ofcomputation as the NLMS algorithm. The mechanism forthis improvement was investigated by analyzing thefirst-order statistical behavior of the proposed algorithm
for the projection order p = 1.

C
-10

REFERENCES

D
-15
0

2

4

6

8

10

t [s]
Fig. 3 Behavior of misalignment for the conventional
second-order affine projection algorithm (A) without and (B)with additive signals, (C) the second-order affine projection
algorithm with inter-channel decorrelation, and (D) the proposed
second-order enhanced affine projection algorithm.

0

Misalignment [dB]speaker alternation
-5

B

-10
-15

D

-20

0

10

20

30
t [s]

40

50

60

Fig. 4 Behavior of misalignment for (B) the conventional
second-order affine projection algorithm with additive signalsand (D) the proposed second-order enhanced affine projection
algorithm.

[1] M. M. Sondhi, D. R. Morgan, and J. L. Hall, “Stereophonic
Acoustic Echo Cancellation – An Overview of theFundamental Problem,” IEEE Signal Processing Letters, vol.
2, no. 8, pp. 148-151 (1995).
[2] S. Shimauchi and S. Makino, “Stereo Projection Echo
Canceller with True Echo Path Estimation,” Proc.
ICASSP95, pp. 3059-3062 (1995).
[3] J. Benesty, D. R. Morgan, and M. M. Sondhi, “A Better
Understanding and an Improved Solution to the Problems of
Stereophonic Acoustic Echo Cancellation,” Proc. ICASSP97,
pp. 303-306 (1997).
[4] J. Benesty, P. Duhamel, and Y. Grenier, “A Multi-Channel
Affine Projection Algorithm with Applications toMulti-Channel Acoustic Echo Cancellation,” IEEE Signal
Processing Letters, vol. 3, no. 2, pp. 35-37 (1996).
[5] S. Shimauchi, Y. Haneda, S. Makino, and Y. Kaneda, “NewConfiguration for a Stereo Echo Canceller with Nonlinear
Pre-Processing,” Proc. ICASSP98, pp. 3685-3688 (1998).
[6] M. Tanaka, Y. Kaneda, S. Makino, and J. Kojima, “FastProjection Algorithm and Its Step Size Control,” Proc.
ICASSP95, pp. 945-948 (1995).
[7] B. Widrow and S. D. Stearns: Adaptive Signal Processing,second edition, pp. 316-331, 1985, Prentice-Hall, New
Jersey.
[8] M. Tarrab and A. Feuer, “Convergence and Performance
Analysis of the Normalized LMS Algorithm with
Uncorrelated Gaussian Data,” IEEE Trans. IT, vol. 34, no. 4,
pp. 680-691 (1988).
[9] P. Eneroth, T. Gaensler, S. Gay, and J. Benesty, “Studies of a
Wideband Stereophonic Acoustic Echo Canceller,” Proc.
IWAENC, pp. 207-210 (1999).