  We study the problem of estimating the best B term Fourier representation for
a given frequency-sparse signal (i.e., vector) $\textbf{A}$ of length $N \gg
B$. More explicitly, we investigate how to deterministically identify B of the
largest magnitude frequencies of $\hat{\textbf{A}}$, and estimate their
coefficients, in polynomial$(B,\log N)$ time. Randomized sub-linear time
algorithms which have a small (controllable) probability of failure for each
processed signal exist for solving this problem. However, for failure
intolerant applications such as those involving mission-critical hardware
designed to process many signals over a long lifetime, deterministic algorithms
with no probability of failure are highly desirable. In this paper we build on
the deterministic Compressed Sensing results of Cormode and Muthukrishnan (CM)
\cite{CMDetCS3,CMDetCS1,CMDetCS2} in order to develop the first known
deterministic sub-linear time sparse Fourier Transform algorithm suitable for
failure intolerant applications. Furthermore, in the process of developing our
new Fourier algorithm, we present a simplified deterministic Compressed Sensing
algorithm which improves on CM's algebraic compressibility results while
simultaneously maintaining their results concerning exponential decay.
