Complexity of pruning strategies for the frequency domain LMS algorithm

Large adaptive filters are frequently used in diverse applications such as channel equalization, interference suppression, beamforming, etc. The least mean squared (LMS) algorithm and its variants form one of the basic building blocks of adaptive systems. The frequency domain implementations of the LMS algorithm are preferred in practice since the computational burden of LMS can be reduced significantly by using the vast family of fast fourier transform (FFT) algorithms. Despite the advantage of frequency domain LMS over regular-LMS, the increasing computational complexity of the FFT-based LMS algorithms (with filter length) makes them unattractive for applications with a large number of filter taps. In this paper, FFT pruning is used to reduce the computational cost of frequency domain LMS by exploiting the structure of the LMS algorithm. We study various pruning strategies with our objective being reduction in computational burden and conclude that transform decomposition is the most appropriate pruning strategy. Using this pruning technique, worst-case computational savings of 10% and 5% can be achieved for applications that use filter lengths on the order of a few hundreds and a few thousands, respectively. In delay-sensitive applications, substantially more savings can be effected by pruning.