# Estimate the Discrete Fourier 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 Series.

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

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

Thank You.

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