To the best of my knowledge, FFT algorithm enables us to compute the matrix-vector multiplication $\boldsymbol{Fx}$ with complexity of $O(N\log N)$ where $\boldsymbol{F}$ is a $N\times N$ Fourier matrix and $\boldsymbol{x}$ is a length-$N$ vector. I'm thinking of a variant of FFT: only first-$k$ components of $\boldsymbol{x}$ are nonzero. How much complexity can we save in this case?
Best regards, Heedong Do