# Fourier Transform based imputation

Fourier Transform based imputation

Can any body please assist me in understanding the Fourier Transform based imputation algorithm shown in Figure.

I am struggling to understand ts and te.

Link of the research paper: https://www.sciencedirect.com/science/article/pii/S1532046415002269

## 1 Answer

This answer might come late, but I leave it here, just in case anybody lands here in the future.

$$t_s = min(j)$$ where $$v_j$$ is missing ==> this is the first position where a missing value is encountered

$$t_e = min(j)$$ where $$v_j$$ in non-missing ==> this is the first position after $$t_s$$ where a value (non-missing) is encountered

By detecting first $$t_s$$ and $$t_e$$, you have a "chunk" (sub-series) of values (till position $$t_s$$) followed by one or more missing values (till position $$t_e$$). The logic further uses DTF on the first $$t_s$$ values, padds it with zeros, performs IDFT and then replaces in the original vector the missing part. This is repeated until no missing values are left in the vector.

For example:

• You start with a vector like below (V = value, M = missing, I = imputed)

VVVVMMVVMMM

• you take the first 4 values, perform DFT, pad this result with 2 zero's, perform IDFT and replace the 2 M values with the ones from IDFT. you get:

VVVVIIVVMMM

• you take the first 8 values, perform DFT, pad this result with 3 zero's, perform IDFT and replace the 3 M values with the ones from IDFT. you get:

VVVVIIVVIII

• you stop because all values have been imputed.

The code in matlab is shared by the authors of the paper on github: https://github.com/kleinberg-lab/FLK-NN

• What is the intuition behind the logic that M values are replaced with ones from IDFT? Why those IDFT values are perfect to be replaced with Ms? – Muhammad Akmal Mar 8 '19 at 18:16
• I do not understand the intuition behind the whole algorithm, specifically I do not understand why padding with zeros at the end of the dft. It is probably some type of interpolation, but as far as I understood in signal processing it is more common to add zeros in the middle of the dft rather than at the end. – Elena Albu Mar 17 '19 at 13:28
• in my case, a last-observation-carried-forward imputation gave better results than this "fourier based imputation". Also, the fourier based imputation gave better results on a rescaled or normalized time series, but still not as good as LOCF. I think this imputation might work best if you have a cyclic time series. In the case of the paper, the authors used lab data like glucose which is cyclic (though if I recall correctly, on their dataset LOCF was also giving better or comparable results) – Elena Albu Mar 17 '19 at 13:35