Combinatorial sublinear-time Fourier algorithms

DOI10.1007/s10208-009-9057-1zbMath1230.65145OpenAlexW2031425559WikidataQ60204986 ScholiaQ60204986MaRDI QIDQ972615

Mark A. Iwen

Publication date: 21 May 2010

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10208-009-9057-1

zbMATH Keywords

discrete Fourier transformcompressed sensingparameter recoverytrigonometric approximationsparse trigonometric polynomialChinese Remainder Theoremdeterministic Fourier algorithmnumber theoretic group testing methodsrandomized Fourier algorithmsublinear runtime

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Numerical methods for discrete and fast Fourier transforms (65T50) Numerical methods for trigonometric approximation and interpolation (65T40)

Related Items (37)

System identification in dynamical sampling ⋮ A deterministic sparse FFT algorithm for vectors with small support ⋮ Improved sparse Fourier approximation results: Faster implementations and stronger guarantees ⋮ Sparse high-dimensional FFT based on rank-1 lattice sampling ⋮ Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods ⋮ Explicit universal sampling sets in finite vector spaces ⋮ Sketching with Kerdock's Crayons: Fast Sparsifying Transforms for Arbitrary Linear Maps ⋮ Parameter estimation for nonincreasing exponential sums by Prony-like methods ⋮ Strengthening hash families and compressive sensing ⋮ 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 ⋮ A hierarchical framework for recovery in compressive sensing ⋮ Deterministic sampling of sparse trigonometric polynomials ⋮ Detecting the large entries of a sparse covariance matrix in sub-quadratic time ⋮ Stochastic Collocation vial₁-Minimisation on Low Discrepancy Point Sets with Application to Uncertainty Quantification ⋮ Deterministic sparse FFT for \(M\)-sparse vectors ⋮ Rapidly computing sparse Legendre expansions via sparse Fourier transforms ⋮ Spectral compressive sensing ⋮ A deterministic sparse FFT for functions with structured Fourier sparsity ⋮ Superfast Fourier transform using QTT approximation ⋮ 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 ⋮ What's the frequency, Kenneth?: sublinear Fourier sampling off the grid ⋮ 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 ⋮ Unnamed Item ⋮ Theory and applications of compressed sensing ⋮ 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 multiscale sub-linear time Fourier algorithm for noisy data ⋮ A sparse fast Fourier algorithm for real non-negative vectors

Uses Software

• FFTW

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorics of random processes and sections of convex bodies
• Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
• Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit
• The type 3 nonuniform FFT and its applications
• Deterministic constructions of compressed sensing matrices
• Empirical evaluation of a sub-linear time sparse DFT algorithm
• Compressed sensing and best 𝑘-term approximation
• A Sparse Spectral Method for Homogenization Multiscale Problems
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
• Near-optimal sparse fourier representations via sampling
• Combinatorial Algorithms for Compressed Sensing
• Fast Fourier Transforms for Nonequispaced Data
• Randomized Interpolation and Approximation of Sparse Polynomials
• Rapid Computation of the Discrete Fourier Transform
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Nonuniform fast fourier transforms using min-max interpolation
• Algorithms and Data Structures
• Stable signal recovery from incomplete and inaccurate measurements
• Compressed sensing

This page was built for publication: Combinatorial sublinear-time Fourier algorithms