A Computationally Efficient Semi-Blind Source Separation Approach for Nonlinear Echo Cancellation Based on an Element-Wise Iterative Source Steering

In telecommunications or teleconferencing, acoustic echo, which is formed by the coupling between loudspeakers and microphones, is detrimental to full-duplex communication. One widely used way to eliminate the detrimental echo effects is through acoustic echo cancellation in which adaptive filters, such as the normalized least mean square (NLMS), recursive least mean square (RLS) and Kalman filters [1, 2], are used to identify the acoustic impulse response (AIR) [3]. While they have been widely used, adaptive filters generally suffer from great performance degradation or even divergence during double-talk in which both the far-end and near-end speech are present [4, 5].

One way to improve acoustic echo cancellation (AEC) performance during double-talk is through adopting the principle used in blind source separation (BSS) [6, 7, 8, 9] to reformulate the AEC problem as one of semi-blind source separation (SBSS) [10, 11]. Several algorithms have been derived based on this SBSS framework, which have demonstrated promising performance [12, 13, 14]. However, those algorithms still suffer from a number of drawbacks. First, they are computationally very expensive, which makes them difficult to implement in embedded systems. A viable approach to reduce complexity is through using the so-called multiplicative transfer function model (MTF) [15] and performing echo cancellation in the short-time Fourier transform (STFT) domain [16, 17]. But this method increases the system latency as MTF requires the length of the analysis window to be longer than the effective part of AIR. Recently, the so-called convolutive transfer function (CTF) [18, 19, 20] model was applied to SBSS-AEC to achieve different compromise between the system latency and computational complexity [21, 22]. Second, the performance of SBSS-AEC suffers from significant degradation in the presence of loudspeaker nonlinearity, which happens often in small devices [23, 24]. One way to deal with this issue is through nonlinear AEC in which nonlinear expansion [25, 26, 27] is used to model the loudspeaker nonlinearity [28]. In [22], researchers proposed a framework which combines the CTF model and nonlinear expansion. An iterative projection (IP) [8] method is carried out to solve the corresponding optimization problem.

However, the IP-based algorithm still faces the challenge of computational complexity, as it requires to calculate the inverse of an auxiliary matrix. To circumvent this problem, we attempt in this work to reduce the complexity, thereby developing an element-wise source steering (EISS) algorithm, which is an extension of the work in [29, 30, 31]. Since no matrix inverse is required, the developed algorithm is computationally much more efficient and its complexity is one order of magnitude lower than that of the IP-based algorithm, yet its performance is as good as that of the IP-based algorithm.

Consider the full-duplex speech communication scenario where a microphone is used to pick up the sound signal from the near-end speaker and a loudspeaker is used to playback the signal from the far-end. The microphone output signal at time instant $t$, which is denoted as $y(t)$, can be written as

where $s(t)$ denotes the near-end speech signal, $v(t)=a(t)*f\left[x(t)\right]$ is the nonlinear acoustic echo, $a(t)$ denotes the acoustic impulse response from the loudspeaker to the microphone, $*$ represents the linear convolution, $f(\cdot)$ stands for the response of the loudspeaker, which includes both the linear and nonlinear effects, and $x(t)$ is the far-end signal, respectively. The problem of acoustic echo cancellation is to mitigate or eliminate the echo signal, i.e., $v(t)$, while preserving the near-end signal $s(t)$.

While they have been widely used in practical systems, adaptive filtering algorithms often suffer from great performance degradation in the presence of loundspeaker nonlinearity. One way to deal with loundspeaker nonlinear distortion is to approximate $f\left[x(t)\right]$ through a $P$th-order basis-generic expansion [26], i.e.,

where $\phi_{p}\left(\cdot\right)$ is the $p$-th order basis function and $c_{p}$ is the corresponding coefficient. For real-valued signal, the following expansion can be used,

Substituting (2) into (1) gives

where $a^{\prime}_{p}(t)=c_{p}a(t)$ denote the echo path of the $p$-th order expanded signal $\phi_{p}\left[x(t)\right]$.

To reduce the computational complexity, the MTF model is introduced, which requires the analysis window to be longer than the effective part of AIR, leading to larger system latency. To achieve proper compromise between the computational complexity and system latency, the CTF approximation is subsequently adopted. The signal model in (4) is then written in the STFT domain as

where $i$ and $j$ denote the frequency and time-frame indexes, $L$ is the length of the CTF filter, and $Y_{i,j}$, $A^{\prime}_{p,i,j}$, $X_{\phi,p,i,j}$, $S_{i,j}$ denote, respectively, the STFTs of $y(t)$, $a^{\prime}_{p}(t)$, $\phi_{p}\left[x(t)\right]$ and $s(t)$. Putting (5) into a vector/matrix form gives

where

the superscript $T$ denotes the transpose operation, and $\mathbf{I}_{PL}$ denotes the identity matrix of size $PL\times PL$. Note that the $\tilde{\mathbf{H}}_{i,j}$ matrix is of size $(PL+1)\times(PL+1)$, which is called the mixing matrix in the literature of BSS, $\mathbf{0}_{PL\times 1}$ is a zero vector of length $PL$.

Following the notation in BSS and echo cancellation, we now define the demixing matrix $\tilde{\mathbf{W}}_{i,j}$ as

where $\mathbf{b}_{i,j}$ is a column vector with $PL$ parameters to be estimated. The near-end signal extraction filter can then be expressed as $\tilde{\mathbf{w}}_{i,j}^{H}=[1\quad\mathbf{b}_{i,j}^{T}]$. Applying the near-end signal extraction filter to the input signal gives the near-end signal, i.e.,

Given the aforementioned signal model and problem formulation, the objective of nonlinear SBSS-AEC is to estimate $\tilde{\mathbf{w}}_{i,j}$ by exploiting independence between the near-end and the reference signals.

In this section, we present the complexity of the IP and EISS algorithms in terms of the number of multiplications/divisions needed per frequency bin and time frame. For the IP algorithm, the complexity is dominated by computing the inverse of the covariance matrix $\mathbf{V}_{j}$, which has a complexity proportional to $\mathcal{O}(PL+1)^{3}$. The complexity for all the other computations is of $\mathcal{O}(PL+1)$. For regular setup, $\mathcal{O}(PL+1)$ is much smaller than $\mathcal{O}(PL+1)^{3}$. Therefore, the complexity of the IP method is

The EISS algorithm needs to estimate $PL+1$ coefficients. Computation of $u_{k,j},k\neq 1$ has a complexity of $\mathcal{O}\left[PL(PL+1)\right]$. The complexity for computing $u_{1,j}$ is $\mathcal{O}\left[(PL+1)^{2}\right]$ and it is $O(PL+1)$ for all the other operations. Similarly, if we only consider the operations that dominate the complexity, the overall complexity of EISS method is

which is one order lower than that of the IP method.

This paper investigated the problem of AEC in the presence of doubletalk and loudspeaker nonlinearity within reverberant environment. Following the framework of SBSS, we developed an element-wise source steering algorithm, which combines the CTF model and nonlinear expansion into the SBSS framework. Unlike the conventional IP-based SBSS method, which requires to compute the inverse of the auxiliary matrix, the proposed algorithm applies an element-wise update strategy, in which no matrix inverse is involved, and as a result, its computational complexity is one order of magnitude lower than that of the IP-based algorithm. Moreover, experiments showed that this efficient algorithm is able to achieve similar performance to that of the IP-based algorithm.