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).
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)