# Sparse Fourier Transform for Sparse Pulse Trains

So I have signals for the form:

$$x_{k}(t) = \sum_{n=0}^{N} a_{k,n} \cdot \delta(t - nT_k)$$

that I receive as a superposition:

$$x(t) = \sum_{k=0}^{K} \sum_{n=0}^{N} a_{k,n} \cdot \delta(t - nT_k)$$

We know that (if we let $$N \rightarrow \infty$$) the Fourier transforms of the $$x_k(t)$$ are sparse, and therefore so would that of $$x(t)$$. In my application, my $$N$$ is fairly large so I say this holds rather well.

Question:

I want to compute a discrete Fourier transform that encourages the result to be as sparse as possible.

Can I use the sparse Fourier transform algorithm to compute the FFT of these signals? Will it produce a spectrum that is sparse in this case?

The sparse Fourier transform seems to rely on the OFDM trick, and, since the majority of my samples are zero, this isn't going to work. Should I just use a L1 regularization technique like the LASSO instead? Or should I just add a bit of noise to the signals to prevent the catastrophic numerical errors?

Thanks!

Clarification:

Note that I really just want an 'clean' FFT because I'm doing all of this on a computer. Even though I am constrained to set a fixed length for my FFT, the FFT of these signals, after the proper resampling, gives me an approximate pulse train contaminated with noise. An NUFFT gives me something similar. I want to know if I can reduce this noise using regularization or the sparse Fourier transform algorithm.

• @MarcusMüller What do you make of this then? math.stackexchange.com/questions/1593800/… Feb 25, 2022 at 13:43
• ah sorry, I had a dumb-brain moment there for a second; a pulse train has a discrete Fourier transform, of course. A single pulse doesn't. Let me delete my bad comment. Feb 25, 2022 at 13:45
• But: you need to be very clear about what kind of Fourier transform you want: your question is about the FFT (which is just a DFT), and the formula above for $x_k$ is about time-continuous signals with infinite duration, which you cannot DFT, because, well, they are infinite and their sum is only periodic (and that period would be the minimal possible DFT length) if all $T_k$ are rationally related. Feb 25, 2022 at 13:47
• @MarcusMüller Okay. I will clarify. I really just want an FFT because I'm doing all of this on a computer. I have to set a fixed length for my FFT, yet, the FFT of these signals, after the proper resampling (and also an NUFFT), gives me an approximate pulse train contaminated with noise. I want to know if I can reduce this noise using regularization. Feb 25, 2022 at 13:52
• slightly confused by the statement "I want an FFT": it simply might not be applicable. So, is your original signal already time-discrete, or is it not? And if discrete, are $T_k$ all integers? Feb 25, 2022 at 14:07