Real sparse fast DCT for vectors with short support

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

Authors Sina Bittens, Gerlind Plonka

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

zbMATH Keywords

discrete cosine transformsampling complexityreal arithmeticsublinear runtimedeterministic sparse fast algorithminverse DCT of type IIvector with short support

Mathematics Subject Classification ID

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

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 $mathbfxinmathbb{R}^N$, $N=2^J$, with short support of length $m$ from its discrete cosine transform $mathbf{x}^{widehatmathrmII}=C_N^{mathrmII}mathbfx$ if an upper bound $Mgeqm$ is known. The resulting algorithm only uses real arithmetic, has a runtime of $mathcalOleft(MlogM+mlo{g}_{2}fracNMight)$ and requires $mathcalOleft(M+mlo{g}_{2}fracNMight)$ samples of $mathbf{x}^{widehatmathrmII}$. For $m,MightarrowN$ 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 $mathbfx$.

Recommendations

• Sparse fast DCT for vectors with one-block support
• Deterministic sparse FFT for M-sparse vectors
• A deterministic sparse FFT algorithm for vectors with small support
• Sparse fast trigonometric transforms
• scientific article; zbMATH DE number 24367

Cites work

• scientific article; zbMATH DE number 6770709 (Why is no real title available?)
• A deterministic sparse FFT algorithm for vectors with small support
• A deterministic sparse FFT for functions with structured Fourier sparsity
• A multiscale sub-linear time Fourier algorithm for noisy data
• A sparse fast Fourier algorithm for real non-negative vectors
• Combinatorial sublinear-time Fourier algorithms
• Deterministic Sparse Fourier Approximation Via Approximating Arithmetic Progressions
• Deterministic sparse FFT for M-sparse vectors
• Fast algorithms for the discrete W transform and for the discrete Fourier transform
• Fast and numerically stable algorithms for discrete cosine transforms
• Improved approximation guarantees for sublinear-time Fourier algorithms
• Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
• Real sparse fast DCT for vectors with short support
• Sparse fast DCT for vectors with one-block support

Cited in

(8)

• Sparse fast trigonometric transforms
• Sparse fast DCT for vectors with one-block support
• Deterministic sparse FFT for M-sparse vectors
• Deterministic sparse sublinear FFT with improved numerical stability
• Real sparse fast DCT for vectors with short support
• A deterministic sparse FFT algorithm for vectors with small support
• A sparse fast Fourier algorithm for real non-negative vectors
• Sparse Fourier transforms on rank-1 lattices for the rapid and low-memory approximation of functions of many variables

Describes a project that uses

Uses Software

• idct
• DCT_shortsupp_oneblock
• Sparse FFT small support
• Matlab

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)