  In this paper we present a new fast and deterministic algorithm for the
inverse discrete cosine transform of type II for reconstructing the input
vector $\mathbf x\in\mathbb R^N$, $N=2^J$, with short support of length $m$
from its discrete cosine transform $\mathbf
x^{\widehat{\mathrm{II}}}=C^{\mathrm{II}}_N\mathbf x$ if an upper bound $M\geq
m$ is known. The resulting algorithm only uses real arithmetic, has a runtime
of $\mathcal{O}\left(M\log M+m\log_2\frac{N}{M}\right)$ and requires
$\mathcal{O}\left(M+m\log_2\frac{N}{M}\right)$ samples of $\mathbf
x^{\widehat{\mathrm{II}}}$. For $m,M\rightarrow N$ the runtime and sampling
requirements approach those of a regular IDCT-II for vectors with full support.
The algorithm presented hereafter does not employ inverse FFT algorithms to
recover $\mathbf x$.
