Elsevier

Signal Processing

Volume 86, Issue 6, June 2006, Pages 1182-1192
Signal Processing

Adaptive algorithms for sparse echo cancellation

https://doi.org/10.1016/j.sigpro.2005.09.015Get rights and content

Abstract

The cancellation of echoes is a vital component of telephony networks. In some cases the echo response that must be identified by the echo canceller is sparse, as for example when telephony traffic is routed over networks with unknown delay such as packet-switched networks. The sparse nature of such a response causes standard adaptive algorithms including normalized LMS to perform poorly. This paper begins by providing a review of techniques that aim to give improved echo cancellation performance when the echo response is sparse. In addition, adaptive filters can also be designed to exploit sparseness in the input signal by using partial update procedures. This concept is discussed and the MMax procedure is reviewed. We proceed to present a new high performance sparse adaptive algorithm and provide comparative echo cancellation results to show the relative performance of the existing and new algorithms. Finally, an efficient low cost implementation of our new algorithm using partial update adaptation is presented and evaluated. This algorithm exploits both sparseness of the echo response and also sparseness of the input signal in order to achieve high performance without high computational cost.

Introduction

Adaptive system identification is a challenging problem especially when the system impulse response is sparse. In this paper, we consider an impulse response or input signal to be ‘sparse’ if a large fraction of its energy is concentrated in a small fraction of its duration. We refer to the degree of sparseness as a qualitative measure ranging from strongly dispersive to strongly sparse.

One of the important applications of adaptive system identification is the cancellation of echoes in telephony networks as depicted in Fig. 1 in which, for discrete-time index n, x(n) is the input signal, e(n) is the returned echo signal, hopt(n) is the echo path impulse response, h(n) is the adaptive filter's impulse response of length L and x(n)=[x(n),x(n-1),,x(n-L+1)]T is a vector of input samples. This application has been the subject of much research in recent years. The echo responses that must be identified by such an echo canceller can have sparse characteristics, for example, if echo arises from reflections at the hybrid transformer in telephony networks with unknown delay. The advent of packet-switched telephony has led to a need for the integration of older analog ‘plain old telephone systems’ (POTS) with modern IP or ATM packet-switch networks. Network gateway products address this need by facilitating the interconnection of various networks and providing appropriate echo cancellers. In such systems, the hybrid echo response will be subject to an unpredictable bulk delay because propagation delays in the network are unknown and depend on several factors including network loading, quality of service constraints and jitter-buffer configuration. The overall effect is therefore that an ‘active’ region associated with the true hybrid echo response will be located with an unknown delay within an overall response window that has to be sufficiently long to accommodate the worst case bulk delay. Fig. 2 shows an example of a sparse system with an overall response window of 128 ms duration with an active region containing a hybrid response of 12 ms duration. State-of-the-art network gateway echo cancellers are typically designed to cancel up to three independently delayed hybrid echo responses, each of up to 16 ms duration, within an overall window of 128 ms. Such multi-hybrid responses occur in multi-party conference calls. Although our main focus in this paper will be on the single hybrid case, many of the principles apply also to multi-hybrid responses. It has been shown [1] that direct application of normalized LMS (NLMS) [2] echo cancellation in the context of G.168 [3] testing gives unsatisfactory performance when the echo response is sparse. The causes of poor performance include (i) the requirement to adapt a relatively long filter, typically 128 ms corresponding to 1024 coefficients for narrow-band speech with a sampling frequency of 8 kHz, and (ii) the coefficient noise that will unavoidably occur during adaptation for the near-zero-valued coefficients in the inactive regions.

In hands-free telephones and desktop conferencing systems, control of echo due to acoustic coupling from the loudspeaker to the microphone is a key requirement [4]. The echo response due to the loudspeaker-room-microphone system can often be considered sparse because of the bulk delay corresponding to the direct path propagation delay from loudspeaker to microphone. Depending on the application, this direct path bulk delay may be predictable as in the case of a telephone handset, or unpredictable as in the case of a desktop conferencing system with physically separate loudspeakers and microphones. The length of the acoustic echo response in a typical teleconferencing room is in the region of 100 to 400 ms and hence adaptive filters employing 1024 taps or more are typically required in order to achieve adequate levels of echo cancellation [5]. The requirement for long adaptive filters together with the presence of near-zero-valued coefficients during the bulk delay region means that significant performance benefits can often be obtained by applying sparse echo cancellation methods to acoustic echo cancellation applications. Other examples which require the identification of sparse impulse responses include certain types of source localization and the control of feedback in sound reinforcement and hearing aid applications.

In addition to consideration of sparse echo responses, adaptive filters can also be designed to exploit sparseness in the input signal. This second type of sparseness can be usefully exploited when processing speech signals which can be considered to exhibit a degree of sparseness since many of the sample amplitudes are close to zero, for example during speech pauses and plosive phonemes. This is illustrated in Fig. 3 which shows, for a typical sentence of male speech analyzed using a frame duration of 128 ms, that 50% of the speech energy is contained within 16% of the frame duration. Partial update adaptive filters can be deployed to exploit this type of sparseness with the aim of reducing computational complexity. Since the magnitudes of tap-updates in LMS-based adaptive filters are proportional to the input sample magnitudes, the tap-updates for near-zero taps will be commensurately small and have little effect on reducing the error. By updating only those taps that will have the greatest effect in reducing the output error, the computations relating to the non-updated taps are saved. Early work on this topic appeared in [6] and subsequently the MMaxNLMS algorithm was reported in [7]. Several other approaches employing partial update adaptive filtering have been proposed including block-based methods [8] and multi-channel techniques [9].

Having now identified two types of sparseness—sparseness in the echo response and sparseness in the input signal—we will first discuss techniques designed to exploit them individually. In Section 2, we will review the technique of proportionate updating in adaptive filters and give examples of several algorithms from the literature; algorithms employing partial updating will be discussed in Section 3. Secondly, we will present a new modified technique for proportionate updating with improved performance in Section 4. Thirdly, we will combine the underlying concepts of proportionate updating and partial updating and, using our modified proportionate scheme, develop the efficient partial update improved proportionate NLMS algorithm (PIPNLMS). Comparative simulation results will be presented in Section 5 whereafter conclusions will be drawn.

Section snippets

Proportionate update adaptive filters

In gradient descent and stochastic gradient adaptive algorithms, an objective function is minimized iteratively by adjusting the parameter vector in the direction of the negative error-gradient, or its estimate. The magnitude of the adjustment is regulated by the step-size (or adaptive gain) parameter. The particular feature of proportionate updating is that the effective value of the step-size is determined for each coefficient in a manner dependent on the magnitude of the coefficient. The

Partial update adaptive filters

It can be advantageous from the point of view of computational complexity to employ adaptive filters that update only a selected subset of size M, out of a total of L, coefficients at each iteration. Various techniques have been proposed in the literature which differ in the criteria used for selecting coefficients for updating. A particularly effective technique is the MMaxNLMS algorithm [7] that updates only M coefficients for which the corresponding elements of the tap-input vector x(n) are

An improved IPNLMS algorithm with efficient partial update

Section 2 discussed the modification of stochastic gradient adaptive algorithms such that the effective adaptation step-size is proportional to the magnitude of each coefficient. This approach aims to improve the effectiveness of adaptive identification of sparse systems and leads to the PNLMS algorithm [10]. It has also been shown how pure proportionate updating can be improved upon by introducing an amount of non-proportionate updating so that, as in the resulting PNLMS++ and IPNLMS

Simulation results

The convergence rate of the above algorithms has been compared in an echo cancellation experiment in which the echo response is sparse as shown in Fig. 2. Convergence rate has been measured in terms of the normalized misalignment hopt-h(n)2/hopt2 where hopt are the coefficients of the true echo response. The first set of tests employed Gaussian distributed white noise input with 8 kHz sampling frequency and measurement noise was injected to give an SNR of 25 dB. The echo response, as shown in

Discussion and conclusions

The topic of sparse echo cancellation has been discussed, where a sequence is considered ‘sparse’ if a large fraction of its energy is concentrated in a small fraction of its duration. Two types of sparseness have been considered in the context of echo cancellation. Sparseness in the echo response occurs in network echo cancellation, particularly for packet-switched networks, and in acoustic echo cancellation, particularly when the direct acoustic path propagation causes significant bulk delay.

Acknowledgements

The authors wish to thank Jacob Benesty for his helpful discussions and advice during the preparation of this manuscript.

References (24)

  • J. Kivinen et al.

    Exponentiated gradient versus gradient descent for linear predictors

    Inform. Comput.

    (January 1997)
  • O. Tanrikulu, K. Dogancay, Selective-partial-update proportionate normalized least-mean-squares algorithm for network...
  • S. Haykin

    Adaptive Filter Theory

    (2002)
  • ITU-T, Digital Network Echo Cancellers. G.168, International Telecommunication Union, Series G: Transmission Systems...
  • C. Breining et al.

    Acoustic echo control. An application of very-high-order adaptive filters

    IEEE Signal Process. Mag.

    (July 1999)
  • A. Gilloire, Experiments with sub-band acoustic echo cancellers for teleconferencing, in: Proceedings of the IEEE...
  • S.C. Douglas

    Adaptive filters employing partial updates

    IEEE Trans. Circuits Systems II

    (March 1997)
  • T. Aboulnasr et al.

    Complexity reduction of the NLMS algorithm via selective coefficient update

    IEEE Trans. Signal Process.

    (May 1999)
  • K. Dogancay et al.

    Adaptive filtering algorithms with selective partial updates

    IEEE Trans. Circuits Systems II

    (August 2001)
  • A.W.H. Khong, P.A. Naylor, Reducing inter-channel coherence in stereophonic acoustic echo cancellation using partial...
  • D.L. Duttweiler

    Proportionate normalized least-mean-squares adaptation in echo cancelers

    IEEE Trans. Speech Audio Process.

    (September 2000)
  • J. Benesty et al.

    Advances in Network and Acoustic Echo Cancellation

    (2001)
  • Cited by (91)

    • Robust and sparsity-aware adaptive filters: A Review

      2021, Signal Processing
      Citation Excerpt :

      Further, NLMS algorithm suffers from slow convergence in sparse system identification [104]. Several sparsity-aware adaptive filters have been recently developed to overcome this limitation [103,354–358]. In many practical applications, the behavior of the signal will be complex either by design like communications or by convenience of representation like radar and sonar [407].

    • Acoustic noise reduction by new two-channel proportionate forward symmetric adaptive decorrelating algorithms in sparse systems

      2018, Applied Acoustics
      Citation Excerpt :

      In this section, we present the three proposed proportionate versions of two-channel forward normalized decorrelation algorithm. In all proposed algorithms presented in this paper, the adaptive step-sizes are calculated from the last estimate of the filter coefficients in an efficient way that the step-size is proportional to the size of the filter coefficients [28–31,34,35]. This is resulted to adjust the active coefficients faster than the non-active ones.

    View all citing articles on Scopus
    View full text