Real sparse fast DCT for vectors with short support

DOI10.1016/J.LAA.2019.08.006zbMATH Open1464.65296arXiv1807.07397OpenAlexW2968831792MaRDI QIDQ2332391FDOQ2332391

Authors: Sina Bittens, Gerlind Plonka 

Publication date: 4 November 2019

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

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$.

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

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

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)

Cites Work

• Sparse fast DCT for vectors with one-block support
• A deterministic sparse FFT algorithm for vectors with small support
• A multiscale sub-linear time Fourier algorithm for noisy data
• Deterministic Sparse Fourier Approximation Via Approximating Arithmetic Progressions
• Combinatorial sublinear-time Fourier algorithms
• Improved approximation guarantees for sublinear-time Fourier algorithms
• Fast and numerically stable algorithms for discrete cosine transforms
• Fast algorithms for the discrete W transform and for the discrete Fourier transform
• Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
• A sparse fast Fourier algorithm for real non-negative vectors
• Deterministic sparse FFT for \(M\)-sparse vectors
• Title not available (Why is that?)
• A deterministic sparse FFT for functions with structured Fourier sparsity
• Real sparse fast DCT for vectors with short 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

Uses Software

• Matlab
• Sparse FFT small support
• DCT_shortsupp_oneblock
• idct

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)