A robust subband adaptive filter algorithm for sparse and block-sparse systems identification

ZAHRA Habibi ,HADI Zayyani ,and MOHAMMAD Shams Esfand Abadi

1.Research Institute for Information and Communications Technologies,Academic Center for Education,Culture and Research,Tehran 1599616313,Iran;2.Department of Electrical and Computer Engineering,Qom University of Technology,Qom 371951519,Iran;3.Faculty of Electrical Engineering,Shahid Rajaee Teacher Training University,Tehran 1678815811,Iran

Abstract: This paper presents a new subband adaptive filter(SAF) algorithm for system identification scenario under impulsive interference,named generalized continuous mixed p-norm SAF (GCMPN-SAF) algorithm.The proposed algorithm uses a GCMPN cost function to combat the impul-sive interference.To further accelerate the convergence rate in the sparse and the block-sparse system identification processes,the proportionate versions of the proposed algorithm,the L0 -norm GCMPN-SAF(L0 -GCMPN-SAF) and the block-sparse GCMPN-SAF (BSGCMPN-SAF) algorithms are also developed.Moreover,the convergence analysis of the proposed algorithm is provided.Simulation results show that the proposed algorithms have a better performance than some other state-of-the-art algorithms in the literature with respect to the convergence rate and the tracking capability.

Keywords:subband adaptive filter (SAF),generalized continuous mixed p-norm (GCMPN),sparse system,block-sparse system,impulsive interference.

1.Introduction

The least-mean-square (LMS) and the normalized LMS(NLMS) adaptive filtering algorithms have been widely used in various applications such as system identification,channel equalization and noise cancellation [1].However,unfortunately,the mentioned algorithms converge slowly when their input signal is colored.

To further speed up the convergence rate of an adaptive filter for colored input signals,in subband adaptive filter (SAF),the colored input signals are divided into multiple approximately white subband signals [2].In [3],the normalized SAF (NSAF) algorithm has approximately the same complexity as the NLMS algorithm,while its convergence rate is higher.In many system identification scenarios,for example,acoustic echo path,the system impulse response is sparse or block-sparse [4−6].It is noteworthy that in the sparse system,most coefficients are zero or near zero and just a few of them are nonzero,and in the block-sparse system,the coefficients are in the form of a single cluster or multi-cluster,where in a cluster is a gathering of the nonzero coefficients.In comparison to the NSAF algorithm,the proportionate NSAF(PNSAF) algorithm has a fast initial convergence,when the echo path is sparse.However,unfortunately,this algorithm has a slow convergence after the initial fast convergence,and a poor performance for the dispersive systems [7].The improved PNSAF (IPNSAF) has a good performance for both the sparse and the dispersive systems [7].To keep the fast initial convergence speed during the whole adaptation process until the adaptive filter reaches its steady state,the µ-law PNSAF (MPNSAF)has been proposed in [7].However,these algorithms are not robust against impulsive interference.

Recently,several subband adaptive filter algorithms have been proposed in [8−17],which show a good robustness against impulsive interference.In [8],the sign subband adaptive filter (SSAF) algorithm,by using the idea that lower order statistics can improve robustness against impulsive interference,minimized anL1-norm of the subband a posteriori error vector of the filter.To enhance the performance of the SSAF algorithm,several algorithms have been developed in [9−17].The individualweighting-factor SSAF (IWF-SSAF) algorithm in [16]used an IWF for each subband.Moreover,in [17],the normalized logarithmic SAF (NLSAF) algorithm has the same convergence rate as the SSAF with less steady state error.

To speed up the convergence rate in the sparse system identification scenario,several SAF algorithms have been proposed in [7,18−23].The proportionate SSAF (P-SSAF)algorithm and the affine projection SSAF (AP-SSAF) algorithms have been presented in [21].TheL0-norm SSAF(L0-SSAF) and theL0-norm NLSAF (L0-NLSAF) algorithms in [22,23]have been derived by inserting a penalty of sparsity,i.e.,L0-norm of the adaptive tap-weights,into the SSAF and the NLSAF algorithms cost functions,respectively.In addition,the developed algorithm named individual-weighting-factor improved PSSAF (IWF-IPSSAF) has been proposed in [17].Recently,several algorithms have been proposed for the block-sparse system identification scenario [24−29].In the block-sparse LMS(BS-LMS) algorithm [24],a penalty of block-sparsity,which is a mixedL2,0-norm of the adaptive tap-weights with the equal group partition sizes inserted into the cost function of the conventional LMS algorithm.

The generalized variable step size continuous mixedpnorm (GVSS-CMPN) algorithm in [30]demonstrates a good robustness against impulsive interference by minimizing thep-norms of the system output error,wherepis a continuous value from 1 to 2.However,according to the simulations,it has a slow convergence rate for the colored input signal.In order to solve this problem,we present a new SAF algorithm named generalized continuous mixedp-norm SAF (GCMPN-SAF) with its convergence analysis,in this paper.To further speed up the convergence rate,for the sparse and the block-sparse systems identification processes,a family of the proposed algorithms are also proposed.In general,our main contributions are as follows:

(i) In order to speed up the convergence rate of the robust GVSS-CMPN algorithm,for the colored input signals,we apply the SAF-structure to this algorithm.According to the simulation results,we can see that the proposed algorithm has a good robustness against impulsive interference,and also exhibits a proper convergence rate and tracking capability for the colored input signals.Also,the proposed algorithms have a better performance than some other state-of-the-art algorithms in the literature with respect to the convergence rate and the tracking capability.

(ii) In order to improve the performance of the proposed algorithm for the sparse and the block-sparse systems identification processes,the proportionate versions of the GCMPN-SAF algorithm,named proportionate GCMPN-SAF (PGCMPN-SAF),improved PGCMPNSAF (IPGCMPN-SAF),and µ-law PGCMPN-SAF (MPGCMPN-SAF) algorithms are developed.Also,for a better sparse system identification,we propose another algorithmL0-GCMPN-SAF which is derived by inserting anL0-norm of the adaptive tap-weights into the GCMPN-SAF algorithm cost function.In order to improve the performance of the proposed algorithm,for the block-sparse system identification process,we also develop the BSGCMPN-SAF algorithm which is derived by inserting a mixedL2,0-norm of the adaptive tap-weights with the equal group partition sizes to the GCMPN-SAF algorithm cost function.Simulation results show that the proportionate versions of the proposed algorithm have a better performance than the non-proportionate counterparts GCMPN-SAF,L0-GCMPN-SAF and BS-GCMPNSAF algorithms for both the sparse and the block-sparse systems.Similar to [7],we can see that the MPGCMPNSAF algorithm has a better performance than the IPGCMPN-SAF algorithm,and the IPGCMPN-SAF algorithm has a better performance than the PGCMPN-SAF algorithm.Also,the performance of the BS-GCMPNSAF algorithm is better than theL0-GCMPN-SAF algorithm,especially for the block-sparse system.

2.Review of the SAF algorithm

In the system identification process,the desired signald(n) is obtained as

whereu(n)=[u(n),u(n−1),···,u(n−M+1)]Tis the input signal vector,wodenotes the unknown weight vector with the lengthMand η(n) is the additive noise which includes the white Gaussian background noise ν(n) and the impulsive interference χ(n).Fig.1 shows the structure of the SAF withNsubbands.The analysis filters {H0(z),H1(z),···,HN−1(z)} partition the input signalu(n) and desired signald(n) intoNsubband signalsui(n) anddi(n)respectively.The subband signalsyi(n) are the output of the adaptive filter whose weight vector is represented asw(k)=[w0(k),w1(k),···,wM−1(k)]T.The signalsyi,D(k) anddi,D(k) are generated byN-fold decimation of the signalsyi(n) anddi(n),respectively.It is easy to obtain that

wheredi,D(k)=di(kN),ui(k)=[ui(kN),ui(kN−1),···,ui(kN−M+1)]Tand ηi(k) is theith subband noise.Also,the subband error signalsei,D(k) fori=0,1,···,N−1 are obtained as

Fig.1 Structure of the SAF

3.The proposed algorithm

In order to speed up the convergence rate of the robust GVSS-CMPN algorithm [30]for the colored input signal,this paper introduces a new SAF algorithm named GCMPN-SAF algorithm,which benefits from the following GVSS-CMPN cost function [30]:

4.Convergence analysis

We can see that αi(k) in (17) is a function of theei,D(k).Therefore,we can write (18) as

wheref(ei,D(k))=αi(k)/|ei,D(k)| is a nonlinear function of the subban d error signalei,D(k).By defining ψ(k)=wo−w(k),we have

By taking the squaredL2-norm and the expectation from both sides of (20),we have

The proposed algorithm converges in mean square sense,if we have in (21)d(µ)<0.Therefore,based on(22),a necessary mean-square convergence condition is obtained as

We proceed by utilizing the following assumptions:

(i) The background noise ν(n) is a zero-mean white Gaussian process with the varianceThe impulsive interference is generally regarded as the χ(n)=ω(n)ρ(n)[14,15,21,22],where ω(n) is a white Gaussian process with zero-mean and varianceand ρ(n)is a Bernoulli distribution with the probability mass function detailed asp{ρ(n)=1}=Pr,p{ρ(n)=0}=1−Pr.Note thatPrrepresents the probability of the occurrence of impulsive interference.Therefore,the additive noise η(n)=ν(n) +χ(n),can be considered as a Gaussian process with the zero-mean and the variance

(ii) Theith decimated subband input signal is approximately white [2,7],thus we conclude

(iii) The ratio of the expectation of two random variables is approximately equal to the expectation of the ratio between them,i.e.,E(x)/E(y)≈E{x/y},which is reasonable for sufficiently long filters [30,31].

By using the above assumptions,(23) is simplified as

By definitions ofm(k) andea,i(k) denoted in this section,we have the following equation:

5.GCMPN-SAF for sparse and block-sparse system

To further speed up the convergence rate of the GCMPNSAF algorithm for the sparse and the block-sparse systems identification processes,three proportionate versions of the GCMPN-SAF algorithm named PGCMPNSAF,IPGCMPN-SAF,and MPGCMPN-SAF algorithms,and twoL0-GCMPN-SAF and BS-GCMPN-SAF algorithms are developed in this section.

5.1 PGCMPN-SAF

In the proposed PGCMPN-SAF algorithm,for each subband,different step-sizes are assigned to the coefficients based on the current estimated magnitudes of them.Therefore large step-size will be assigned to the coefficient with a large current magnitude,and vice versa.With the update gains proportional to the current tap weights,very fast convergence performance is obtained [7].Vector update for the PGCMPN-SAF algorithm is given [7]by

where γ is a small positive constant to avoid dividing by zero,U(k)=[u0(k),u1(k),···,uN−1(k)],eD(k)=[e0,D(k),e1,D,(k),···,eN−1,D(k)]T,andA(k)=diag(a0(k),a1(k),···,aM−1(k)) is a diagonal matrix whose diagonal elements are calculated as

5.2 IPGCMPN-SAF

Unfortunately,when the impulse response is dispersive(non-sparse),the proportionate version of algorithms converges much slower than itself.The improved proportionate version is independent of whether or not the impulse response of the system is sparse or dispersive [7].According to [7],the update formula for the tap-weights of the IPGCMPN-SAF algorithm can be expressed as

where,at each iteration,the relative weighting of the proportionate and the non-proportionate adaptation is controlled by the selection α ∈[−1,1].The values of −0.5 or 0 are typically used for α in [7,21].

5.3 MPGCMPN-SAF

The µ-law proportionate version of algorithms shows the fast convergence during the whole adaptation process.Here,by using an objective function we can obtain the step-size control factors.Also,the condition under which the fastest overall convergence will be achieved for the steepest descent algorithm has been obtained and the equations used to calculate the optimal step-size control factors in order to satisfy that condition have been derived [7].According to [7],the update formula for the tapweights of the MPGCMPN-SAF algorithm can be obtained as

5.4 L0 -norm GCMPN-SAF (L0 -GCMPN-SAF)

By adding theL0-norm feature,which directly determines the sparsity of a vector to the cost function (6),we develop theL0-GCMPN-SAF algorithm in this section.This extra term can lead to finding a sparse vector that reduces the cost function.According to [19,23],the weight vector of theL0-GCMPN-SAF algorithm is updated as

where β ∈[5,20]shows a good performance [19,23,24].

5.5 BS-GCMPN-SAF

By adding theL2,0-norm feature,which directly determines the block-sparsity of a vector to the cost function(6),we develop the BS-GCMPN-SAF algorithm in this section.This extra term can lead to finding a block-sparse vector that reduces the cost function.According to [24,25],the weight vector of the BS-GCMPN-SAF algorithm is updated as

Here the mirrors represent the stepsisters vanity and the family s wealth. The fact that the family owns mirrors large enough to give a full reflection of a person from head to toe shows that they have been extremely wealthy and thus powerful at least in the past if not Cinderella s present (Chevalier 1982).Return to place in story.

wherepdenotes the group partition size,β is a positive c onstant anddenotes the ceiling function.

6.Simulation results

The performance of the proposed GCMPN-SAF algorithm in a system identification process is evaluated in this section.We use two sparse types of the measured acoustic-echo-channels as the unknown systems,which are depicted in Fig.2,where the first type is a sparse impulse response (Fig.2(a)),and the second type is a blocksparse impulse response (Fig.2(b)).For all the simulations,the length of the unknown system isM=512,and the adaptive filter has the same length.The input signal is an AR(1) or an AR(2) signal,generated by filtering a white Gaussian noise using a first-orderH(z)=1/ (1−0.9z−1),or a second-order systemH(z)=1/(1−0.25z−1−0.65z−2),respectively.The filter bank is an extended lapped transform (ELT) [33],and the number of subbands is chosen asN=4.Also,the background noise ν(n)is an additive white Gaussian noise with a signal-to-background-noise ratio (SBNR) of 30 dB,which is defined as SBNR=wherez(n)=uT(n)wo.Also,we consider the impulsive interference χ(n),as mentioned in Assumption (i),withIn addition,we use the normalized mean square deviation(NMSD) in dB defined asto measure the performance of the algorithms.In all the simulations we choose the parameters value of the competing algorithms according to the best values in their references,in such a way that all the algorithms have the same steady-state NMSD with the maximum convergence speed in achieving such a steady-state level.All the results are averaged over 50 independent trials.

Fig.2 Two types of measured acoustic-echo-channels as unknown systems

6.1 Choice of θ

We study the performance of the GCMPN-SAF algorithm for the different θ for block-sparse impulse response with AR(1) input signal,in presence of impulsive interference,in Fig.3.As expected from [30],θ=−2 provides the least steady-state error.Therefore,θ=−2 is chosen as a proper value for the proposed algorithm in other simulations.

Fig.3 NMSD learning curves of the GCMPN-SAF for different θ(µ=0.05,ρ=δ=0.01,ξ=400)

6.2 Comparisons with the versions of SSAF

Fig.4 shows the NMSD learning curves of the robust GVSS-CMPN [30]algorithm,the non-robust algorithm with SAF structure NSAF [3]algorithm,and some robust SAF algorithms including proposed GCMPN-SAF,SSAF [8],NLSAF [13],and IWF-SSAF [16]algorithms,for the colored AR(1) and AR(2) input signals.In order to evaluate the tracking capability of the algorithms for the AR(1) input signal in Fig.4(a),the impulse response is selected as the sparse in Fig.2(a) at first and abruptly is changed into the BS in Fig.2(b) at iteration 7.5×103.Also the tracking capability of the algorithms for the AR(2) input signal is evaluated in Fig.4(b) by selecting the impulse response as sparse in Fig.2(a) at first and change it into the BS in Fig.2(b) at iteration 3.5×103.The value of the parameters for Fig.4(a) are selected as SSAF (µ=0.02),NLSAF (µ=0.03,α=1 500),IWF-SSAF (µ=0.01),GVSS-CMPN (µ=0.000 4),NSAF (µ=0.5,0.01),GCMPN-SAF(µ=0.02),and for Fig.4(b) are selected as SSAF(µ=0.05),NLSAF (µ=0.06,α=1 500),IWFSSA(µ=0.02),GVSS-CMPN (µ=0.001),NSAF (µ=0.5,0.01) and GCMPN-GVSS-CMPN (µ=0.001),NSAF(µ=0.5,0.01) and GCMPN-SAF(µ=0.04).As can be seen,for both Fig.4(a) and Fig.4(b),the performance of the proposed algorithm is better than SSAF,NLSAF and GVSS-CMPN algorithms in terms of the convergence rate and is the best algorithm in terms of the tracking capability.As expected,the performance of the proposed algorithm is much better than the GVSS-CMPN,for the colored input signals,because it benefits from the SAF structure.It is noteworthy that although the convergence rate of the GCMPN-SAF algorithm is almost similar to the IWF-SSAF algorithm at first,but the proposed algorithm has a better tracking capability.Also,the NSAF which is not robust against impulsive interference,exhibits a poor convergence performance for both the AR(1)and the AR(2) input signals.

Fig.4 NMSD learning curves of the several subband and the proposed algorithms under impulsive interference

6.3 A family of the proposed algorithm

Fig.5 NMSD learning curves of a family of the proposed algorithm with the AR(1) input signal under impulsive interference

Fig.6 NMSD learning curves of a family of the proposed algorithm with AR(2) input signal under impulsive interference

6.4 Comparisons with the other developed algorithms

Fig.7 and Fig.8 show the NMSD learning curves of the several developed algorithmsL0-SSAF [22],L0-NLSAF[23],L0-GCMPN-SAF,IPSSAF [21],IWF-IPSSAF [16],IPGCMPN-SAF and MPGCMPN-SAF,with the AR(1)and the AR(2) input signals respectively,for the sparse and the BS systems.In Fig.7(a) and Fig.8(a),the impulse response is sparse (Fig.2(a)) and in Fig.7(b) and Fig.8(b),the impulse response is BS (Fig.2(b)).In order to evaluate the tracking capability of the algorithms,all of the impulse responses are abruptly multiplied by −1 at iteration 5 000.The value of the parameters are selected as IPSSAF (µ=0.06),L0-SSAF (µ=0.000 6,γ=0.01,β=5),L0-NLSAF (µ=0.06,γ=5×10−4,β=5,α=1 500),IWF-IPSSAF(µ=0.025) and for other algorithms are selected as in Section 6.3.It is found that in Fig.7 and Fig.8,the proposed MPGCMPN-SAF algorithm has the best performance,and the IPGCMPN-SAF and theL0-GCMPNSAF algorithms have better performance than their counterparts,IPSSAF andL0-SSAF algorithms,respectively.Although,the IWF-IPSSAF and the proposed IPGCMPNSAF algorithms have almost the same convergence performance at first,the proposed IPGCMPN-SAF algorithm has a better tracking capability than the IWFIPSSAF algorithm.As can be seen,theL0-NLSAF algorithm has a better performance than theL0-GCMPNSAF algorithm at first,but the proposedL0-GCMPN-SAF algorithm has a better tracking capability than theL0-NLSAF algorithm,especially for the AR(1) input signal.

Fig.7 NMSD learning curves of the several algorithms and the proposed algorithms for the AR(1) input signal under impulsive interference

Fig.8 NMSD learning curves of the several algorithms and the proposed algorithms for the AR(2) input signal under impulsive interference

7.Conclusions

In this paper,the new SAF algorithm named GCMPNSAF algorithm that benefits from the GCMPN constraint in its cost function to suppress the effect of impulsive interference is proposed.Then,the convergence of the proposed algorithm is analyzed.Furthermore,in order to accelerate the convergence rate in the sparse and BS systems identification processes,several proportionate versions of the proposed algorithm PGCMPN-SAF,IPGCMPN-SAF and MPGCMPN-SAF,L0-GCMPN-SAF and BS-GCMPN-SAF algorithms are developed.Simulation results demonstrate that the proposed algorithms have a better performance than some other state-of-the-art algorithms in the literature with respect to the convergence rate and tracking capability.