Combinatorial sublinear-time Fourier algorithms

DOI10.1007/S10208-009-9057-1zbMATH Open1230.65145OpenAlexW2031425559WikidataQ60204986 ScholiaQ60204986MaRDI QIDQ972615FDOQ972615

Authors: M. 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

Recommendations

• Nearly optimal sparse Fourier transform
• (Nearly) sample-optimal sparse Fourier transform
• Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
• Improved approximation guarantees for sublinear-time Fourier algorithms
• What's the frequency, Kenneth?: Sublinear Fourier sampling off the grid

zbMATH Keywords

compressed sensingparameter recoverydiscrete Fourier transformtrigonometric approximationsparse trigonometric polynomialChinese Remainder Theoremdeterministic Fourier algorithmnumber theoretic group testing methodsrandomized Fourier algorithmsublinear runtime

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (47)

• A note on the high-dimensional sparse Fourier transform in the continuous setting
• Title not available (Why is that?)
• A multiscale sub-linear time Fourier algorithm for noisy data
• Nonlinear approximation in bounded orthonormal product bases
• Sparse fast DCT for vectors with one-block support
• A deterministic algorithm for constructing multiple rank-1 lattices of near-optimal size
• A deterministic sparse FFT for functions with structured Fourier sparsity
• A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions
• Parameter estimation for nonincreasing exponential sums by Prony-like methods
• A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees
• Deterministic sparse FFT for \(M\)-sparse vectors
• Spectral compressive sensing
• Detecting the large entries of a sparse covariance matrix in sub-quadratic time
• Theory and applications of compressed sensing
• High-dimensional sparse Fourier algorithms
• Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
• Sparse Fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time
• What's the frequency, Kenneth?: Sublinear Fourier sampling off the grid
• Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables
• Nearly optimal sparse Fourier transform
• Sketching with Kerdock's crayons: fast sparsifying transforms for arbitrary linear maps
• An adaptive sublinear-time block sparse Fourier transform
• Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares
• Deterministic sparse sublinear FFT with improved numerical stability
• Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time
• A sublinear algorithm for the recovery of signals with sparse Fourier transform when many samples are missing
• On the design of deterministic matrices for fast recovery of Fourier compressible functions
• What's the frequency, Kenneth?: sublinear Fourier sampling off the grid
• Sparse high-dimensional FFT based on rank-1 lattice sampling
• Improved approximation guarantees for sublinear-time Fourier algorithms
• Real sparse fast DCT for vectors with short support
• (Nearly) sample-optimal sparse Fourier transform
• Empirical evaluation of a sub-linear time sparse DFT algorithm
• Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods
• System identification in dynamical sampling
• A deterministic sparse FFT algorithm for vectors with small support
• Stochastic Collocation vial₁-Minimisation on Low Discrepancy Point Sets with Application to Uncertainty Quantification
• Performance of the multiscale sparse fast Fourier transform algorithm
• A sparse fast Fourier algorithm for real non-negative vectors
• Two subspace methods for frequency sparse graph signals
• Superfast Fourier transform using QTT approximation
• Explicit universal sampling sets in finite vector spaces
• Sparse Fourier transforms on rank-1 lattices for the rapid and low-memory approximation of functions of many variables
• A hierarchical framework for recovery in compressive sensing
• Strengthening hash families and compressive sensing
• Deterministic sampling of sparse trigonometric polynomials
• Rapidly computing sparse Legendre expansions via sparse Fourier transforms

Uses Software

• FFTW

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q972615)