Sparse fast DCT for vectors with one-block support

DOI10.1007/S11075-018-0620-1MaRDI QIDQ2274167zbMATH OpenOpenAlexFDO

Publication date 19 September 2019

Published in Numerical Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.05207

computational cost deterministic sparse fast algorithm discrete cosine transform inverse DCT-II inverse discrete cosine transform of type II one-block support sampling complexity sparse inverse fast Fourier transform

Mathematics Subject Classification ID

Numerical methods for discrete and fast Fourier transforms (65T50) Complexity and performance of numerical algorithms (65Y20) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: In this paper we present a new fast and deterministic algorithm for the inverse discrete cosine transform of type II that reconstructs the input vector

m a t h b f x i n m a t h b b R^{N}

,

N = 2^{J - 1}

, with short support of length

m

from its discrete cosine transform

m a t h b f x^{w i d e h a t m a t h r m I I} = m a t h b f C_{N}^{m a t h r m I I} m a t h b f x

. The resulting algorithm has a runtime of

m a t h c a l O l e f t (m l o g m l o g f r a c 2 N m i g h t)

and requires

m a t h c a l O l e f t (m l o g f r a c 2 N m i g h t)

samples of

m a t h b f x^{w i d e h a t m a t h r m I I}

. In order to derive this algorithm we also develop a new fast and deterministic inverse FFT algorithm that constructs the input vector

m a t h b f y i n m a t h b b R^{2 N}

with reflected block support of block length

m

from

w i d e h a t m a t h b f y

with the same runtime and sampling complexities as our DCT algorithm.

Review text

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.

Recommendations

Cites work

Cited in

(8)

Describes a project that uses

Uses Software

This page was built for publication: Sparse fast DCT for vectors with one-block support

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2274167)