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?


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:

enter image description here


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.