Header menu link for other important links
Complexity of pruning strategies for the frequency domain LMS algorithm
K. M.Muraleedhara Prabhu
Published in
Volume: 86
Issue: 10
Pages: 2836 - 2843
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. © 2006 Elsevier B.V. All rights reserved.
About the journal
JournalSignal Processing
Open AccessNo
Concepts (11)
  •  related image
    Adaptive filtering
  •  related image
    Adaptive systems
  •  related image
  •  related image
    Fast fourier transforms
  •  related image
    Frequency domain analysis
  •  related image
    Interference suppression
  •  related image
  •  related image
  •  related image
  •  related image
  •  related image
    Computational complexity