40m QIL Cryo_Lab CTN SUS_Lab TCS_Lab OMC_Lab CRIME_Lab FEA ENG_Labs OptContFac Mariner WBEEShop
  40m Log  Not logged in ELOG logo
Message ID: 6553     Entry time: Fri Apr 20 23:02:25 2012
Author: Den 
Type: Update 
Category: Adaptive Filtering 
Subject: frequency domain filter 

 DFT-LMS is a frequency domain adaptive filter that demonstrates faster convergence compared to the time-domain LMS filter. I've tested Discrete Fourier Transform (DFT-LMS) filter. It converts witness signal to the frequency domain using DFT and corrects the eigenvalues of the covariance matrix to make them as equal to each other as possible (does pre-whitenning of the witness signal).

Left plot compares learning curves for time domain LMS and DFT-LMS algorithms on the simulated data from seismometers and mcl (number of averages  = 30) Right plot shows the evolution of the filter coefficients norm (Euclidean norms of the coefficient vector). Though LMS algorithm works in the time domain and DFT-LMS in the frequency domain, the coefficient vectors must have the same length, because we Fourier Transform is achieved by applying a unitary operator => vector norm must not change.

dft.png   norm.png

Plots show that both algorithms converge to the same coefficients vector norm, but DFT-LMS does it much faster then LMS. 

Online realization: 

Good news: algorithm complexity is linear in filter length. Though the algorithm does Fourier transform, its complexity is still O(M), M - number of coefficients. Simulations show that DFT-LMS is ~8-9 times slower then LMS. This is not so bad, may be we can do even slightly better.

Bad news: downsample process is not simple. Due to Fourier transform, the filter needs the whole witness signal vector before calculating the output. This is sad and in contrast with LMS algorithm where we could start to calculate the new output immediately after computing the previous output. We either need to calculate the whole output immediately or introduce delay in the output or approximate Fourier transform with some previous witness signal values.

Realization in the kernel: I asked Alex about complex numbers, exponents, sin and cos functions in the kernel c and he answers that we do not have complex numbers, about exp, cos, sin he is not sure. But for DFT-LMS algorithm we are able to get round of these difficulties. Complex numbers will be presented as  2 real numbers. Then exp (a) = cos(a) + i*sin(a). All what we need for DFT-LMS are sin(2 * pi * k / M) and cos(2 * pi * k / M), k=0,1,2,...,M-1. Fortunately, M - (filter length) is big enough, typical value pi/M ~ 0.001 and we can calculate sin(2*pi/M) and cos(2*pi/M) using Taylor series. As the argument is small, 5-6 terms will be enough to get precision ~1e-20. Then we build the whole table of cos and sin according to induction cos(2*pi/M*k) = cos(2*pi/M*(k-1))cos(2*pi/M) - sin(2*pi/M*(k-1))sin(2*pi/M), sin(2*pi/M*k) = cos(2*pi/M*(k-1))sin(2*pi/M) + sin(2*pi/M*(k-1))cos(2*pi/M). We should do it only once, so the algorithm will build these values in the beginning during first several iterations, then will use them.

The main problem is downsampling. I need to think more about it.

ELOG V3.1.3-