  In this paper we present a new fast and deterministic algorithm for the
inverse discrete cosine transform of type II that reconstructs the input vector
$\mathbf{x}\in\mathbb{R}^{N}$, $N=2^{J-1}$, with short support of length $m$
from its discrete cosine transform
$\mathbf{x}^{\widehat{\mathrm{II}}}=\mathbf{C}_N^{\mathrm{II}}\mathbf{x}$.
  The resulting algorithm has a runtime of $\mathcal{O}\left(m\log m\log
\frac{2N}{m}\right)$ and requires $\mathcal{O}\left(m\log \frac{2N}{m}\right)$
samples of $\mathbf{x}^{\widehat{\mathrm{II}}}$.
  In order to derive this algorithm we also develop a new fast and
deterministic inverse FFT algorithm that constructs the input vector
$\mathbf{y}\in\mathbb{R}^{2N}$ with reflected block support of block length $m$
from $\widehat{\mathbf{y}}$ with the same runtime and sampling complexities as
our DCT algorithm.
