# Estimate the Discrete Fourier Transform / Series of a Signal with Missing Samples

Assuming we have a discrete signal $${ \left\{ x \left[ n \right] \right\}}_{n = 1}^{N}$$.
Which has a Discrete Fourier Transform / Series.

Now, assume I'd like to estimate its Discrete Fourier Series coefficient yet some samples of $$x \left[ n \right]$$ are missing (The indices are known).

How could that be done efficiently without computing the Pseudo Inverse of the adapting Fourier Series matrix?

• How many samples are missing? – gallamine Aug 19 '14 at 19:06
• Let's say $K < N$. Something like $N = 3500$ and $K = 500$. – Royi Aug 19 '14 at 19:28

Given $$\left\{ x \left[ n \right] \right\}_{n \in M}$$ where $$M$$ is the set of indices given for the samples of $$x \left[ n \right]$$.

The trivial solution (Which it would be great to have a faster more efficient solution is what I'm looking for) would be:

$$\arg \min_{y} \frac{1}{2} \left\| \hat{F}^{T} y - x \right\|_{2}^{2}$$

Where $$\hat{F}$$ is formed by subset of columns of the DFT Matrix $$F$$ matching the given indices of the samples, $$x$$ is the vector of the given samples and $$y$$ is the vector of the estimated DFT of the full data of $$x \left[ n \right]$$.

The solution is then given by the Pseudo Inverse (Least Squares Solution):

$$y = { ( \hat{F} \hat{F}^{T} ) }^{-1} \hat{F} x$$

In practice, the matrix will be very poorly conditioned hence solution must be generated using the LS Solution using the SVD.

A sample code is shared on GitHub Repository.

Result of the code: 