Block Sparse Memory Improved
Proportionate Affine Projection Sign
Algorithm

gl  n  

h  n   h0  n  h1  n 

sgn 



hˆ  n   [hˆ 0  n  , hˆ 1  n  ,

y  n    y  n  y  n  1

(2)

gk  n  

in which 1P

hˆ k  n  
2

(12)

1   
2L



1   
2 N  i 0

N 1

, g N 1  n  1P  (13)

hˆ k  n 

2

hˆ i  n   

,

(14)

2

is a P-length column vector of all ones, and



P

hˆ

2
j 1 kN  j

 n

, k  0,1,

, N 1 . The weight

update equation for BS-MIP-ASPA is

M most

P  n   g  n 

x  n  , P1  n  1 ,

x gs  n   P  n  sgn  e  n   ,

(4)
(5)

hˆ  n   hˆ  n  1 

y  n  M  1 , (6)
T

 x gs  n 
  xTgs  n  x gs  n 

where P1  n  1 also contains the first

where M is called the projection order. In [5], MIP-APSA proposed the
following weight update:

, g L 1  n  ,

, hˆ N 1  n ],

g  n   g0  n  1P , g1  n  1P ,

recent input vectors together:

e  n   y  n   X  n  hˆ  n  1 ,

 is a small

then the control matrix g  n  in (7)-(8) is be replaced by

hˆ  n  be the L1 adaptive filter coefficient vector which estimates the

T

M  1 columns of P  n  1 ,

and L  N  P ,

time index, and v  n  is the background noise plus near-end signals. Let

x  n  M  1 ,

denotes the Hadamard

Algorithm design: In network echo cancellation, the network echo path
is typically characterized by a bulk delay dependent on network loading,
encoding, and jitter buffer delays and an “active” dispersive region in the
range of 8-12 ms duration [1]. Meanwhile, it is well-known that NLMS
is preferred over PNLMS for dispersive system. Therefore, considering
the block-sparse characteristic of the network impulse response, the BSPNLMS algorithm was proposed to improve the PNLMS algorithm by
exploiting this special block-sparse characteristic, in which BS-PNLMS
used the same step-size within each block and the step-sizes for each
block were proportionate to their relative magnitude [7]. We propose to
take in account the block-sparse characteristic and partition the MIPAPSA adaptive filter coefficients into N groups with group-length P ,

T denotes transposition, L is the filter length, n is the

X  n   x  n  x  n  1

(11)

, L  1 ,  is a small positive constant

takes the sign of each element of a vector, and

(3)

true echo path vector h  n  at iteration n , and group the

,

positive constant. Compared with RIP-PAPSA, MIP-PAPSA takes into
account the ‘proportionate history’ from the last M moments of time.
More details can be found in [5]-[6].

(1)

T

(10)

  xTgs  n  x gs  n 

product, P1  n  1 contains the first

T

hL 1  n  ,

(9)

 x gs  n 

that avoids division by zero, the operation

filtered through the echo path h  n  to get the desired signal y  n  .

x  n  L  1 ,

(8)

x  n  , P1  n  1 ,

where 1    1 , l  0,1,

Review of MIP-APSA: For echo cancellation, the far-end signal x  n  is

x  n    x  n  x  n  1

.

L 1
2 i  0 hˆi  n   

hˆ  n  1  hˆ  n  

Introduction: Adaptive filters have been widely used in various
applications of system identification in which the normalized least mean
square (NLMS) algorithm is well-known due to its simplicity, but suffers
from slow convergence for colored input [1]. The affine projection
algorithm (APA) provides better convergence for colored input compared
with NLMS [2]. Meanwhile, the family of affine projection sign
algorithm (APSA) has been proposed to improve the performance of
APA under impulsive noise together with lower complexity [3]. In order
to exploit the sparsity of some echo paths, the real-coefficient improved
proportionate APSA (RIP-APSA) was proposed [4], and a memory
improved proportionate APSA (MIP-APSA) was further proposed to
achieve improved steady-state misalignment with similar computational
complexity compared with RIP-APSA [5]. Recently, the block-sparse
improved proportionate NLMS (BS-IPNLMS) algorithm was proposed
to improve the performance of IPNLMS for identifying block-sparse
systems [7]. In this Letter, motived by both BS-PNLMS and MIP-APSA,
we will propose a block sparse memory improved proportionate APSA
(BS-MIP-APSA) algorithm, which not only inherits the performance
improvement for block-sparse system identification, but also achieves
robustness to impulsive noise and the efficiency of MIP-APSA.

y(n)  xT (n)h(n)  v(n)

1    hˆl  n 



x gs  n   P  n  sgn  e  n   ,

A block sparse memory improved proportionate affine projection sign
algorithm (BS-MIP-APSA) is proposed for block sparse system
identification under impulsive noise. The new BS-MIP-APSA not only
inherits the performance improvement for block-sparse system
identification, but also achieves robustness to impulsive noise and the
efficiency of the memory improved proportionate affine projection sign
algorithm (MIP-APSA). Simulations indicate that it can provide both
faster convergence rate and better tracking ability under impulsive
interference for block sparse system identification as compared to APSA
and MIP-APSA.

g  n   g0  n  , g1  n  ,

2L

P  n   g  n 

J. Liu, and S. L. Grant

super-script

1   

(15)
(16)
(17)

M  1 columns of P  n  1 .

It should be noted that the proposed BS-MIP-APSA includes both APSA
and MIP-APSA. The MIP-APSA algorithm is a special case of proposed
BS-MIP-APSA with group length P  1 . Meanwhile, when P is
chosen as L , the BS-MIP-APSA algorithm degenerates to APSA.

(7)

1

Complexity: Compared with traditional RIP-APSA and MIP-APSA, the
extra computational complexity of the BS-MIP-APSA arises from the
computation of the l2 norm in (14), which requires

10

L multiplications
0

Normalized Misalignment

and N square roots. The complexity of the square root could be reduced
through a look up table or Taylor series [7]. Meanwhile, the increase in
complexity can be offset by the performance improvement as shown in
the simulation results.
Simulation results: In our simulation, the echo path is a L  512 finite
impulse response (FIR) filter, and the adaptive filter is the same length.
We generated colored input signals by filtering white Gaussian noise
through a first order system with a pole at 0.8. Independent white
Gaussian noise is added to the system background with a signal-to-noise
ratio (SNR) of 40 dB. The impulsive noise with signal-to-interference
ratio (SIR) of 0 dB is generated as a Bernoulli-Gaussian (BG) distribution.
BG is a product of a Bernoulli process and a Gaussian process, and the
probability for Bernoulli process is 0.1. The performance was evaluated
through the normalized misalignment: 10log10 ( h  hˆ

2
2

-10

-20

-30

-50

Normalized Misalignment

0
-0.5

100

150

200

250
(a)

300

350

400

450

2

3

4
Iterations

5

6

7

8
x 10

4

0

0.5

50

1

5

1

0

0

Fig. 2 Normalized misalignment of APSA, MIP-APSA, and BS-MIPAPSA for colored input signal.

2

h 2 ) . In

order to evaluate the tracking ability, we switch the echo path from the
one-cluster block-sparse system of Fig. 1(a) to the two-cluster blocksparse system of Fig. 1(b).

-1

APSA
MIP-APSA
BS-MIP-APSA

-40

-5
-10
-15
-20
-25

APSA
MIP-APSA
BS-MIP-APSA

500

-30

0.4

-35
0.2
0

1

2

3

4
Iterations

5

6

7

8
x 10

4

Fig. 3 Normalized misalignment of APSA, MIP-APSA, and BS-MIPAPSA for speech input signal.

-0.2
-0.4

0

0

50

100

150

200

250
(b)

300

350

400

450

References

500

Fig. 1 Two block-sparse systems used in the simulations: (a) one-cluster
block-sparse system, (b) two-cluster block-sparse system.

1

The APSA and MIP-APSA algorithms are compared with BS-MIPAPSA. The parameters are   0.001 ,   0.01 ,   0.01 ,   0 ,

2

M  2 , and P  4 . In the first case, we show the normalized
misalignment for colored input in Fig. 2. We could see that the proposed
BS-MIP-APSA achieves both faster convergence rate and better tracking
ability. In Fig. 3, the performance of BS-MIP-APSA is compared with
APSA and MIP-APSA for speech input signal, and we found that our
proposed algorithm demonstrates better performance too.

3

4

Conclusion: We have proposed a block-sparse memory improved affine
projection sign algorithm to improve the performance of block-sparse
system identification. Simulations demonstrate the proposed algorithm
has both faster convergence speed and tracking ability for block-sparse
system identification compared with APSA and MIP-APSA algorithms.

5

6

Acknowledgments: This work is supported by Wilkens Missouri
Endowment.
7

J. Liu, and S. L. Grant (Department of Electrical and Computer
Engineering, Missouri University of Science and Technology, Rolla, MO,
USA)
E-mail: sgrant@mst.edu

2

Benesty, J., Gänsler, T., Morgan, D.R., Sondhi, M.M, and Gay,
S.L., Advances in network and acoustic echo cancellation.
Springer, 2001.
Ozeki, K., and Umeda, T.: ‘’An adaptive filtering algorithm
using an orthogonal projection to an affine subspace and its
properties’, Electron. Commun. Jpn., 1984, 67-A, (5), pp. 1927
Shao, T., Zheng, Y. R., and Benesty, J.: ‘An affine projection
sign algorithm robust against impulsive interferences’, IEEE
Signal Process. Lett., 2010, 17, (4), pp. 327–330.
Yang, Z., Zheng, Y.R., and Grant, S.L.: ‘Proportionate Affine
Projection Sign Algorithms for Network Echo Cancellation’,
IEEE Trans. Audio, Speech, Lang. Process., 19, (8), pp. 22732284.
Albu, F., and Kwan, H.K.: ‘Memory improved proportionate
affine projection sign algorithm’, Electron. Lett., 2012, 48,
(20), pp. 1279-1281.
Paleologu, C., Ciochina, S., and Benesty, J.: ‘An efficient
proportionate affine projection algorithm for echo
cancellation’, IEEE Signal Process. Lett., 2010, 17, (2), pp.
165–168
Liu, J., and Grant, S.L.: ‘Proportionate adaptive filtering for
block-sparse system identification’, arXiv preprint
arXiv:1508.04172, 2015

