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.FT based imputation

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


1 Answer 1


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)


  • 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:


  • 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:


  • 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

  • $\begingroup$ 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? $\endgroup$ Mar 8, 2019 at 18:16
  • $\begingroup$ 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. $\endgroup$
    – Elena Albu
    Mar 17, 2019 at 13:28
  • $\begingroup$ 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) $\endgroup$
    – Elena Albu
    Mar 17, 2019 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.