A deterministic sparse FFT algorithm for vectors with small support (Q281476)

Let \(\mathbf x=(x_0,x_1,\dots,x_{N-1})\in\mathbb C^N\). The authors define the support length \(m\) of \(\mathbf x\in\mathbb C^N\) as the minimal integer \(m\) for which there exists a \(\mu\in\{0,1,\dots,N-1\}\) such that the components \(x_k\) vanish for \(k\notin I=\{(\mu+r)\mod N\), \(r=0,1,\dots, m-1\}\). The authors derive new algorithms to reconstruct a vector \(\mathbf x\in\mathbb C^N\) with support length \(m<N\) from its discrete Fourier transform \(\hat x\in\mathbb C^N\).