Sparse fast DCT for vectors with one-block support (Q2274167)

In this paper, the authors present a new deterministic sparse fast algorithm for the inverse discrete cosine transform of type II (inverse DCT-II), assuming that the resulting vector \({\mathbf x}\in {\mathbb R}^N\) possesses a one-block support of length \(m < N\), where \(m\) is unknown a priori. The resulting algorithm has computational cost of \({\mathcal O}\big(m\, \log m\,\log \frac{2N}{m}\big)\) flops and uses only \({\mathcal O}\big(m\,\log \frac{2N}{m}\big)\) samples. This algorithm employs an efficient sparse deterministic inverse fast Fourier transform that reconstructs a vector \({\mathbf y} \in {\mathbb R}^{2N}\) with reflected block support of length \(m\) from the discrete Fourier transform \(\hat{\mathbf y}\) of \({\mathbf y}\) with the same computational cost and sampling complexity as the algorithm for the inverse DCT-II. The computational cost and numerical stability of both algorithms are illustrated by numerical experiments.