Improved approximation guarantees for sublinear-time Fourier algorithms

DOI10.1016/J.ACHA.2012.03.007zbMath1260.65115arXiv1010.0014OpenAlexW1522894866WikidataQ60204978 ScholiaQ60204978MaRDI QIDQ1762319

Mark A. Iwen

Publication date: 23 November 2012

Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)

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

zbMATH Keywords

signal recoveryfast Fourier transformsFourier analysisapproximation algorithmstrigonometric approximation

Mathematics Subject Classification ID

Trigonometric approximation (42A10) Numerical methods for discrete and fast Fourier transforms (65T50) Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42A38) Numerical methods for trigonometric approximation and interpolation (65T40)

Related Items (26)

System identification in dynamical sampling ⋮ A deterministic sparse FFT algorithm for vectors with small support ⋮ Sparse high-dimensional FFT based on rank-1 lattice sampling ⋮ High-dimensional sparse FFT based on sampling along multiple rank-1 lattices ⋮ Sketching with Kerdock's Crayons: Fast Sparsifying Transforms for Arbitrary Linear Maps ⋮ Performance of the multiscale sparse fast Fourier transform algorithm ⋮ Nonlinear approximation in bounded orthonormal product bases ⋮ A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees ⋮ Deterministic sparse FFT for \(M\)-sparse vectors ⋮ Rapidly computing sparse Legendre expansions via sparse Fourier transforms ⋮ Compressed sensing with sparse binary matrices: instance optimal error guarantees in near-optimal time ⋮ A deterministic sparse FFT for functions with structured Fourier sparsity ⋮ High-dimensional sparse Fourier algorithms ⋮ Sparse fast DCT for vectors with one-block support ⋮ Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables ⋮ Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time ⋮ Deterministic sparse sublinear FFT with improved numerical stability ⋮ A deterministic algorithm for constructing multiple rank-1 lattices of near-optimal size ⋮ Sparse Fourier transforms on rank-1 lattices for the rapid and low-memory approximation of functions of many variables ⋮ Real sparse fast DCT for vectors with short support ⋮ Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares ⋮ The uniform sparse FFT with application to PDEs with random coefficients ⋮ Unnamed Item ⋮ A note on the high-dimensional sparse Fourier transform in the continuous setting* ⋮ A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions ⋮ A sparse fast Fourier algorithm for real non-negative vectors

This page was built for publication: Improved approximation guarantees for sublinear-time Fourier algorithms