Real sparse fast DCT for vectors with short support (Q2332391)

The authors present a new deterministic sparse fast algorithm for the inverse discrete cosine transform of type II (inverse DCT-II) for the reconstruction of an input vector \(\mathbf{x} \in \mathbb{R}^N\), \(N=2^J\), with support of short length \(m\) from its DCT-II, assuming that an upper bound \(M\) on the support length \(m\) is known. Note that the case where \(m\) is unknown a priori is solved by the same authors [Numer. Algorithms 82, No. 2, 663--697 (2019; Zbl 1472.65172)]. The proposed algorithm uses only real arithmetic, has a sublinear runtime of \(\mathcal{O} \big(m \log m \log \frac{2N}{m}\big)\) and requires \(\mathcal{O} \big(m\log \frac{2N}{m}\big)\) samples. The runtime and stability for noisy input data are illustrated by numerical experiments.