Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis.

*(English)*Zbl 1085.65128This excellent paper greatly improves the previous randomized algorithm for sparse Fourier analysis proposed by A. C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan and M. Strauss, Near-optimal sparse Fourier representations via sampling, Proc. Thirty-Fourth Annual ACM Symp. on Theory of Computing, 152–161 (2002)]. Several novel ideas and techniques to speed up the algorithm, as well as rigorous and heuristic arguments for choosing parameters, are presented. The approach to higher dimensional cases is also introduced and demonstrated. Various experiments, even with different levels of noise are given in details. The time and spatial complexity are analyzed. Almost all the results given here outperform than previous results, thus a wide range of applications can be expected, based on the important progress proposed in this paper.

Reviewer: Qiao Wang (Nanjing)

##### MSC:

65T50 | Numerical methods for discrete and fast Fourier transforms |

65T40 | Numerical methods for trigonometric approximation and interpolation |

68W20 | Randomized algorithms |

42A10 | Trigonometric approximation |

##### Keywords:

sparse Fourier representation; Fast Fourier transform; sublinear algorithm; randomized algorithm; numerical examples; complexity##### Software:

FFTW
PDF
BibTeX
XML
Cite

\textit{J. Zou} et al., J. Comput. Phys. 211, No. 2, 572--595 (2006; Zbl 1085.65128)

Full Text:
DOI

##### References:

[1] | Bensoussan, A.; Lions, P.L.; Papanicolaou, G., Asymptotic analysis for periodic structures, (1978), North-Holland Publ. Co. The Netherlands · Zbl 0411.60078 |

[2] | Frigo, M.; Johnson, S.G., The design and implementation of FFTW3, Proceedings of the IEEE, 93, 2, 216-231, (2005), Special Issue on Program Generation, Optimization, and Platform Adaptation |

[3] | A.C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. Strauss, Near-Optimal Sparse Fourier Representations via Sampling, STOC, 2002. · Zbl 1192.94078 |

[4] | A.C. Gilbert, S. Muthukrishnan, M. Strauss, Improved Time Bounds for Near-Optimal Sparse Fourier Representation, in: Wavelets XI Conference in the SPIE Symposium on Optics and Photonics, San Diego, California, USA (to appear). |

[5] | Mansour, Y., Randomized interpolation and approximation of sparse polynomials, SIAM journal on computing, 24, 2, (1995) · Zbl 0826.65005 |

[6] | Mansour, Y.; Sahar, S., Implementation issues in the Fourier transform algorithm, Nerual information processing systems, 260-265, (1995), [Machine Learning Journal 40 (1) 2000 5-33] |

[7] | O. Runborg, Private communication, 2002. |

[8] | Weaver, H.J., Applications of discrete and continuous Fourier analysis, (1983), Wiley · Zbl 0588.42002 |

[9] | J. Zou, I. Daubechies, O. Runborg, A Sublinear Spectral Method for Multiscale Problems (in press). · Zbl 1152.65099 |

[10] | J. Zou, Sublinear Algorithms for the Fourier Transform of Signals with very few Fourier modes: theory, implementations and applications, Ph.D. Thesis, Princeton University, July 2005. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.