Combinatorial sublinear-time Fourier algorithms (Q972615)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Combinatorial sublinear-time Fourier algorithms
scientific article

    Statements

    Combinatorial sublinear-time Fourier algorithms (English)
    0 references
    21 May 2010
    0 references
    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.
    0 references
    discrete Fourier transform
    0 references
    trigonometric approximation
    0 references
    deterministic Fourier algorithm
    0 references
    sparse trigonometric polynomial
    0 references
    compressed sensing
    0 references
    parameter recovery
    0 references
    sublinear runtime
    0 references
    randomized Fourier algorithm
    0 references
    Chinese Remainder Theorem
    0 references
    number theoretic group testing methods
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references