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:
