Adaptive algorithms for sparse echo cancellation
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, is the input signal, is the returned echo signal, is the echo path impulse response, is the adaptive filter's impulse response of length L and 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 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 where 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)
- 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...
Adaptive Filter Theory
(2002)- ITU-T, Digital Network Echo Cancellers. G.168, International Telecommunication Union, Series G: Transmission Systems...
- 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...
Adaptive filters employing partial updates
IEEE Trans. Circuits Systems II
(March 1997)- et al.
Complexity reduction of the NLMS algorithm via selective coefficient update
IEEE Trans. Signal Process.
(May 1999) - 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...
Proportionate normalized least-mean-squares adaptation in echo cancelers
IEEE Trans. Speech Audio Process.
Advances in Network and Acoustic Echo Cancellation
Cited by (91)
A two-gain NLMS algorithm for sparse system identification
2022, Signal ProcessingRobust and sparsity-aware adaptive filters: A Review
2021, Signal ProcessingCitation 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].
Complex-valued proportionate affine projection Versoria algorithms and their combined-step-size variants for sparse system identification under impulsive noises
2021, Digital Signal Processing: A Review JournalAcoustic noise reduction by new two-channel proportionate forward symmetric adaptive decorrelating algorithms in sparse systems
2018, Applied AcousticsCitation 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.
An adjusting-block based convex combination algorithm for identifying block-sparse system
2018, Signal ProcessingA family of gain-combined proportionate adaptive filtering algorithms for sparse system identification
2017, Digital Signal Processing: A Review Journal