  We consider the problem of building numerically stable algorithms for
computing Discrete Fourier Transform (DFT) of $N$- length signals with known
frequency support of size $k$. A typical algorithm, in this case, would involve
solving (possibly poorly conditioned) system of equations, causing numerical
instability. When $N$ is a power of 2, and the frequency support is a random
subset of $\mathbb{Z}_N$, we provide an algorithm that has (a possibly optimal)
$O(k \log k)$ complexity to compute the DFT while solving system of equations
that are $O(1)$ in size.
