Simple and practical algorithm for sparse Fourier transform
Explore this paper's citation graph
Summary
This work considers the sparse Fourier transform problem, and proposes a new algorithm, which leverages techniques from digital signal processing, notably Gaussian and Dolph-Chebyshev filters, and is faster than FFT, both in theory and practice.
- Type
- article
- Published
- 2012-01-17
- Cited by
- 385
- References
- 28
- Access
- Open access
- OpenAlex
- https://openalex.org/W1494749725
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:114188
Keywords
Algorithm, Fast Fourier transform, Discrete cosine transform, Signal processing, Discrete Fourier transform (general)
References
- Deterministic Sparse Fourier Approximation via Fooling Arithmetic Progressions.
- Compressed Sensing
- Improved Approximation Guarantees for Sublinear-Time Fourier Algorithms
- Some topics in analysis of boolean functions
- Randomized Interpolation and Approximation of Sparse Polynomials
- Discrete-Time Signal Pro-cessing
- A Sparse Spectral Method for Homogenization Multiscale Problems
- Sparse Recovery Using Sparse Matrices
- Improved time bounds for near-optimal sparse Fourier representations
- Empirical evaluation of a sub-linear time sparse DFT algorithm
- Combinatorial Algorithms for Compressed Sensing
- Near-optimal sparse fourier representations via sampling
- Combinatorial Sublinear-Time Fourier Algorithms
- Constant depth circuits, Fourier transform, and learnability
- A New Flexible Filter Bank for Low Complexity Spectrum Sensing in Cognitive Radios
- Learning decision trees using the Fourier spectrum
- Fast approximate correlation for massive time-series data
- The influence of variables on Boolean functions
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- A Tutorial on Fast Fourier Sampling
Cited by
- Computing the fast Fourier transform on SIMD microprocessors
- Sublinear Time Algorithms for the Sparse Recovery Problem
- High Dimensional Fast Fourier Transform Based on Rank-1 Lattice Sampling
- On the computational power of quantum computers
- Sparse Encoding of Signals through Structured Random Sampling
- Methods of Music Classification and Transcription
- Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time
- Fast multi-dimensional NMR acquisition and processing using the sparse FFT
- Sparse high-dimensional FFT based on rank-1 lattice sampling
- A fast algorithm for multi-component LFM signal analysis exploiting segmented DPT and SDFrFT
- Adaptive sub-linear Fourier algorithms
- Sparse Fast Fourier Transform for Exactly and Generally K-Sparse Signals by Downsampling and Sparse Recovery
- BigBand: GHz-Wide Sensing and Decoding on Commodity Radios
- Sub-Nyquist rate wideband spectrum sensing over TV white space for M2M communications
- Volumetric Data Reduction in a Compressed Sensing Framework
- A deterministic sparse FFT algorithm for vectors with small support
- Matrix probing, skeleton decompositions, and sparse Fourier transform
- Object recognition based on reconstruction of light field
- Data-Based Statistical Property Analyzing and Storage Sizing for Hybrid Renewable Energy Systems
- Efficient Software Implementation of the Nearly Optimal Sparse Fast Fourier Transform for the Noisy Case
Related papers
- On the odd-DFT and its applications to DCT/IDCT computation
- Computation of the discrete cosine transform via the arcsine transform
- New algorithm for the calculation of the Fourier transform of discrete signals
- Comparison & Performance Evaluation of Several Types of ECG Compression Techniques
- Nonuniform fast cosine transform and the Chebyshev PSTD algorithm
- Number theoretic techniques applied to algorithms and architectures for digital signal processing
- An expanded 2D DCT algorithm based on convolution
- FFT based Interval Arithmetic Analysis for Signal Processing System