Low Complexity &Fast Affine Projection Sign Algorithm

Low Complexity &Fast Affine Projection Sign Algorithm

1 Mr. S. D. Shinde , 2 Mrs. P. P. Belagali, 3 Mrs. A. P. Patil

1,2Dept. of Electronics & Telecommunication Engg, JJMCOE Jaysingpur, India

3Dept. of Electronics Engg, JJMCOE Jaysingpur, India

Abstract

Least mean square algorithm is simplest algorithm having low time complexity & fast convergence rate but is not robust to noise. If no of inputs increases the convergence rate slows down which is overcome in APA, with increase in computational complexity. Sign algorithms (SAs) are more robust against impulsive interference but have slow convergence rate. In order to overcome this problem, an affine projection SA (APSA) has been proposed, which exhibits fast convergence rate. In this letter, we analyze LMS, APSA and then apply a Recursive approach proposed for the affine projection algorithm (APA) to the APSA to reduce its computational complexity.

Index Terms Adaptive filtering, Least mean square, affine projection, sign algorithm

Introduction

Adaptive filtering is a very important technique in a number of applications such as system identification, channel equalization, network and acoustic echo cancellation, and active noise control. An adaptive filter is characterized by its structure and algorithm. Once the structure of the adaptive filter has been selected, its convergence performance is fully dependent on its algorithm. It is well-known that adaptive filtering algorithms such as the least mean square (LMS) and normalized LMS (NLMS) have been widely used in the above applications. However, in some cases, the interference in the environment is impulsive, which degrades the performance of these adaptive filtering algorithms. Research has shown that classical sign algorithms (SAs) are robust against impulsive interference. However, they normally suffer from slow converge rate. Recently, a fast converging SA, called the affine projection SA (APSA), has been proposed, which combines the benefit of the affine projection algorithm (APA) and sign algorithm. Simulation results showed that the APSA can achieve improved performance on combating impulsive noise and speeding up convergence. Besides, the APSA is much simpler in implementation than the APA and does not have the numerical problems that exhibit in the classical fast affine projection (FAP) algorithm. Although the discussion of the computational complexity of

the APSA was simply mentioned, it was not considered as the main issue.

In this letter, we first analyze the LMS which has low complexity & fast convergence rate but as no of input values goes on increasing the convergence rate slows down hence APA is used for fast convergence rate as compared to LMS & NLMS algorithms but as the order of affine projection increases the computational complexity of the algorithm goes on increasing so APSA with the direct implementation in detail is studied and then the recursive approach which was proposed in for the APA is applied to the APSA to reduce its computational complexity. From the analysis, we will see that the computational complexity of the APSA with the efficient implementation can be reduced and is even lower than that of the classical fast affine projection (FAP) algorithm.

Generalized Block Diagram

Least Mean Square Algorithm

LMS algorithm uses the estimates of the gradient vector from the available data. LMS incorporates an iterative procedure that makes successive corrections to the weight vector in the direction of the negative of the gradient vector which

eventually leads to the minimum mean square error. Compared to other algorithms LMS algorithm is relatively simple; it does not require correlation function calculation nor does it require matrix inversions. LMS algorithms have a step size that determines the amount of correction to apply as the filter adapts from one iteration to the next. Choosing the appropriate step size requires experience in adaptive filter design.

Filter convergence is the process where the error signal (the difference between the output signal and the desired signal) approaches an equilibrium state over time

The LMS algorithm initiated with some arbitrary value for the weight vector is seen to converge and stay stable for

0 < < 1/

max

Define the output vector and the a priori error vector, respectively, as

= ( 1)

and e k =y k -y'(k)

let = ( ) where (. ) represents the sign function. Then the update equation of the APSA can be written as

= 1 + ()

+

where is the step-size parameter which controls the tradeoff between the convergence rate and final misalignment and is the regularization parameter which is used to overcome numerical difficulties.The algorithm requires one square root

Where

max

is the largest eigenvalue of the

operation and one division at each time instant.

correlation matrix R. The convergence of the algorithm is inversely proportional to the eigenvalue spread of the correlation matrix R. When the eigenvalues of R are widespread, convergence may be slow. The eigenvalue spread of the correlation matrix is estimated by computing the ratio of the largest eigenvalue to the smallest eigenvalue of the matrix. If is chosen to be very small then the algorithm converges very slowly. A large value of may lead to a faster convergence but may be less stable around the minimum value. One of the literatures [will provide reference number here] also provides an upper bound for based on several approximations as <= 1/(3trace(R)).

The LMS algorithm can be summarized by following equations

y(n) = wh x(n) e(n) = d (n) y(n)

w(n + 1) = w(n) + x(n)e (n)

Affine Projection Sign Algorithm

APA is a generalization of NLMS & when sign for error signal is considered we introduce an APSA algorithm.Consider the desired signal y(k) that arises from the linear model. where (.)T denotes the transpose operation, w is the unknown system to be estimated,x(k) is the input signal vector of length L, and v(k) represents the background noise plus interference signal.

y(k) = xT (k)w + v(k)

Grouping the M recent input signal vectors together forms the input signal matrix, i.e. X(k)

Although sign operations are also required in the APSA, they are much simpler than multiplication and addition operations. It can be seen that the APSA with the direct implementation requires multiplications and additions at each time instant and that the computational complexity of the APSA increases with the increase of its projection order.

Recursive Affine Projection Sign Algorithm

we see that the number of multiplications of the APSA with the direct implementation is mainly related to Step 1.

= 1

+ ( )

( ) +

Where = ()

= 1

= 2

1 ( 1 )

+

1 1 ( 1 ) +

= ()

()( 1 )

+

1 1 ( 1 ) +

and G(k)= 1

In this section, we employ an efficient implementation method to reduce the computational complexity of the APSA. In fast projection algorithm the recursive approach is used to calculate z(k),G(k),R(k).the same approach if applied to the APSA, an efficient implementation of the APSA can be obtained,

Results Obtaned

Input signal can be a audio file or generated in random form. Here an audio input is considered. fig 1. below shows the computational time difference over number of iterations N for a predefined system parameters. here we have considered parameters of low pass filter. from the graph it is clear that APSA requires more time than LMS & efficient APSA. Though LMS & efficient APSA graphs are almost constant throughout the difference is seen for low no of iterations. Efficient APSA performs better and requires much less time as that of LMS for low value of N.

When an unknown system is considered, we have generated system parameters by using random function. For the graphs below we will be required to have to vary the no of inputs L & no of iterations N value. If the value of L is varying we cannot use the predefined system parameters.

Computational time difference with fixed no of inputs L for variable number of iterations N is shown in fig 2. It is observed that for low of values of N the computational time is nearly similar for LMS, APSA & efficient APSA. The computational time of APSA starts increasing as value of N increases. It is observed that there is no variation in the plot of LMS & efficient APSA as the value of N increases or decreases.If the value of number of iterations N is kept constant and the no of inputs L is varied then the computational time difference over number of inputs plot is as shown in fig 3.

If the plot of no of iterations N over number of inputs L is plot for LMS, APSA, efficient APSA we get result as shown in fig 4. It is observed that for APSA as the value of L goes on increasing the number of iterations N required for algorithm to converge goes on increasing.

Fig 1. Computational time difference for variable N of system having predefined System Parameters

Fig 2. Plot of Computational time difference over number of inputs N for constant number of inputs L

Fig 3. Plot of Computational time difference over varying no of input L for constant number of iterations N

Observing the LMS & efficient APSA plot it is seen that number of iterations required are not as APA but the number of iterations required for efficient APSA nearly remains constant & has better performance than LMS.

When the plot of error signal for the three algorithms is plotted for variable number of iterations the result was as shown in fig 5. It is clearly observed that the error signal is more for APSA as compared to basic LMS algorithm but for efficient APSA the error is minimum and is almost equal to zero which does not change with change in number of iterations

Fig 4. Plot of number of iterations N over number of inputs L

Fig 5. Error difference for varying number of iterations N

Conclusion

It is seen that convergence rate of APA is fast as compared to LMS but as projection order increases it degrades hence APSA algorithm is implemented. The computational complexity of the APSA with the direct implementation is relatively high and increases with increasing the projection order of the APSA. Then, a recursive approach which was applied to the APSA to reduce its computational complexity. With this efficient implementation method, the APSA can be applied to adaptive filtering applications

References

1. A learning method for system identification Nagumo, J.; Noda, A. Automatic Control, IEEE Transactions on Volume: 12 , Issue: 3 Digital Object Identifier: 0.1109/TAC.1967.1098599 Publication Year: 1967 , Page(s): 282 – 287

2. Efficient Implementation of the Affine Projection Sign Algorithm, Jingen Ni; Feng Li Signal Processing Letters, IEEE Volume: 19 , Issue: 1 Digital Object Identifier: 0.1109/LSP.2011.2174784 Publication Year: 2012 , Page(s): 24 26

3. Low-Complexity Implementation of the Affine Projection Algorithm Zakharov, Y.V.Signal Processing Letters, IEEE Volume: 15 Digital Object Identifier: 10.1109/LSP.2008.2001111 Publication Year: 2008 , Page(s): 557 560

4. A new sign algorithm for interference suppression in DS-CDMA systems Liping Sun; Guangrui Hu Communications Letters, IEEE Volume: 7 , Issue: 5 Digital Object Identifier:

   10.1109/LCOMM.2003.811194 Publication Year: 2003 , Page(s): 233 235

5. A robust mixed-norm adaptive filter algorithm Chambers, J.; Avlonitis, A.Signal Processing Letters, IEEE Volume: 4 , Issue: 2 Digital Object Identifier: 10.1109/97.554469 Publication Year: 1997 , Page(s): 46 48

6. An Affine Projection Sign Algorithm Robust Against Impulsive Interferences Tiange Shao; Zheng, Y.R.; Benesty, J. Signal Processing Letters, IEEE Volume: 17 , Issue: 4 Digital Object Identifier: 10.1109/LSP.2010.2040203 Publication Year: 2010 , Page(s): 327 330

7. Proportionate Affine Projection Sign Algorithms for Network Echo Cancellation Zengli Yang; Zheng, Y.R.; Grant, S.L. Audio, Speech, and Language Processing, IEEE Transactions on Volume: 19 , Issue: 8 Digital Object Identifier: 10.1109/TASL.2011.2125955 Publication Year: 2011 , Page(s): 2273 2284

8. Low-complexity constrained affine- projection algorithms Werner, S.; Apolinario, J.A., Jr.; de Campos, M.L.R.; Diniz, P.S.R. Signal Processing, IEEE Transactions on Volume: 53 , Issue: 12 Digital Object Identifier: 10.1109/TSP.2005.859348 Publication Year: 2005 , Page(s): 4545 4555