Nearly optimal sparse fourier transform
From MaRDI portal
Publication:5415501
DOI10.1145/2213977.2214029zbMath1286.94046arXiv1201.2501OpenAlexW2107625832WikidataQ60204976 ScholiaQ60204976MaRDI QIDQ5415501
Haitham Hassanieh, Dina Katabi, Eric Price, Piotr Indyk
Publication date: 13 May 2014
Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1201.2501
Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42B10) Randomized algorithms (68W20) Sampling theory in information and communication theory (94A20)
Related Items (27)
A deterministic sparse FFT algorithm for vectors with small support ⋮ Faster sparse multivariate polynomial interpolation of straight-line programs ⋮ Sparse high-dimensional FFT based on rank-1 lattice sampling ⋮ Reconstruction of sparse Legendre and Gegenbauer expansions ⋮ 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 ⋮ Detecting the large entries of a sparse covariance matrix in sub-quadratic time ⋮ Applications of classical approximation theory to periodic basis function networks and computational harmonic analysis ⋮ Time series joins, motifs, discords and shapelets: a unifying view that exploits the matrix profile ⋮ Deterministic sparse FFT for \(M\)-sparse vectors ⋮ Rapidly computing sparse Legendre expansions via sparse Fourier transforms ⋮ A deterministic sparse FFT for functions with structured Fourier sparsity ⋮ Sparse polynomial interpolation: sparse recovery, super-resolution, or Prony? ⋮ Superfast Fourier transform using QTT approximation ⋮ High-dimensional sparse Fourier algorithms ⋮ Unnamed Item ⋮ The partial fast Fourier transform ⋮ Vibration analysis of cyclic symmetrical systems by quantum algorithms ⋮ What's the frequency, Kenneth?: sublinear Fourier sampling off the grid ⋮ Quantum learning of concentrated Boolean functions ⋮ Approximation of multivariate periodic functions by trigonometric polynomials based on rank-1 lattice sampling ⋮ A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions ⋮ A multiscale sub-linear time Fourier algorithm for noisy data ⋮ A sparse fast Fourier algorithm for real non-negative vectors
This page was built for publication: Nearly optimal sparse fourier transform
