Real Sparse Fast DCT for Vectors with Short Support

Abstract

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_N^{\mathrm{II}}\mathbf{x}$ if an upper bound $M\ge 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\to 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}$.

arXiv comment28 pages, 5 figures