Combinatorial sublinear-time Fourier algorithms
type: Item
instance of: scholarly article
title: Combinatorial sublinear-time Fourier algorithms
zbMATH Open document ID: 1230.65145
published in: Foundations of Computational Mathematics
publication date: 2010-05-21T00:00:00Z
review text: Let \(f\) be a sufficiently smooth \(2\pi\)-periodic function which is well approximated by a \(k\)-sparse trigonometric polynomial \[ {\tilde f}(x) = \sum_{j=1}^k c_j\, \exp ({\mathrm i}\, \omega_j\, x) \] with integer frequencies \(\omega_j \in [-N/2,\, N/2]\) and complex coefficients \(c_j \neq 0\), where the smallest possible \(N\) is much larger than \(k\). The aim is the efficient recovery of all parameters \(\omega_j\), \(c_j\) \((j=1,\ldots, k)\) using as few sampled values of \(f\) as possible. Compressed sensing methods provide a robust framework for reducing the number of samples. In this interesting paper, the author presents a novel fast algorithm of deterministic parameter recovery. The main result is a Fourier algorithm which has runtime \({\mathcal O}(k^2\,(\log N)^4)\) and requires \({\mathcal O}(k^2\, (\log N)^3)\) sampled values of \(f\). This new Fourier algorithm is based on several discrete Fourier transforms of small lengths and uses number theoretic group testing methods and the Chinese Remainder Theorem. A simple relaxation of this deterministic method provides a new randomized Fourier algorithm which has sublinear runtime \({\mathcal O}(k\,(\log N)^5)\) and requires \({\mathcal O}(k\, (\log N)^4)\) sampled values of \(f\). Numerical tests show the performance of the deterministic Fourier algorithm.
reviewed by: Manfred Tasche
Mathematics Subject Classification ID: 65T50
Mathematics Subject Classification ID: 65T40
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 94A12
zbMATH DE Number: 5710613
zbMATH Keywords: discrete Fourier transform
zbMATH Keywords: trigonometric approximation
zbMATH Keywords: deterministic Fourier algorithm
zbMATH Keywords: sparse trigonometric polynomial
zbMATH Keywords: compressed sensing
zbMATH Keywords: parameter recovery
zbMATH Keywords: sublinear runtime
zbMATH Keywords: randomized Fourier algorithm
zbMATH Keywords: Chinese Remainder Theorem
zbMATH Keywords: number theoretic group testing methods
Wikidata QID: Q60204986
describes a project that uses: FFTW
author: M. A. Iwen
MaRDI profile type: Publication
full work available at URL: s10208-009-9057-1
OpenAlex ID: W2031425559
cites work: Rapid Computation of the Discrete Fourier Transform
cites work: Chebyshev and Fourier spectral methods.
cites work: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
cites work: Stable signal recovery from incomplete and inaccurate measurements
cites work: Q4515159
cites work: Compressed sensing and best 𝑘-term approximation
cites work: An Algorithm for the Machine Calculation of Complex Fourier Series
cites work: Q3619797
cites work: Combinatorial Algorithms for Compressed Sensing
cites work: A Sparse Spectral Method for Homogenization Multiscale Problems
cites work: Deterministic constructions of compressed sensing matrices
cites work: Compressed sensing
cites work: Q4857782
cites work: Fast Fourier Transforms for Nonequispaced Data
cites work: Algorithms and Data Structures
cites work: Nonuniform fast fourier transforms using min-max interpolation
cites work: Q3138785
cites work: Near-optimal sparse fourier representations via sampling
cites work: Q4829004
cites work: Q3579464
cites work: Q3579463
cites work: Empirical evaluation of a sub-linear time sparse DFT algorithm
cites work: Q3126966
cites work: Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit
cites work: The type 3 nonuniform FFT and its applications
cites work: Q4839061
cites work: Randomized Interpolation and Approximation of Sparse Polynomials
cites work: Q4856179
cites work: Q3425115
cites work: Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
cites work: Q4001741
cites work: Combinatorics of random processes and sections of convex bodies
cites work: Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
DOI: 10.1007/S10208-009-9057-1
description: scientific article; zbMATH DE number 5710613