Low Complexity Adaptive Post-Whitening DCT-LMS for Echo Cancellation

In adaptive filtering, robust, simple, and computationally efficient algorithms such as the least mean square (LMS) are broadly used [1-5]. Nevertheless, their convergence performance is significantly affected when the input signal autocorrelation matrix is characterized by a significant spread of eigenvalues [6-9]. Several time-domain whitening techniques have been suggested in studies [10-13] to reduce such eigenvalue spreads. The time-domain whitening is achieved using the adaptive predictive decorrelation to decorrelate the input signal or jointly decorrelate the input signal with the error signal. This offers improvements in the behavior of the mean square error (MSE) convergence, which depends on the initial convergence speed and reached steady state [14-16].

The whitening of correlated input signals is also adopted in the transform-domain LMS (TDLMS) algorithm [17, 18], which is considered as a good alternative to the time-domain LMS algorithm. This whitening is achieved by exploiting the decorrelation property of orthogonal transforms such as the discrete cosine transform (DCT), discrete Fourier transform (DFT) and discrete Hartley transform (DHT). As a result, a significant reduction in the eigenvalue spread of the transformed and power-normalized autocorrelation matrix signal has been obtained, and the MSE convergence has then been improved. However, the performance of the existing TDLMS in terms of convergence is still limited due to the fact that the decorrelation capability of the transforms is limited [19].

To overcome this problem by reinforcing the decorrelation skills of the transforms, an efficient pre-whitening TDLMS (PW-TDLMS) algorithm has been designed in paper [19] by introducing at the input of the TDLMS a pre-whitening filter of first order. The role of this filter is to decrease the spread of the eigenvalues of the autocorrelation matrix corresponding to the resulting transformed and power normalized signal, and subsequently improve the MSE convergence performance. As demonstrated in paper [19], the PW-TDLMS adaptive noise canceller algorithm exhibits good performance in speech denoising applications, where the processed noise is employed mutually in filtering and adaptation steps. In order to reinforce the decorrelation ability of the employed orthogonal transforms and improve the MSE convergence of the TDLMS algorithm for the purpose of identifying systems, where the input signal characteristics needs to be kept unchanged during the filtering step and can only be altered during the adaptation step, a post-whitening TDLMS (POW-TDLMS) algorithm has been designed in paper [20]. This algorithm post-whitens the transformed signal and reduces the eigenvalue spread of the autocorrelation matrix of the post-whitened and power-normalized signal. Moreover, it has been shown in paper [20] that the MSE convergence of POW-DCT-LMS algorithm is superior to that of POW-DFT-LMS and POW-DHT-LMS algorithms. Additionally, past research has also shown that the DCT outperforms the DFT and DHT in a range of practical signal models [5, 18, 19, 21]. Although POW-DCT-LMS algorithm is very attractive for adaptive acoustic echo cancellation, it presents high arithmetic complexity primarily arising due to the necessity of computing two transforms during each iteration. This crucial limitation becomes extremely serious in real-time applications such as stereophonic and teleconferencing systems [22-24] and hence should be addressed.

In this paper, we develop a low-complexity POW-DCT-LMS (LC-POW-DCT-LMS) algorithm for adaptive acoustic echo cancellation by exploiting the fact that the adaptation process of the decorrelation coefficients slows down with relatively small values of the step size parameter. This leads to a new first-order adaptive post-whitening process allowing substantial reduction in the complexity and permitting our LC-POW-DCT-LMS algorithm to require for the calculation of one iteration only one transform.

The rest of this paper is organized as follows. Section 2 presents a brief review on the POW-DCT-LMS algorithm reported in paper [20]. In Section 3, we propose a LC-POW-DCT-LMS algorithm. The arithmetic complexity analysis of this algorithm is presented in Section 4 and its performance analysis is carried out in Section 5 in terms of eigenvalue spread, stability and performance measure. In Section 6, we apply our algorithm in the context of echo cancellation and perform a comparison with existing algorithms by considering both the normalized misalignment (MSI) and MSE convergence metrics. Some conclusions are included in Section 7.

The POW-DCT-LMS algorithm reviewed in Section 2 corresponds of post-whitening and adaptive filtering. The aim of this section is to design a low-complexity POW-DCT-LMS (LC-POW-DCT-LMS) algorithm by developing a low-complexity first order adaptive post-whitening. For this purpose, let us start by observing that the adaptation process of the decorrelation coefficients $a_k$ in (2) becomes slow when the step size parameter $\gamma$ takes relatively small values.

Assuming that the value taken by the adaptation step size $\gamma within the interval suggested in Section 2 is small enough to slowdown the process of adapting the decorrelation coefficients defined by (2).

Therefore, at each iteration $k$, the term $\gamma \tilde{x}_k x_{k-1}$ will not introduce a significant alteration to the values taken by $a_k$. Thus, we can assume that the values $\left(a_{k-1}, a_{k-2}, \ldots, a_{k-N}\right)$ taken over a finite duration $N$ are nearly equal.

With this assumption in mind, the vectors $\left[a_{k-1}, a_{k-2}, \ldots, a_{k-N}\right]^T$ and $\left[\bar{a}_k, \bar{a}_k, \ldots, \bar{a}_k\right]^T$ are asymptotically equal, where $\bar{a}_k$ is the mean value of the vector $\left[a_{k-1}, a_{k-2}, \ldots, a_{k-N}\right]^T$, i.e.

$\bar{a}_k=\frac{1}{N} \sum_{i=1}^N a_{k-i}$           (8)

By replacing the vector $\left[a_{k-1}, a_{k-2}, \ldots, a_{k-N}\right]^T$ in (1) by the approximated vector $\left[\bar{a}_k, \bar{a}_k, \ldots, \bar{a}_k\right]^T$, the post-whitening given by (1) can be rewritten as:

$\widetilde{\mathrm{X}}_k=\mathrm{X}_k-\mathrm{T}_N \times \operatorname{diag}\left(\bar{a}_k, \bar{a}_k, \ldots, \bar{a}_k\right) \times \mathrm{x}_{k-1}$           (9)

The term $\mathrm{T}_N \times \operatorname{diag}\left(\bar{a}_k, \bar{a}_k, \ldots, \bar{a}_k\right) \times \mathrm{x}_{k-1}$ can be rearranged as $\bar{a}_k \times \mathrm{T}_N \times \mathrm{x}_{k-1}$, and then, (9) becomes $\widetilde{\mathrm{X}}_k=$ $\mathrm{X}_k-\bar{a}_k \times \mathrm{T}_N \times \mathrm{x}_{k-1}$.

Consequently,

$\widetilde{\mathrm{X}}_k=\mathrm{X}_k-\bar{a}_k \times \mathrm{X}_{k-1}$           (10)

where, $\mathrm{X}_{k-1}=\mathrm{T}_N \times \mathrm{x}_{k-1}$.

Finally, a simplified form of the post-whitening process of is obtained in (10) and illustrated in Figure 2.

Now, we appropriately replace the post-whitening process of the POW-DCT-LMS algorithm, which is reviewed in Section 2, by the suggested post-whitening process obtained in Figure 2 to design the LC-POW-DCT-LMS algorithm illustrated in Figure 3.

2.png

Figure 2. Suggested low-complexity adaptive post-whitening

3.png

Figure 3. Suggested low-complexity adaptive post-whitening DCT-LMS algorithm

In this section, we analyze the eigenvalue spread, stability and performance measures of the LC-POW-DCT-LMS.

5.1 Eigenvalue spread analysis

As mentioned in Section 3, the value of the step size parameter  has a direct effect on the adaptation process of the decorrelation coefficients $a_k$ given by (2) and used in (8) to calculate the mean value $\bar{a}_k$ required in the new low complexity post-whitening given by (9).

In addition, the spread of the eigenvalues of the autocorrelation matrix $\tilde{S}_N$ obtained from the post-whitened signal and normalized by the power as $\widetilde{\mathrm{P}}_k^{-1} \widetilde{\mathrm{X}}_k$ has a significant influence on the convergence of the algorithm.

The autocorrelation matrix $\widetilde{\mathrm{B}}_N$ of $\widetilde{\mathrm{X}}_k$ after performing post whitening using the LC-POW process given by (10) can be computed as:

$\widetilde{\mathrm{B}}_N=E\left\{\widetilde{\mathrm{X}}_k \widetilde{\mathrm{X}}_k^H\right\}$          (11)

where, ( )^H denotes the Hermitian transpose operation.

After transformation and power normalization, the autocorrelation matrix is obtained in studies [6, 19, 20] by rearranging the elements such that $\widetilde{\mathrm{X}}_k$ transforms its elements $\tilde{X}_k(i), i=0,1 \ldots, N-1$ into $\tilde{X}_k(i) / \sqrt{\text { Power of } \tilde{X}_k(i)}$, with the power of $\widetilde{X}_k(i)$ being placed on the main diagonal of $\widetilde{\mathrm{B}}_N$.

$\widetilde{\mathrm{S}}_N=\left(\operatorname{diag} \widetilde{\mathrm{B}}_N\right)^{-1 / 2} \widetilde{\mathrm{~B}}_N\left(\operatorname{diag} \widetilde{\mathrm{~B}}_N\right)^{-1 / 2}$          (12)

The eigenvalue spread of $\widetilde{\mathrm{S}}_N$ is computed numerically for $T_N$ being the DCT. Therefore, it is of great interest to find an interval for appropriate values of $\gamma$ ensuring a small eigenvalue spread.

We now analyze numerically, for the conventional DCTLMS, existing POW-DCT-LMS and new LC-POW-DCTLMS algorithms, the eigenvalue spread of the autocorrelation matrix $\widetilde{\mathrm{S}}_N$ for different values of $\gamma$ in the interval $[0,0.1]$, various correlation coefficient values ρ=0.9, 0.7, and 0.5, and filter length $N=16$. The results of this analysis are depicted in Figures 4-6.

It is clear from these figures that the DCT-LMS algorithm presents a worse performance, whereas the eigenvalue spreads obtained using the LC-POW-DCT-LMS algorithm are comparable to those of the POW-DCT-LMS with a slight increase in the case of relatively high values of . Therefore, the interval for appropriate values of  is $\gamma$ = ]0,0.002[.

4.png

Figure 4. Eigenvalue spreads of the DCT-LMS, POW-DCT-LMS and LC-POW-DCT-LMS for $\rho=0.9, N=16$ and different values of the step size $\gamma$

5.png

Figure 5. Eigenvalue spreads of the DCT-LMS, POW-DCT-LMS and LC-POW-DCT-LMS for $\rho=0.7, N=16$ and different values of the step size $\gamma$

6.png

Figure 6. Eigenvalue spreads of the DCT-LMS, POW-DCT-LMS and LC-POW-DCT-LMS for $\rho=0.5, N=16$ and different values of the step size $\gamma$

5.2 Stability analysis

Similarly, to the analysis conducted for the existing POW-DCT-LMS algorithm [20], we analyze in this section the mean convergence of our LC-POW-DCT-LMS algorithm.

It is obvious from (4) that normalizing the power by $\tilde{\mathrm{P}}_k^{-1}$ affects the step size parameter and enhances the MSE convergence, but complicates stability analysis. To simplify this, we perform on the post-whitened vector $\widetilde{\mathrm{X}}_k$ the power normalization by multiplying (4) by $\tilde{\mathrm{P}}_k^{1 / 2}$.

$\tilde{\mathrm{P}}_k^{1 / 2} \mathrm{w}_{k+1}=\widetilde{\mathrm{P}}_k^{1 / 2} \mathrm{w}_k+\mu e_k \tilde{\mathrm{P}}_k^{-1 / 2} \widetilde{\mathrm{X}}_k$         (13)

By assuming that $\widetilde{\mathrm{X}}_k$ is a stationary process with zero mean value, $\tilde{\mathrm{P}}_k{ }^{1 / 2} \approx \tilde{\mathrm{P}}_{k+1}{ }^{1 / 2}$. This allows (13) to be formulated as $\tilde{\mathrm{P}}_{k+1}^{1 / 2} \mathrm{w}_{k+1}=\tilde{\mathrm{P}}_k^{1 / 2} \mathrm{w}_k+\mu e_k \tilde{\mathrm{P}}_k^{-1 / 2} \widetilde{\mathrm{X}}_k$, and then becomes:

$\widehat{\mathrm{w}}_{k+1}=\widehat{\mathrm{w}}_k+\mu e_k \mathrm{~V}_k$         (14)

where, $\widehat{\mathrm{w}}_k=\tilde{\mathrm{P}}_k^{1 / 2} \mathrm{w}_k$ and $\mathrm{V}_k=\tilde{\mathrm{P}}_k^{-1 / 2} \widetilde{\mathrm{X}}_k$.

In stationary or mildly non-stationary environments, the weight vector $\hat{\mathrm{w}}_k$ from (14) converges to $\tilde{\mathrm{P}}^{1 / 2} \mathrm{~T}_N \mathrm{~W}^0$, where $\tilde{\mathrm{P}}=\mathrm{E}\left\{\tilde{\mathrm{P}}_k\right\}$. This implies that (4) and (14) are equivalent forms.

We now subtract the quantity $\tilde{\mathrm{P}}^{1 / 2} \mathrm{~T}_N \mathrm{~W}^o$, obtained by transforming and normalizing Wiener filter, from (14), and then reformulate the result as:

$\widetilde{\mathrm{w}}_{k+1}=\widetilde{\mathrm{w}}_k+\mu e_k \mathrm{~V}_k$         (15)

where, $\widetilde{\mathrm{w}}_k=\widehat{\mathrm{w}}_k-\widetilde{\mathrm{P}}^{1 / 2} \mathrm{~T}_N \mathrm{~W}^o$ representing the weight-error vector.

By assuming the convergence of the decorrelation filter defined by (2) and (3), the decorrelation coefficients $a_k$ converge to the optimal scalar coefficient $a^o$ belonging to the range ]0, 1[. Hence, (8) becomes:

$\bar{a}_k=\frac{1}{N} \sum_{i=1}^N a^o=a^o,$         (16)

The approximated vector $\left[\bar{a}_k, \bar{a}_k, \ldots, \bar{a}_k\right]^T$ of length $N$ tends to $\left[a^o, a^o, \ldots, a^o\right]^T$, and (10), which corresponds to the low complexity post whitening, reduces to:

$\widetilde{\mathrm{X}}_k=\mathrm{X}_k-a^o \mathrm{X}_{k-1}$         (17)

The expression for $e_k$ in terms of $\widetilde{\mathrm{X}}_k$ is given by [20]:

$e_k=d_k-\left(\mathrm{w}_k\right)^H\left(\alpha \widetilde{\mathrm{X}}_k-\varphi w_k\right)$         (18)

where, $w_k=T_N \times \omega_k$ and $\omega_k=\left[\omega_k, \omega_{k-1}, \ldots, \omega_{k-N+1}\right]^T$ is zeros mean white gaussian noise. $\alpha=\frac{\rho}{\rho-a^0}, \varphi=\frac{a}{\rho-a^0}, 0<\rho<1, \rho$ is the correlation coefficient and $a^o \neq \rho$, and the expression of the obtained $e_k$ given by (18) in terms of $\widetilde{\mathrm{w}}_k$ and $\mathrm{V}_k$ is:

$e_k=e^o-\left(\alpha \mathrm{V}_k-\varphi \widetilde{\mathrm{P}}_k^{-1 / 2} w_k\right)^H \widetilde{\mathrm{w}}_k$         (19)

where, $e^o=d_k-\left(\alpha \mathrm{V}_k-\varphi \tilde{\mathrm{P}}_k^{-1 / 2} w_k\right)^H \tilde{\mathrm{P}}^{1 / 2} \mathrm{~T}_{N \mathrm{~W}^o}$ representing the error when the filter is optimum.

The substitution of (19) in (15) leads to:

$\begin{gathered}

\widetilde{\mathrm{w}}_{k+1}=\widetilde{\mathrm{w}}_k+ 

\mu\left[\mathrm{V}_k e^o-\left(\alpha \mathrm{V}_k\left(\mathrm{~V}_k\right)^H-\varphi \mathrm{V}_k\left(w_k\right)^H \tilde{\mathrm{P}}_k^{-1 / 2}\right) \widetilde{\mathrm{w}}_k\right]

\end{gathered}$         (20)

At time $k$, it is assumed that there is independence between the coefficients of $\widetilde{\mathrm{w}}_k, \mathrm{~V}_k, w_k$, and $\tilde{\mathrm{P}}_k{ }^{-1 / 2}$, which is justified by considering small values of $\mu$. The computation of the expectation of (20), leads to:

$\mathrm{E}\left\{\widetilde{\mathrm{w}}_{k+1}\right\}=\left[\mathrm{I}-\mu \alpha \tilde{\mathrm{S}}_N\right] \mathrm{E}\left\{\widetilde{\mathrm{w}}_k\right\}+\mu \varphi \mathrm{E}\left\{\mathrm{~V}_k\left(\mathrm{w}_k\right)^H \tilde{\mathrm{P}}_k^{-1 / 2}\right\} \mathrm{E}\left\{\widetilde{\mathrm{w}}_k\right\}$         (21)

where, $\mathrm{E}\left\{\mathrm{V}_k e^{\circ}\right\}=0$, and $\tilde{\mathrm{S}}_N=E\left\{\mathrm{~V}_k\left(\mathrm{~V}_k\right)^H\right\}$.

By assuming that the algorithm is convergent, (21) becomes:

$\mathrm{E}\left\{\widetilde{\mathrm{w}}_{k+1}\right\}=\left[\mathrm{I}-\mu \widetilde{\mathrm{S}}_N\right] \mathrm{E}\left\{\widetilde{\mathrm{w}}_k\right\}$         (22)

From (22), it is clear that the equivalent forms of (4) and (14) are stabilized in the mean-square sense under the resulting necessary condition.

$\left|1-\mu 3 \operatorname{tr}\left\{\tilde{\mathrm{~S}}_N\right\}\right|<1$         (23)

Therefore, we are able to express:

$0<\mu<\frac{2}{3 \operatorname{tr}\left\{\tilde{\mathrm{~S}}_N\right\}}$         (24)

where, $\operatorname{tr}(\cdot)$ denotes the trace of matrix and

$\operatorname{tr}\left\{\tilde{\mathrm{S}}_N\right\}=N$         (25)

Consequently, the stability criterion (24) becomes:

$0<\mu<\frac{2}{3 N}$         (26)

where, $N$ is the length of the filter.

Therefore, the stability condition of the LC-POW-DCT-LMS algorithm is similar to the stability conditions of the existing POW-DCT-LMS and conventional DCT-LMS algorithm.

5.3 Performance measure

The performance assessment of different algorithms is conducted in decibel (dB), utilizing different performance metrics, namely: the MSE, the normalized misalignment (MSI), the steady state MSE also known as the excess MSE (EMSE) and the steady-state excess MSE ($\operatorname{EMSE}_{s s}$).

At each time sample $k$, the ${MSE}_k$ is defined as:

$\operatorname{MSE}_k(d B)=10 \times \ Log _{10}\left(E\left\{e_k^2\right\}\right)$         (27)

Here, $e_k$ represents the error measured at the time sample k.

The normalized misalignment ${MSI}_k$ is defined as:

$\operatorname{MSI}_k(d B)=20 \times \ L og _{10} \left(\frac{\left\|\mathrm{w}_k-\mathrm{h}\right\|_2}{\|\mathrm{~h}\|_2}\right)$         (28)

where, $w_k$ is the weight vector estimated at the time sample $k$, $h$ is the echo channel impulse response and $\|\cdot\|_2$ refers to the $\ell_2 $ norm.

The $\mathrm{EMSE}_k$ is defined as [19]:

$\operatorname{EMSE}_k=\frac{1}{M} \sum_{n=0}^{M-1}\left|e_{k-n}\right|^2$         (29)

$M$ denotes the number of samples utilized in estimating the $\mathrm{EMSE}_k$. The $\mathrm{EMSE}_{s s}$, which is determined by averaging the $\mathrm{EMSE}_k$ values after the algorithm reaches a steady state, and has the following definition [19]:

$\operatorname{EMSE}_{s s}=\left(\frac{1}{K-S}\right) \sum_{k=S}^{K-1} \mathrm{EMSE}_k$         (30)

with K representing the total number of samples and S is the number of samples that the algorithm needs to attain the steady-state.