A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions

DOI10.1007/s11075-021-01162-1zbMath1491.65177arXiv2006.13053OpenAlexW3036122956MaRDI QIDQ2118948

Toni Volkmer, Lutz Kämmerer, Felix Krahmer

Publication date: 23 March 2022

Published in: Numerical Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

multivariate trigonometric polynomialsapproximation of multivariate functionslattice rulehigh-dimensional sparse fast Fourier transformmultiple rank-1 lattices

Mathematics Subject Classification ID

Trigonometric approximation (42A10) Numerical methods for discrete and fast Fourier transforms (65T50)

Related Items (2)

Sketching with Kerdock's Crayons: Fast Sparsifying Transforms for Arbitrary Linear Maps ⋮ Nonlinear approximation in bounded orthonormal product bases

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A multiscale sub-linear time Fourier algorithm for noisy data
• Sparse high-dimensional FFT based on rank-1 lattice sampling
• Combinatorial sublinear-time Fourier algorithms
• Time bounds for selection
• Explicit estimates of some functions over primes
• Multiple rank-1 lattices as sampling schemes for multivariate trigonometric polynomials
• Improved approximation guarantees for sublinear-time Fourier algorithms
• High-dimensional sparse Fourier algorithms
• 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
• Multiscale high-dimensional sparse Fourier algorithms for noisy data
• Approximation of multivariate periodic functions based on sampling along multiple rank-1 lattices
• Constructing spatial discretizations for sparse multivariate trigonometric polynomials that allow for a fast discrete Fourier transform
• Explicit universal sampling sets in finite vector spaces
• Parameter estimation for multivariate exponential sums
• High-dimensional sparse FFT based on sampling along multiple rank-1 lattices
• Nonequispaced Hyperbolic Cross Fast Fourier Transform
• On sparse reconstruction from Fourier and Gaussian measurements
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Near-optimal sparse fourier representations via sampling
• Combinatorial Algorithms for Compressed Sensing
• Stable and Robust Sampling Strategies for Compressive Imaging
• Sparse Multidimensional Exponential Analysis with an Application to Radar Imaging
• Sparsity and incoherence in compressive sampling
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Probability Inequalities for Sums of Bounded Random Variables
• Nearly optimal sparse fourier transform

This page was built for publication: A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions