# Selective Partial Update Adaptive Filtering Algorithms for Block-Sparse System Identification

Authors: Dandan Wei; Qing Xu
Journal: Security and Communication Networks
 (2022)

---

## Abstract

The block-sparse normalized least mean square (BS-NLMS) algorithm which takes advantage of sparsity, successfully shows fast convergence in adaptive block-sparse system identification, adaptive control, and other industrial informatics applications. It is also attractive in acoustic processing where long impulse response, highly correlated and sparse echo path are encountered. However, the major drawback of BS-NLMS is largely computational complexity. This paper proposes a novel selective partial-update block-sparse normalized least mean square (SPU-BS-NLMS) algorithm. Compared with conventional BS-NLMS for block-sparse system identification, the proposed elective partial-update block-sparse NLMS algorithm takes partial-update blocks scheme which is determined by the smallest squared Euclidean-norm at each iteration instead of entire block coefficients to save computations. Computational complexity analysis is conducted to help researchers select appropriate parameters for practical realizations and applications. Computer simulations on acoustic echo cancellation are conducted to verify the results and the effectiveness of the proposed algorithm.


---

## Body

## 1. Introduction

System identification is frequently encountered in many applications such as acoustic echo cancellation (AEC) [1], interference suppression in industrial [2], and biomedical engineering [3]. In order to adapt to the time-varying characteristics of the statistical speech signal, the LMS algorithm or the normalized form is usually used to iteratively identify the unknown system [4]. In many scenarios, like network echo cancellation, the impulse responses are sparse which means most of the tap-weights are zero or small value, and there are few nonzero or large coefficients. There are several different kinds of sparse systems. The typical one such as TV transmission channels [5] is called a block-sparse system or a block-compressible system. Different from general impulse response sparse systems in which large coefficients are randomly distributed, the nonzero coefficients of block-sparse systems are composed of one or more clusters, and a cluster is a set of nonzero or large coefficients [6]. Multichannel input and multichannel output and satellite communication communications in confined spaces are a representative example of a multiclustering sparse system. Unlike multicluster-like sparse systems, the unit impulse response of acoustic echo channels is a single-cluster-like sparse system consisting of a long tail delay and an active part [7, 8].Considering the speech echo path is a representative single-clustering sparse system, there is only one gathering of non-zero coefficients [9]. Several methods based on this priori knowledge have been presented including the group-zero-attracting LMS (GZA-LMS) algorithm and its improved version, the sparsity constraint LMS algorithm [10], the block-sparse LMS (BS-LMS) algorithm [11] and its input normalization variant version, the BS-NLMS algorithm, the block-sparse proportionate normalized LMS (BS-PNLMS) [10], and the BS-IPNLMS [12]. Compared with traditional LMS algorithms, the BS-LMS algorithm inserts a group of zero attraction of adaptive tap-weights into the cost function. Then, the optimization of group zero attraction of adaptive tap-weights is introduced to the block-sparse proportionate NLMS. Motivated by this, the computation reduction of the BS-LMS algorithm per iteration will be discussed in this paper by partial updating. Partial update is an efficient technique to reduce computations. It is very attractive for practical realizations and applications in hardware and digital signal processors. The representative algorithms include the preupdate strategy and the continuous NLMS algorithm [13], the M-max NLMS [14] algorithm that does not require extra operations to determine the value of tap-weights, and the set-membership PU-NLMS algorithm [15] that adopts the nonfixed filter coefficient update strategy.In this paper, we will broadly categorized partial-updating adaptive algorithms into two classes based on different updating strategies as follows: first, various kinds of using certain data-dependent selection criteria adaptive algorithms were proposed to update the tap-weights, including the selective-block-update NLMS (SBU-NLMS) algorithm [16], the M-max NLMS algorithm (Max-NLMS) [17], the set-membership PU-NLMS algorithm [18]and its improved version, the L-norm-based algorithm [19]. These algorithms generally use the characteristics of unfixed updating strategies to achieve a faster convergence rate, like the BS-LMS and GZA-LMS. However, the drawback of certain data-dependent selection criteria adaptive algorithms is lower convergence rate for nonstationary signals because of data-dependent updating [18]. The second type is predetermined updating schemes adaptive algorithms [20], including the periodic LMS algorithm [21], the sequential PU LMS algorithm [22] which updates filter coefficients periodically, and a novel stochastic PU LMS (SPU-LMS) algorithm. These algorithms aim to lower the steady-state error of adaptive filters. However, the drawbacks of these algorithms are that they have to set many parameters. Furthermore, a novel variant of the S-LM algorithm was proposed to improve the robustness of this algorithm [23]. The sequential block LMS (SB-LMS) algorithm and its normalized version [23] for acoustic echo cancellation problems and the sequential block NLMS (SB-NLMS) algorithm [24] were proposed to speed up the convergence rate.We proposed a novel SPU-BS-NLMS algorithm. The work focuses on the loss of computational complexity by selective partial update of blocks which chooses the smallest squared-Euclidean-distance as an optimization criterion in this paper. The selection criterion can be divided into two classes. The first class can update the blocks of the tap-weights vector by using squared Euclidean norms. The second class of algorithms can use larger gradient vector components. The complexity reduction of the SPU-BS-NLMS algorithm is achieved by dividing the filter taps into blocks and iterating only one block at a time instead of all the filter taps. As an indispensable part of AEC, the voice activity detection (VAD) algorithm technique of the speech signal distinguish the active/inactive speech periods will be utilized in this paper.In Section2, the BS-NLMS algorithm and voice activity detection technique are briefly reviewed. The proposed SPU-BS-NLMS algorithm and its computational complexity are derived and analyzed in Section 3. Computer simulations on acoustic echo cancellation in automobiles and tracking performance are conducted in Section 4. Notation: the notation .T is used for transpose, and E. for taking expectation.


## 2. BS-NLMS Algorithm and VAD

### 2.1. BS-NLMS Algorithm

The system to be identified of the acoustic echo cancellation system is shown in Figure1. Acoustic echo cancellation (AEC) aims to use the reference signal to cancel the echo in the microphone signal. The best goal of the echo cancellation algorithm is to achieve zero echo leakage and no distortion of the target speech. Of course, since noise is also unavoidable in the acoustic environment, it is sometimes necessary to take into account noise processing. The far-end user sends out a speech signal u=u1n,u2n,…,uLn. The speech signal passes through the unknown echo path to get the desired signal dn=unTs+vn, where L denotes the length of echo path, and vn denotes the additive background noise. The background noise is assumed to follow Gaussian distribution with zero mean. The core of echo cancellation is to use the LMS algorithm to find out w to model the echo path. w is the estimation of unknown system. The error signal en is expressed as(1)en=dn−unTwn.Figure 1
Block diagram for unknown system identification scenario.The smaller the error signal value is, the closer the estimated echo value is to the real echo. According to [12], the cost function of the least mean square algorithm can be expressed as ξn=Een2. Then, using the negative gradient steepest descent method of the mean square error based algorithm, namely, the well-known least mean square adaptive algorithm, is expressed as(2)wn+1=wn+μenun,where μ is the step size to adjust the balance between steady-state error and convergence speed of the adaptive algorithm. The low-order mixed L2,0 norm of vector w=w1n,w2n,…,wLnT is the zero attractive force exerted by improving the block-sparse characteristic of the echo channel. The expression is as follows:(3)w2,0=w12w22⋯wN20,where N is the number of groups of echo canceller orders, and wj=wj−1P+1,wj−1P+2,…,wjP denotes the jth group of w. P denotes the group partition and can always divide evenly L. According to [12], the cost function of BS-NLMS algorithm can be rewritten as follows:(4)ξn=Een2+λw2,0.This cost function is a quadratic convex function with respect to the tap coefficients, so there must be a globally unique minimum, and it is a positive factor. Then, using the negative gradient steepest descent method which is a similar derivation as that for NLMS, to obtain the coefficient update formula as follows:(5)wn+1=wn+μenun+κgwn,where gw is expressed as formula (6), κ=μ∗λ/2 is used to adjust the intensity of block-sparse penalty and is step size parameter.(6)gn≜g1n,g2n,…,gLnT,(7)giw=2α2wi−2αwiwi/p,0<wip≤1η;0,elsewhere.,where symbol ⌈•⌉ denotes ceiling function, and η is a positive constant. For practical realization, a particularly small positive number will be inserted into the denominator to avoid division by zero. According to the description of the BS-NLMS algorithm in the second part of the article, the computational complexity is O(L). In real applications, partial update provides an effective solution for saving computational complexity because the method only needs to update some parameters instead of all parameters at each iteration.


### 2.2. VAD Scheme

As an indispensable part of AEC, the voice activity detection (VAD) algorithm technique of the speech signal distinguish the active/inactive speech periods will be utilized in this paper. The voice activation detection algorithm extracts speech feature parameters and then needs to select specific decision criteria according to the application of the VAD detector to obtain the detection result. Since the third-order statistic of Gaussian noise is zero, for the speech signal whose environmental noise is Gaussian noise, there is a big difference between them. If a set of random signalu1,u2,…un is a real stationary discrete time signal, then r th-order joint cumulant is(8)Ck1…kn=−jrαrlnϕω1,ω2,…,ωn∂ω1k1∂ω2k2…∂ωnkn|ω1=ω2=…=ωn=0,where ϕω1,ω2,…,ωn=Eexpjω1u1+ω2u2+⋯+ωnun represents the k th-order moment function of the stationary signal. Then, the relationship between the moments τ and cumulant sequence are as follows:Second-order cumulant(9)C2uτ1=Eunun+τ1.Third-order cumulant(10)C3uτ1,τ2=Eunun+τ1un+τ2.Fourth-order cumulant(11)C4uτ1,τ2,τ3=Eunun+τ1un+τ2un+τ2−C2uτ1,C2uτ2−τ3−C2uτ2C2uτ3−τ1−C2uτ3C2uτ1−τ2.Furthermore, by letting inτ1=τ2=τ3=0, we obtain, respectively, the variance γ2u , skewness γ3u , and kurtosis γ4u as follows: variance γ2u=C2u0=Ey2n=σ2, skewness γ3u=C3u0,0=Ey3n, and kurtosis. γ4u=C4u0,0,0=Ey4n−3γ2u=Ey4n−3σ2.


## 2.1. BS-NLMS Algorithm

The system to be identified of the acoustic echo cancellation system is shown in Figure1. Acoustic echo cancellation (AEC) aims to use the reference signal to cancel the echo in the microphone signal. The best goal of the echo cancellation algorithm is to achieve zero echo leakage and no distortion of the target speech. Of course, since noise is also unavoidable in the acoustic environment, it is sometimes necessary to take into account noise processing. The far-end user sends out a speech signal u=u1n,u2n,…,uLn. The speech signal passes through the unknown echo path to get the desired signal dn=unTs+vn, where L denotes the length of echo path, and vn denotes the additive background noise. The background noise is assumed to follow Gaussian distribution with zero mean. The core of echo cancellation is to use the LMS algorithm to find out w to model the echo path. w is the estimation of unknown system. The error signal en is expressed as(1)en=dn−unTwn.Figure 1
Block diagram for unknown system identification scenario.The smaller the error signal value is, the closer the estimated echo value is to the real echo. According to [12], the cost function of the least mean square algorithm can be expressed as ξn=Een2. Then, using the negative gradient steepest descent method of the mean square error based algorithm, namely, the well-known least mean square adaptive algorithm, is expressed as(2)wn+1=wn+μenun,where μ is the step size to adjust the balance between steady-state error and convergence speed of the adaptive algorithm. The low-order mixed L2,0 norm of vector w=w1n,w2n,…,wLnT is the zero attractive force exerted by improving the block-sparse characteristic of the echo channel. The expression is as follows:(3)w2,0=w12w22⋯wN20,where N is the number of groups of echo canceller orders, and wj=wj−1P+1,wj−1P+2,…,wjP denotes the jth group of w. P denotes the group partition and can always divide evenly L. According to [12], the cost function of BS-NLMS algorithm can be rewritten as follows:(4)ξn=Een2+λw2,0.This cost function is a quadratic convex function with respect to the tap coefficients, so there must be a globally unique minimum, and it is a positive factor. Then, using the negative gradient steepest descent method which is a similar derivation as that for NLMS, to obtain the coefficient update formula as follows:(5)wn+1=wn+μenun+κgwn,where gw is expressed as formula (6), κ=μ∗λ/2 is used to adjust the intensity of block-sparse penalty and is step size parameter.(6)gn≜g1n,g2n,…,gLnT,(7)giw=2α2wi−2αwiwi/p,0<wip≤1η;0,elsewhere.,where symbol ⌈•⌉ denotes ceiling function, and η is a positive constant. For practical realization, a particularly small positive number will be inserted into the denominator to avoid division by zero. According to the description of the BS-NLMS algorithm in the second part of the article, the computational complexity is O(L). In real applications, partial update provides an effective solution for saving computational complexity because the method only needs to update some parameters instead of all parameters at each iteration.


## 2.2. VAD Scheme

As an indispensable part of AEC, the voice activity detection (VAD) algorithm technique of the speech signal distinguish the active/inactive speech periods will be utilized in this paper. The voice activation detection algorithm extracts speech feature parameters and then needs to select specific decision criteria according to the application of the VAD detector to obtain the detection result. Since the third-order statistic of Gaussian noise is zero, for the speech signal whose environmental noise is Gaussian noise, there is a big difference between them. If a set of random signalu1,u2,…un is a real stationary discrete time signal, then r th-order joint cumulant is(8)Ck1…kn=−jrαrlnϕω1,ω2,…,ωn∂ω1k1∂ω2k2…∂ωnkn|ω1=ω2=…=ωn=0,where ϕω1,ω2,…,ωn=Eexpjω1u1+ω2u2+⋯+ωnun represents the k th-order moment function of the stationary signal. Then, the relationship between the moments τ and cumulant sequence are as follows:Second-order cumulant(9)C2uτ1=Eunun+τ1.Third-order cumulant(10)C3uτ1,τ2=Eunun+τ1un+τ2.Fourth-order cumulant(11)C4uτ1,τ2,τ3=Eunun+τ1un+τ2un+τ2−C2uτ1,C2uτ2−τ3−C2uτ2C2uτ3−τ1−C2uτ3C2uτ1−τ2.Furthermore, by letting inτ1=τ2=τ3=0, we obtain, respectively, the variance γ2u , skewness γ3u , and kurtosis γ4u as follows: variance γ2u=C2u0=Ey2n=σ2, skewness γ3u=C3u0,0=Ey3n, and kurtosis. γ4u=C4u0,0,0=Ey4n−3γ2u=Ey4n−3σ2.


## 3. Proposed SPU-BS-NLMS Algorithm

The voice activation detection algorithm extracts speech feature parameters at first, and then needs to select specific decision criteria according to the application of the VAD detector to obtain the detection result. Since the third-order statistic of Gaussian noise is zero, for a speech signal whose environmental noise is Gaussian noise, there is a big difference between the third-order statistics of the signal frame and the noise frame, and it is easy to judge the speech segment and the noise segment. Therefore, the third-order statistic can be used to detect the activation of speech. The output result of the VAD algorithm is represented by a Boolean value. When it is judged as a speech frame, the result is “1”; when it is judged as background noise, the result is “0.” The fundamental partial-update scheme of the SPU-BS-NLMS algorithm is to update only some of the tap-weights per iteration instead of all by block selection criteria. It should be assumed thatP and C can always divide L because the BS-NLMS algorithm already consider the filter coefficients into equal group partition which is different from several tradition methods in literature. C denotes the partition number of filter blocks and B is the length of coefficient block. The coefficients vector and input signal vector can be expressed as follows:(12)un=u1Tn,u2Tn,…,uCTn,(13)wn=w1Tnw2Tn,…,wCTn,with(14)u1n=u1Tnu2Tn,…,uBTn,and(15)w1n=w1Tnw2Tn,…,wBTn.The posterior and prior error vectors areein+1=din−uinTwin+1 and ein=dnn−uinTwin, respectively. For a given updated block denoted i, the SPU-BS-NLMS algorithm is obtained by following optimisation criteria which is the minimized L2,0-norm of error vector with a constraint.(16)minwin+1−win2,0,(17)Subject todn=wTn+1un.Combining equations (13) and (14), the cost function of SPU-BS-NLMS can be derived by using the method of the Lagrange multiplier.(18)ξin+1=Een2−βwin+1−win2,0,where β is a Lagrange multiplier. The update formula is obtained by setting the partial derivative of the cost function to the weight vector equal to zero. The update equation is expressed as follows:(19)win+1=win+μenuiui2+δ+κgwin.In equation (13), the ith block is a prefixed block. However, it is unknown and required to be determined according to the data-dependent selection criteria. The approach is to seek a block which achieved minimized the Euclidean distance win+1−win2, thus resulting in the largest magnitude of input sample. Hereby, we can modify the selective block partial-update equation as follows:(20)wn+1=wn+Snμenuu2+δ+κgwn,where Sn=diagS1n,S2n,…,SCn. SinE0,1,i=1,2…C, is a diagonal selection matrix. It can be seen from equation (17) that, at time instant n, the value of Sin will be equal to one and corresponding block win in wn will be updated while other blocks keep the original value. And when Sn=I, which is an identity matrix, the proposed algorithm will be identical to the BS-NLMS algorithm. The voice activation detection algorithm extracts speech feature parameters at first, and then needs to select specific decision criteria according to the application of the VAD detector to obtain the detection result. Since the third-order statistic of Gaussian noise is zero, for the speech signal whose environmental noise is Gaussian noise, there is a big difference between the third-order statistics of a signal frame and the noise frame, and it is easy to judge the speech segment and the noise segment. Therefore, the third-order statistic can be used to detect the activation of speech. The output result of the VAD algorithm is represented by a Boolean value. When it is judged as a speech frame, the result is “1”; when it is judged as background noise, the result is “0.” In the SPU-BS-NLMS algorithm, wn is divided into C nonoverlapping blocks which are updated selectively. The elements of Sn are thus B=L/C equally spaced. Only one block with B tap-weights will be updated per iteration. The computational complexity are summarized in Table 1.Table 1
Complexities of the BS-NLMS and SPU-BS-NLMS algorithms.
AlgorithmBS-NLMSSPU-BS-NLMSMultiplication2L+6L+B+6Addition4L+22L+2B+2Division1+L/PL/P+1Square rootL/PL/PComparisonL/PL/P+BTable1 shows the computational complexity of BS-NLMS and proposed SPU-BS-NLMS algorithm at each iteration in terms of multiplication, addition, square root, and comparison. The BS-NLMS algorithm requires 2L+6 multiplications, 4L+2 additions, L/P+1 divisions, L/P comparisons, and L/P square roots for updating full filter coefficients per iteration. And the proposed algorithm requires an extra B comparisons for block selection compared with the BS-NLMS algorithm. However, the saving of L−B multiplications and 2L−2B additions will much exceed the additional complexity of B comparision operations for acoustic echo cancellation with large L. The procedure of SPU-PU-NLMS is described in Table 2.Table 2
The procedure of SPU-BS-NLMS.
input:xn,dn=1,2,3,…,L,P,μ,α,κ,δoutput:wnn=0,1,2,…Initialization:w0=0,N=L/P.forn=0,1,2,…en=dn−xnTwnfori=1,2,…,NEi=∑j=i−1P+1iPwj,n21/2Si=1,n+jmodC=00,othersizeend forforj=1,2,…,Lgjwn=2α2wj,n−2αwj.nmax1/Ej/p+δ,αwj,n+1=wj,n+Sj,nuenxn,j+1/Xn,y2+δ+kgjwnend forend for


## 4. Simulations

The unknown system to be identified is of lengthL=800 and a typical single-clustering of non-zero tap-weights which is randomly generated and located as shown in Figure 2. A zero-mean Gaussian random signal generates an input signal by through a first-order auto regressive (AR) model system Tz=1/1−0.7z. The system superimposes a zero-mean white noise with a Gaussian distribution and a value of 30 dB. The normalized misalignment learning curves are obtained to evaluate the tracking performance of the SPU-BS-NLMS algorithm. The step sizes were chosen as 0.5 for BS-NLMS and 0.6 for SPU-BS-NLMS to get approximately the same normalized mean square deviation after convergence. For the SPU-BS-NLMS algorithm, we set two parameters: C = 2 and C = 4.Implement simulation experiments to verify and compare normalized learning curves of BS-NLMS and SPU-BS-NLMS in Figure 3. It is clear from the figure that the SPU-BS-NLMS algorithm with C = 4 exhibits the slower convergence and the S PU-BS-NLMS algorithm with C = 2 converges quickly, whereas BS-NLMS obtains the best convergence performance. It can be seen that, when C = 1, the SPU-BS-NLMS is equal to the BS-NLMS algorithm. When C = 2 and C = 4, the algorithm loses some convergence speed with less computational load. The bigger the parmeters of an algorithm, the smaller the computational load and less convergence speed. Thus, the selection of the appropriate C value is mainly based on the trade-off between convergence performance and computational complexity according to specific requirements.The second experiment was conducted to test the proposed algorithm in acoustic echo cancellation in automobiles without double-talk. The experimental platform is the MATLAB environment under Windows. The corpus recording is carried out in an empty room with an area of about 20 m2. The equipment used for corpus acquisition includes a computer, a microphone, and a speaker. The computer is placed in the middle, and the speaker and the microphone are separated; on both sides and the distance between the two is about 0.45 m. The microphone records the far-end voice signal, which forms an echo through the echo channel, and is picked up by the microphone together with the near-end speech and ambient noise to become the desired signal. The sampling rate of the data is set at 8000 Hz, and the adaptive FIR filter order is set according to the truncated pulse of the actual room. Two algorithms, the BS-NLMS and the proposed algorithm are compared in simulation. Figure 4(a) calculated the skewness of echo signal and Figure 4(b) depicts echo signal with VAD decision value, which is plotted as dotted line. Additionally, the VAD value is obtained after multimedia smoothing to echo signal. The influence of the echo signal mixed with 10 dB white noise is shown in Figure 5. Figure 5(a) calculated the skewness of echo mixed with 10 dB white noise and Figure 5(b) depicts amplitude of echo mixed with 10 dB white noise and VAD decision value. Figure 6 plots the AEC output employing the SPU-BS-NLMS and the BS-NLMS algorithms. It can be clearly observed that there is only little difference between the two results. The two waveforms with different gray scales represent the two algorithms, respectively. It can be seen from the figure that the residual echo of the proposed SPU-BS-NLMS algorithm is less than that of the conventional algorithm. The residual echo can be observed from the amplitude values of the spectrogram of the time domain.Figure 2
A single cluster block-sparse system tested in experiments.Figure 3
Normalized learning curves of the BS-NLMS and SPU-BS-NLMS withC equal to 2.Figure 4
(a) Echo’s skewness. (b) Echo’s amplitude and VAD decision value.
(a)(b)Figure 5
(a) Skewness of echo mixed with 10 dB white noise. (b) Amplitude of echo mixed with 10 dB white noise and VAD decision value.
(a)(b)Figure 6
AEC outpute(n) SPU-BS-NLMS and BS-NLMS algorithms.


## 5. Conclusion

In this paper, a selective partial-update normalization adaptive filtering algorithm based on the BS-NLMS algorithm is proposed to reduce the computation complexity of block-sparse system identification in acoustic echo cancellation applications. In order to reduce computations, the selective block updating scheme of the smallest Euclidean distance is chosen to update filter tap-weights per iteration. Computational complexity is analyzed in detail. Additionally, simulation results show that the algorithm proposed in this paper performs better in tracking performance. Therefore, it can be potentially applied to many real implantations where simulation of unknown systems requires long adaptive transverse filters. However, the algorithm may converge unevenly when the black-sparse system needs to be identified under impulsive inference. Future work will be focused on developing black-sparse.



---

*Source: 2207115-2022-04-29.xml*