Sparse signal FFT

Question

Say I had a time domain signal $x[k]$ wich is sparse: $\log(N)^2$ nonzero samples and the fourier transform has only a very (very!) small number of high frequency components. Are there any techniques or algorithms for recovering these high frequency components in sublinear time? (something like $O(k^c\log(N)^d)$ where $k$ is a variable related the sparsity in either the frequency or the time domain).

Answer 1

Partial FFT

Sparse FFT

Can also subsample the input, which will alias (fold) the high frequencies onto lower, then take FFT at the lower length, and then shift the result back onto higher frequencies as a post-processing step. If the lower frequencies are exactly zero, then the procedure is exact. Care is due for handling odd vs even, and dc and Nyquist bins; example below.

import numpy as np
from numpy.fft import fft, ifft

x = np.random.randn(128) + 1j * np.random.randn(128)
xf = fft(x)
# high freqs only
xf[:64-16] = 0
xf[64+16:] = 0
xhigh = ifft(xf)
xf = fft(xhigh)

# take fft at lower length, compensate for subsampling
xf_s = fft(xhigh[::2]) * 2  # xf short
xf_sc = np.zeros(len(x), dtype='complex128')  # xf short corrected
xf_sc[64-16:64] = xf_s[-16:]
xf_sc[64:64+16] = xf_s[:16]

# confirm they match
assert np.allclose(xf, xf_sc)