Document Open Access Logo

Estimating the Frequency of a Clustered Signal

Authors Xue Chen, Eric Price

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.36.pdf
  • Filesize: 0.55 MB
  • 13 pages

Document Identifiers

Author Details

Xue Chen
  • Northwestern University, Evanston, IL, USA
Eric Price
  • The University of Texas at Austin, USA

Funding

  • Chen, Xue: Supported by research funding from Northwestern University. Part of this work was done while the author was in the University of Texas at Austin supported by NSF Grant CCF-1526952 and a Simons Investigator Award (#409864, David Zuckerman).
  • Price, Eric: Supported in part by NSF Award CCF-1751040 (CAREER).

Acknowledgements

We thank Daniel Kane and Zhao Song for many helpful discussions. We also thank the anonymous referee for the detailed feedback and comments.

Cite As Get BibTex

Xue Chen and Eric Price. Estimating the Frequency of a Clustered Signal. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 36:1-36:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.36

Abstract

We consider the problem of locating a signal whose frequencies are "off grid" and clustered in a narrow band. Given noisy sample access to a function g(t) with Fourier spectrum in a narrow range [f_0 - Delta, f_0 + Delta], how accurately is it possible to identify f_0? We present generic conditions on g that allow for efficient, accurate estimates of the frequency. We then show bounds on these conditions for k-Fourier-sparse signals that imply recovery of f_0 to within Delta + O~(k^3) from samples on [-1, 1]. This improves upon the best previous bound of O(Delta + O~(k^5))^{1.5}. We also show that no algorithm can do better than Delta + O~(k^2).
In the process we provide a new O~(k^3) bound on the ratio between the maximum and average value of continuous k-Fourier-sparse signals, which has independent application.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • sublinear algorithms
  • Fourier transform

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. A. Akavia, S. Goldwasser, and S. Safra. Proving hard-core predicates using list decoding. FOCS, 44:146-159, 2003. Google Scholar
  2. Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh. A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms. In Proceedings of the 51st annual ACM symposium on Theory of computing (STOC 2019), 2019. URL: http://arxiv.org/abs/1812.08723.
  3. Y. Bresler and A. Macovski. Exact maximum likelihood parameter estimation of superimposed exponential signals in noise. IEEE Transactions on Acoustics, Speech, and Signal Processing, 34(5):1081-1089, October 1986. URL: http://dx.doi.org/10.1109/TASSP.1986.1164949.
  4. Xue Chen, Daniel M. Kane, Eric Price, and Zhao Song. Fourier-sparse interpolation without a frequency gap. In Foundations of Computer Science(FOCS), 2016 IEEE 57th Annual Symposium on, 2016. URL: http://arxiv.org/abs/1609.01361.
  5. Xue Chen and Eric Price. Active Regression via Linear-Sample Sparsification. In the 32nd Annual Conference on Learning Theory (COLT 2019), 2019. Google Scholar
  6. Herman Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics, 23:493-507, 1952. Google Scholar
  7. Anna C Gilbert, Sudipto Guha, Piotr Indyk, S Muthukrishnan, and Martin Strauss. Near-optimal sparse Fourier representations via sampling. In Proceedings of the thirty-fourth annual ACM symposium on Theory of computing, pages 152-161. ACM, 2002. Google Scholar
  8. Anna C Gilbert, S Muthukrishnan, and Martin Strauss. Improved time bounds for near-optimal sparse Fourier representations. In Optics &Photonics 2005, pages 59141A-59141A. International Society for Optics and Photonics, 2005. Google Scholar
  9. Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price. Simple and practical algorithm for sparse Fourier transform. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1183-1194. SIAM, 2012. Google Scholar
  10. Piotr Indyk and Michael Kapralov. Sample-Optimal Fourier Sampling in Any Constant Dimension. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages 514-523. IEEE, 2014. Google Scholar
  11. Y. Mansour. Randomized Interpolation and Approximation of Sparse Polynomials. ICALP, 1992. Google Scholar
  12. Ankur Moitra. The threshold for super-resolution via extremal functions. In STOC, 2015. Google Scholar
  13. Eric Price and Zhao Song. A Robust Sparse Fourier Transform in the Continuous Setting. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 583-600. IEEE, 2015. Google Scholar
  14. R Prony. Essai experimental et analytique. J. de l’Ecole Polytechnique, 1795. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact