3
$\begingroup$

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.

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

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

$\endgroup$

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.