Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
From MaRDI portal
Publication:2376358
DOI10.1007/s11075-012-9621-7zbMath1276.65097MaRDI QIDQ2376358
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
numerical examples; fast Fourier transforms; Monte Carlo algorithm; randomized algorithms; sparse Fourier approximation; Fourier series coefficients
65C05: Monte Carlo methods
65T50: Numerical methods for discrete and fast Fourier transforms
65T40: Numerical methods for trigonometric approximation and interpolation
42A16: Fourier coefficients, Fourier series of functions with special properties, special Fourier series
Related Items
Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares, Nonlinear approximation in bounded orthonormal product bases, Rapidly computing sparse Legendre expansions via sparse Fourier transforms, Deterministic sparse FFT for \(M\)-sparse vectors, A deterministic sparse FFT for functions with structured Fourier sparsity, 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, Sparse fast DCT for vectors with one-block support, Real sparse fast DCT for vectors with short support, A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees
Uses Software
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
