Improved sparse Fourier approximation results: Faster implementations and stronger guarantees

DOI10.1007/s11075-012-9621-7zbMath1276.65097OpenAlexW1977453732MaRDI QIDQ2376358

Ben Segal, Mark A. Iwen

Publication date: 21 June 2013

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

Full work available at URL: https://doi.org/10.1007/s11075-012-9621-7

zbMATH Keywords

numerical examplesfast Fourier transformsMonte Carlo algorithmrandomized algorithmssparse Fourier approximationFourier series coefficients

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Numerical methods for discrete and fast Fourier transforms (65T50) Numerical methods for trigonometric approximation and interpolation (65T40) Fourier coefficients, Fourier series of functions with special properties, special Fourier series (42A16)

Related Items

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, A deterministic sparse FFT for functions with structured Fourier sparsity, 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

Uses Software

• FFTW
• CoSaMP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Iterative hard thresholding for compressed sensing
• Combinatorial sublinear-time Fourier algorithms
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
• Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit
• Empirical evaluation of a sub-linear time sparse DFT algorithm
• On the Design of Deterministic Matrices for Fast Recovery of Fourier Compressible Functions
• Deterministic Sparse Fourier Approximation Via Approximating Arithmetic Progressions
• Compressed sensing and best 𝑘-term approximation
• On sparse reconstruction from Fourier and Gaussian measurements
• A Sparse Spectral Method for Homogenization Multiscale Problems
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
• Near-optimal sparse fourier representations via sampling
• Combinatorial Algorithms for Compressed Sensing
• Learning Decision Trees Using the Fourier Spectrum
• Fast Fourier Transforms for Nonequispaced Data
• Randomized Interpolation and Approximation of Sparse Polynomials
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Stable signal recovery from incomplete and inaccurate measurements
• Compressed sensing