Real sparse fast DCT for vectors with short support.

In this paper we present a new fast and deterministic algorithm for the inverse discrete cosine transform of type II for reconstructing a real input vector of length N with short support of length m from its discrete cosine transform of type II if an upper bound M on the support length m is known. The resulting algorithm only uses real arithmetic, has a sublinear runtime of O (M log ⁡ M + m log 2 ⁡ N M) and requires O (M + m log 2 ⁡ N M) samples. For m and M approaching the vector length, the runtime and sampling requirements approach those of a regular IDCT-II for vectors with full support. [ABSTRACT FROM AUTHOR]