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