Real sparse fast DCT for vectors with short support

DOI10.1016/J.LAA.2019.08.006MaRDI QIDQ2332391zbMATH OpenOpenAlexFDO

Publication date 4 November 2019

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

deterministic sparse fast algorithm discrete cosine transform inverse DCT of type II real arithmetic sampling complexity sublinear runtime vector with short support

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 for reconstructing the input vector

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

,

N = 2^{J}

, 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} = C_{N}^{m a t h r m I I} m a t h b f x

if an upper bound

M g e q m

is known. The resulting algorithm only uses real arithmetic, has a runtime of

m a t h c a l O l e f t (M l o g M + m l o g_{2} f r a c N M i g h t)

and requires

m a t h c a l O l e f t (M + m l o g_{2} f r a c 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}

. For

m, M i g h t a r r o w 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

m a t h b f x

.

Review text

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.

Recommendations

Cites work

Cited in

(8)

Describes a project that uses

Uses Software

This page was built for publication: Real sparse fast DCT for vectors with short support

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