Introduction

In modern communication systems, such as hands-free telephony and audio teleconferencing, adaptive filtering plays an important role, particularly in applications like acoustic echo cancellation (AEC) and noise reduction (NR). Adaptive filtering adjusts filter coefficients in real-time, making it highly effective in non-stationary environments. Several reduced-complexity adaptive algorithms have been proposed in the literature, including partial update techniques [1], where only a subset of filter taps is updated during each iteration [1,2]. Set-membership algorithms have also been introduced as an alternative, utilizing specific time-update instances to reduce overall computational complexity (CC) [3,4]. A compromise between partial updating and set-membership NLMS algorithms has been proposed to further reduce CC [2,5,6]. Recently, a Set-Membership Fast NLMS [4] (SM-FNLMS) algorithm was developed. The FNLMS algorithm [7] uses the decorrelation properties to improve convergence speed by estimating the first forward predictor coefficient. When combined with the set-membership approach, this improves both computational complexity and convergence rate.

In this work, we develop a subband (SB) approach for the SM-FNLMS algorithm, where a setmembership adaptive filtering technique is applied in each subband. This approach offers two key advantages: subband filtering enhances the convergence rate, while incorporating set membership in each subband reduces the frequency updating which leads to reduce the computational complexity compared to the original SM-FNLMS algorithm [4]. The performance of the proposed algorithm is evaluated based on mean square error (MSE) and the overall computational complexity required in simulation time. The structure of this paper is as follows: Section 1 discusses the adaptive filtering problem. Section 2 introduces the NLMS, FNLMS [7], and SM-FNLMS [4] algorithms. In Section 3, we present the derivation of the proposed subband SM-FNLMS (SB-SM-FNLMS) algorithm. Simulation results, in terms of MSE and computational complexity, are provided in Section 4. Finally, Section 5 concludes the paper.

Adaptive Filtering

The principle of adaptive filtering is illustrated in Figure 1 It involves processing an input signal x(n) to generate, at each time instant, an output signal y(n) such that the difference between the desired response d(n) and the estimated response y(n) is minimized. This minimization is achieved by updating the coefficients (weights) of the adaptive filter w at time n, using the latest data set, which includes the desired signal d(n), the input signal x(n), and the a priori filtering error defined as follows:

𝑒(𝑛) = 𝑑(𝑛) − w 𝑇 (𝑛 − 1)x(𝑛)(1)

Here the input signal vector x(n) represents the M last simples of the input signal at instant n, and the filter vector w(n) represents the M adjusted coefficients at time instant n. These two vectors are defined as follows:

x(𝑛) = [︀ 𝑥(𝑛) 𝑥(𝑛 − 1) . . . 𝑥(𝑛 − 𝑀 − 1) ]︀ 𝑇(2)w(𝑛) = [︀ 𝑤 0 (𝑛) 𝑤 1 (𝑛) . . . 𝑤 𝑀 −1 (𝑛) ]︀ 𝑇(3)

In most common cases, the desired signal d(n), is correlated with the input signal x(n), as it is obtained using a linear transformation of the input signal (e.g., in cases of acoustic echo cancellation, adaptive filter identification, and adaptive noise cancellation). The adaptive algorithm iteratively minimizes the mean square error E[e(n)]at each time step, using the previous estimate of w(n-1) and the new correction term G(n)e(n).

w(𝑛 + 1) = w(𝑛) + G(𝑛)𝑒(𝑛)(4)

Where G(n) represents the adaptation gain.

Adaptive filtering algorithms

NLMS Algorithm

The adaptation gain G(n) can be computed in different ways by various algorithms. In the normalized least mean squares (NLMS) algorithm, it is calculated by minimizing the mean squared error (MSE) and is defined as:

G(𝑛) = 𝜇 NLMS x(𝑛)/x 𝑇 (𝑛)x(𝑛)(5)

Here, 𝜇_NLMS serves as the step size parameter, controlling the convergence behavior of the NLMS algorithm and is bounded by 0<𝜇_NLMS<2 . As a result, the adaptive filter's weights are updated through the recursive equation:

w(𝑛 + 1) = w(𝑛) + 𝜇 NLMS x(𝑛)𝑒(𝑛)/x 𝑇 (𝑛)x(𝑛)(6)

The NLMS algorithm has a computational complexity of 3M+1 multiplications and 1 division per iteration, making it feasible for implementation in real-time applications with limited computational resources. Algorithm 1 provides a summary of the NLMS algorithm.

Algorithm 1 NLMS Algorithm 𝑒(𝑛) = 𝑑(𝑛) − w 𝑇 (𝑛 − 1)x(𝑛) w(𝑛) = w(𝑛 − 1) + 𝜇 NLMS x 𝑇 (𝑛)x(𝑛)+𝛿 NLMS x(𝑛)𝑒(𝑛)

Where 𝛿 NLMS is a small constant to avoid division by zero.

FNLMS Algorithm

The Fast Recursive Least Squares (FRLS) Algorithm is an efficient alternative computational method to the Recursive Least Squares (RLS) algorithm. The FRLS algorithm minimizes the sum of squared errors with an exponential forgetting factor 𝜆 by calculating the dual Kalman gain k(n) of the RLS algorithm, introducing forward and backward predictor vectors a(n) and b(n),. In the FRLS algorithm, the adaptation vector is defined as follows:

𝐺(𝑛) = 𝛾(𝑛)𝑘(𝑛)(7)

where 𝛾(𝑛) is called the likelihood factor. This algorithm provides a high convergence speed rate compared to the NLMS algorithm. However, the CC of this algorithm remains high in comparison with that of NLMS.

A more recent approach, the fast-convergence NLMS (FNLMS) algorithm [7], further reduces computational complexity by simplifying the adaptation gain of the FRLS algorithm, achieving a computational cost similar to that of the NLMS algorithm while maintaining a convergence rate close to that of the FRLS algorithm. In the FNLMS algorithm, the adaptation gain is computed using the following recursive equation:

[︂ 𝑘(𝑛) 𝑘(𝑛) ]︂ = [︃ −𝑒 ¯(𝑛) 𝜆𝑝(𝑛−1)+𝑐 0 𝑘(𝑛 − 1) ]︃(8)

𝑐 0 is a small constant included to prevent division by zero. The forward prediction error 𝑒 ¯(𝑛) and its variance p(n) are calculated using the following equations:

𝑒 ¯(𝑛) = 𝑥(𝑛) + 𝑎(𝑛)𝑥(𝑛 − 1) (9) 𝑝(𝑛) = 𝜆𝑝(𝑛 − 1) + 𝑒 ¯2(𝑛)(10)

The predictor 𝑎(𝑛) is estimated by using the auto-correlation coefficients 𝑟 0 (𝑛) and 𝑟 1 (𝑛):

𝑎(𝑛) = 𝑟 1 (𝑛)/𝑟 0 (𝑛)(11)

these autocorrelation coefficients are recursively updated as follows:

𝑟 0 (𝑛) = 𝜆 𝑎 𝑟 0 (𝑛 − 1) + 𝑥(𝑛)𝑥(𝑛) (12) 𝑟 1 (𝑛) = 𝜆 𝑎 𝑟 1 (𝑛 − 1) + 𝑥(𝑛)𝑥(𝑛 − 1)(13)

Where 𝜆 𝑎 is the forgetting factor. The conversion factor 𝛾(𝑛) is updated using the following recursive equation:

𝛾(𝑛) = 𝛾(𝑛 − 1) 1 + 𝛾(𝑛 − 1) + 𝛽(𝑛)(14)

Where 𝛽(𝑛) is computed as follows:

𝛽(𝑛) = 𝑘(𝑛)𝑥(𝑛 − 𝑀 ) + 𝑥(𝑛)𝑒 ¯(𝑛) 1 + 𝜆𝑝(𝑛 − 1) + 𝑐 0 (15)

The NLMS algorithm is summarized in algorithm 2:

Algorithm 2 FNLMS algorithm 𝑘(0) = 0, 𝛾(0) = 1, 𝑟 1 (0) = 0, 𝑟 0 (0) = 1, 𝑝(0) = 1 0.9 < 𝜆 < 1, 0.9 < 𝜆 𝑎 < 1, 𝑐 𝑎 = 𝑐 0 (small constant) 𝑟 0 (𝑛) = 𝜆 𝑎 𝑟 0 (𝑛 − 1) + 𝑥(𝑛)𝑥(𝑛) 𝑟 1 (𝑛) = 𝜆 𝑎 𝑟 1 (𝑛 − 1) + 𝑥(𝑛)𝑥(𝑛 − 1) 𝑎(𝑛) = 𝑟 1 (𝑛) 𝑟 0 (𝑛)+𝑐𝑎 𝑒 ¯(𝑛) = 𝑥(𝑛) + 𝑎(𝑛)𝑥(𝑛 − 1) 𝑝(𝑛) = 𝜆𝑝(𝑛 − 1) + 𝑒 ¯2(𝑛) [︂ 𝑘(𝑛) 𝑘(𝑛) ]︂ = [︃ −𝑒 ¯(𝑛) 𝜆𝑝(𝑛−1)+𝑐 0 𝑘(𝑛 − 1) ]︃ 𝛽(𝑛) = 𝑘(𝑛)𝑥(𝑛 − 𝑀 ) + 𝑥(𝑛)𝑒 ¯(𝑛) 1+𝜆𝑝(𝑛−1)+𝑐 0 𝛾(𝑛) = 𝛾(𝑛−1) 1+𝛾(𝑛−1)+𝛽(𝑛)

Filtering: 𝑒(𝑛) = 𝑑(𝑛) − w 𝑇 (𝑛 − 1)𝑥(𝑛) w(𝑛) = w(𝑛 − 1) − 𝜇 FNLMS 𝛾(𝑛)𝑘(𝑛)𝑒(𝑛)

Set-Membership FNLMS (SM-FNLMS) algorithm

The main strategy of the SM-FNLMS algorithm is to conduct a verification step that checks whether the prior estimate vector w(𝑛 − 1) falls outside the constraint set Ψ. This set includes all vectors w for which the corresponding output error 𝑒(𝑛) at time 𝑛 remains within a specified upper limit, denoted by 𝜁:

Ψ = {︀ w ∈ R 𝑀 : |𝑑(𝑛) − w 𝑇 x(𝑛)| < 𝜁 }︀(16)

A recursive algorithm with a priori error 𝑒(𝑛) testing can be used to converge the filter w(𝑛) to the set of filter solutions defined by equation ( 16). The recursive updating equation is given below:

w(𝑛) = w(𝑛 − 1) − 𝜇(𝑛)𝛾(𝑛)𝑘(𝑛)𝑒(𝑛)(17)

Where:

𝜇(𝑛) = {︃ 1 − 𝜁 |𝑒(𝑛)| if |𝑒(𝑛)| > 𝜁 0 otherwise(18)

Clearly, when |𝑒(𝑛)| ≤ 𝜁, the step-size value will be 𝜇(𝑛) = 0, and consequently, w(𝑛) = w(𝑛 − 1), resulting in no update of the filter. This provides a benefit in terms of the computational complexity of the overall update time. Additionally, the SM-FNLMS algorithm employs a variable step-size, which can achieve good convergence with an optimal MSE steady-state. The SM-FNLMS algorithm is summarized in algorithm 3.

Algorithm 3 SM-FNLMS Algorithm

𝑘(0) = 0, 𝛾(0) = 1, 𝑟 1 (0) = 0, 𝑟 0 (0) = 1, 𝑝(0) = 1 0.9 < 𝜆 < 1, 0.9 < 𝜆 𝑎 < 1, 𝑐 𝑎 = 𝑐 0 (small constant)

𝑟 0 (𝑛) = 𝜆 𝑎 𝑟 0 (𝑛 − 1) + 𝑥(𝑛)𝑥(𝑛) 𝑟 1 (𝑛) = 𝜆 𝑎 𝑟 1 (𝑛 − 1) + 𝑥(𝑛)𝑥(𝑛 − 1) 𝑎(𝑛) = 𝑟 1 (𝑛) 𝑟 0 (𝑛)+𝑐𝑎 𝑒 ¯(𝑛) = 𝑥(𝑛) + 𝑎(𝑛)𝑥(𝑛 − 1) 𝑝(𝑛) = 𝜆𝑝(𝑛 − 1) + 𝑒 ¯2(𝑛) [︂ 𝑘(𝑛) 𝑘(𝑛) ]︂ = [︃ −𝑒 ¯(𝑛) 𝜆𝑝(𝑛−1)+𝑐 0 𝑘(𝑛 − 1) ]︃ 𝛽(𝑛) = 𝑘(𝑛)𝑥(𝑛 − 𝑀 ) + 𝑥(𝑛)𝑒 ¯(𝑛) 1+𝜆𝑝(𝑛−1)+𝑐 0 𝛾(𝑛) = 𝛾(𝑛−1) 1+𝛾(𝑛−1)+𝛽(𝑛) Filtering: 𝑒(𝑛) = 𝑑(𝑛) − w 𝑇 (𝑛 − 1)𝑥(𝑛) if |𝑒(𝑛)| > 𝜁 then 𝜇(𝑛) = 1 − 𝜁 |𝑒(𝑛)| w(𝑛) = w(𝑛 − 1) − 𝜇(𝑛)𝛾(𝑛)𝑘(𝑛)𝑒(𝑛) else w(𝑛) = w(𝑛 − 1) end if

Proposed Algorithm

Consider the critically subband adaptive filtering (𝐷 = 𝑁 ) given in Figure 11 [8]. Before filtering, the input signals 𝑥(𝑛) and 𝑑(𝑛) are analyzed using the analysis filters 𝐹 𝑗 to generate subband signals 𝑥 𝑖 (𝑛) and 𝑑 𝑖 (𝑛). The desired signals 𝑑 𝑖 (𝑛) and the output signals of the filter 𝑦 𝑖 (𝑛) are then decimated with a factor 𝐷, to provide low-time-rate signals 𝑑 𝑖 (𝑘) and 𝑦 𝑖 (𝑘), producing low-time-rate subband errors 𝑒 𝑗 (𝑘).

Note that the subband and decimated signals are referred to by the indices 𝑗 and 𝐷. In our algorithm, in each subband, we calculate the prediction parameters using the corresponding input subband signal 𝑥 𝑖 (𝑛), following the same strategy as the fullband FNLMS.

The proposed algorithm is based on subband set-membership, where the adaptive filters 𝑤(𝑘 + 1) belong to the set of filters Ψ:

𝑤(𝑘 + 1) ∈ Ψ (19)

The proposed algorithm uses subband adaptive updating, so we define the set of filters Ψ as the intersection of the sets of subband filters 𝜓 𝑗 , as follows:

Ψ = 𝜓 1 ∩ 𝜓 2 ∩ • • • ∩ 𝜓 𝑁 (20)

Each subband filter set 𝜓 𝑗 is defined in low sampling time 𝑘 as follows:

𝜓 𝑗 = {𝑤 ∈ R 𝑀 : |𝑑 𝐷,𝑗 (𝑘) − 𝑥 𝑇 𝑗 (𝑘)𝑤| < 𝜁} (21)

As with the full-band SM-FNLMS algorithm, we can converge the adaptive filter inside the set Ψ. However, here, 𝑁 conditions are imposed on the subband errors. The recursive updating equation is given by:

𝑤(𝑘) = 𝑤(𝑘 − 1) − 𝑁 ∑︁ 𝑗=1 𝜇 𝑗 (𝑘)𝛾 𝑗 (𝑘)𝑘 𝑗 (𝑘)𝑒 𝑗 (𝑘)(22)

where:

𝜇 𝑗 (𝑘) = {︃ 1 − 𝜁 |𝑒 𝑗 (𝑘)| , if |𝑒 𝑗 (𝑘)| > 𝜁 0, otherwise(23)𝑘 𝑗 (0) = 0, 𝛾 𝑗 (0) = 1, 𝑟 𝑗,1 (0) = 0, 𝑟 𝑗,0 (0) = 1, 𝑝 𝑗 (0) = 1 0.9 < 𝜆 < 1, 0.9 < 𝜆 𝑎 < 1, 𝑐 𝑎 = 𝑐 0 (small constant) 𝑟 𝑗,0 (𝑛) = 𝜆 𝑎 𝑟 𝑗,0 (𝑛 − 1) + 𝑥 𝑗 (𝑛)𝑥 𝑗 (𝑛) 𝑟 𝑗,1 (𝑛) = 𝜆 𝑎 𝑟 𝑗,1 (𝑛 − 1) + 𝑥 𝑗 (𝑛)𝑥 𝑗 (𝑛 − 1) 𝑎 𝑗 (𝑛) = 𝑟 𝑗,1 (𝑛) 𝑟 𝑗,0 (𝑛)+𝑐𝑎 𝑒 ¯𝑗(𝑛) = 𝑥 𝑗 (𝑛) + 𝑎 𝑗 (𝑛)𝑥 𝑗 (𝑛 − 1) 𝑝 𝑗 (𝑛) = 𝜆𝑝 𝑗 (𝑛 − 1) + 𝑒 ¯2 𝑗 (𝑛) [︂ 𝑘 𝑗 (𝑛) 𝑘 𝑗 (𝑛) ]︂ = [︃ −𝑒 ¯𝑗 (𝑛) 𝜆𝑝 𝑗 (𝑛−1)+𝑐 0 𝑘 𝑗 (𝑛 − 1) ]︃ 𝛽 𝑗 (𝑛) = 𝑘 𝑗 (𝑛)𝑥 𝑗 (𝑛 − 𝑀 ) + 𝑥 𝑗 (𝑛)𝑒 ¯𝑗 (𝑛) 𝜆𝑝 𝑗 (𝑛−1)+𝑐 0 𝛾 𝑗 (𝑛) = 𝛾 𝑗 (𝑛−1) 1+𝛾 𝑗 (𝑛−1)+𝛽 𝑗 (𝑛) Filtering: 𝑒 𝑗 (𝑘) = 𝑑 𝑗 (𝑘) − 𝑤(𝑘 − 1) 𝑇 𝑥 𝑗 (𝑘) if |𝑒 𝑗 (𝑘)| > 𝜁 then 𝜇 𝑗 (𝑘) = 1 − 𝜁 |𝑒 𝑗 (𝑘)| 𝑤 𝑗 (𝑘) = 𝑤 𝑗 (𝑘 − 1) − 𝜇 𝑗 (𝑘)𝛾 𝑗 (𝑘)𝑘 𝑗 (𝑘)𝑒 𝑗 (𝑘) else 𝑤 𝑗 (𝑘) = 𝑤 𝑗 (𝑘 − 1) end if

Simulation

In this section, we evaluate the performance of the proposed SB-SM-FNLMS algorithm in terms of convergence rate (MSE learning curve) and computational complexity (CC). The input signal is a colored autoregressive signal generated by an autoregressive model:

𝑥(𝑛) = −0.8650 𝑥(𝑛 − 1) − 0.8066 𝑥(𝑛 − 2) − 0.7703 𝑥(𝑛 − 3) + 𝑣(𝑛)(24)

Here, v(n) represents Gaussian white noise with variance 𝜎 2 𝑣 , adjusted to ensure 𝜎 2 𝑥 = 1. The desired signal is derived from filtering the input signal using an impulse response of 512 samples, as illustrated in Figure 3. To simulate various perturbations, white noise with a variance of 𝜎 2 𝜂 = 0.01 is added to the desired signal. The parameters of each algorithm are adjusted for optimal convergence rates, with step sizes set to 1. For set-membership algorithms (i.e. SM-NLMS, SM-FNLMS, and the proposed SB-SM-FNLMS), the error bound is defined as 𝜁 = √︁ 5𝜎 2 𝜂 = 0.223. This simulation aims to evaluate the behavior of the proposed algorithms in addressing the impulse response identification problem. The learning curve simulation involves calculating the segmental mean square error (Seg MSE), as described by the relation below:

SegMSE dB = 𝐵−1 ∑︁ 𝑖=0 10 log 10 [︀ 𝑒 2 (𝑛) ]︀ (25)

Where B is the block length, and in this simulation, B is set to 400 samples. To generate the subband input signals x_j (k) and subband desired signals d_j (k), we use analysis and synthesis FIR filters with 32 taps. The frequency responses of these filters for two subbands decompositions (N=2 and N=4) is shown in Figure 4.

Learning curve

In this experiment, we evaluate the performance of the proposed SB-SM-FNLMS algorithm in comparison with the NLMS, SM-NLMS, FNLMS, and SM-FNLMS algorithms using the SegMSE criterion. We consider 2, 3, and 4 subband decompositions with critical decimation for our proposed algorithm. The obtained results are shown in Figure 5. Based on this figure, we observe a higher convergence rate with the proposed algorithm compared to all other algorithms, especially for higher numbers of subband decompositions (N), which is due to the decorrelation introduced by subband decomposition. Additionally, a lower steady-state MSE is achieved by the proposed algorithm, which is due to the minimization of subband power errors, leading to a lower fullband power error.

Computational complexity

0 presents the computational complexity (CC) in terms of the number of multiplications and divisions required for one iteration of the four algorithms (i.e., NLMS, SM-NLMS, FNLMS, SM-FNLMS, and the proposed SB-SM-FNLMS algorithms). With critical decimation (D=N), the proposed algorithm requires 2M+12N+2 multiplication and 1+4N divisions per iteration, and for 𝑀 ≫ 𝑁 , the CC of the proposed algorithm is close to that of the SM-FNLMS algorithm. However, since the adaptive filter is updated based on the low time-rate k, the overall time CC of the proposed algorithm can be significantly lower than that of the SM-FNLMS. Figure 6 presents the ON/OFF updating filter at each time instant for our simulation. We set N=4, and the updating filter based on the proposed algorithm operates on four subbands with a low time rate.

As shown in Fig 6, the update frequency obtained by the proposed algorithm is less dense compared to the other algorithms. The total number of updates obtained for the learning curve in Figure 5 is provided in Table 2. Based on this Table, we observe that, the number of updates is approximately one-fifth that of the SM-FNLMS and SM-NLMS algorithms. This result demonstrates the superior performance of the proposed algorithm in terms of computational complexity (CC).

Conclusion

We have introduced in this work a new subband set-membership-based Fast Normalized Least Mean Square (SB-SM-FNLMS) algorithm. By incorporating subband filtering, the proposed algorithm improves both convergence rate and computational complexity (CC). Simulation results demonstrate its superior performances compared to the existing NLMS, SM-NLMS, FNLMS, and SM-FNLMS algorithms in term of convergence speed rate, final mean square error (MSE) and computational complexity (CC) , making it well-suited for practical adaptive filtering applications, including acoustic echo cancellation, adaptive noise reduction, etc.