{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,18]],"date-time":"2025-10-18T15:02:46Z","timestamp":1760799766289},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,7,22]],"date-time":"2014-07-22T00:00:00Z","timestamp":1405987200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,10]]},"DOI":"10.1007\/s00453-014-9918-0","type":"journal-article","created":{"date-parts":[[2014,7,21]],"date-time":"2014-07-21T11:54:00Z","timestamp":1405943640000},"page":"261-288","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["What\u2019s the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid"],"prefix":"10.1007","volume":"73","author":[{"given":"Petros","family":"Boufounos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Volkan","family":"Cevher","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anna C.","family":"Gilbert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yi","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin J.","family":"Strauss","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,7,22]]},"reference":[{"issue":"6","key":"9918_CR1","doi-asserted-by":"crossref","first-page":"959","DOI":"10.1109\/JPROC.2009.2038076","volume":"98","author":"R Baraniuk","year":"2010","unstructured":"Baraniuk, R., Cevher, V., Wakin, M.: Low-dimensional models for dimensionality reduction and signal recovery: a geometric perspective. Proc. IEEE 98(6), 959\u2013971 (2010)","journal-title":"Proc. IEEE"},{"issue":"8","key":"9918_CR2","doi-asserted-by":"crossref","first-page":"2567","DOI":"10.1016\/j.sigpro.2010.03.003","volume":"90","author":"K Chahine","year":"2010","unstructured":"Chahine, K., Baltazart, V., Wang, Y.: Interpolation-based matrix pencil method for parameter estimation of dispersive media in civil engineering. Signal Process. 90(8), 2567\u20132580 (2010)","journal-title":"Signal Process."},{"key":"9918_CR3","unstructured":"Chui, D.: Personal communication (2013)."},{"issue":"6","key":"9918_CR4","doi-asserted-by":"crossref","first-page":"937","DOI":"10.1109\/JPROC.2010.2045092","volume":"98","author":"A Gilbert","year":"2010","unstructured":"Gilbert, A., Indyk, P.: Sparse recovery using sparse matrices. Proc. IEEE 98(6), 937\u2013947 (2010)","journal-title":"Proc. IEEE"},{"issue":"2","key":"9918_CR5","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1137\/100816705","volume":"41","author":"A Gilbert","year":"2012","unstructured":"Gilbert, A., Li, Y., Porat, E., Strauss, M.: Approximate sparse recovery: optimizing time and measurements. SIAM J. Comput. 41(2), 436\u2013453 (2012)","journal-title":"SIAM J. Comput."},{"key":"9918_CR6","doi-asserted-by":"crossref","unstructured":"Gilbert, A.C., Guha, S., Indyk, P., Muthukrishnan, S., Strauss, M.: Near-optimal sparse Fourier representations via sampling. In: Proceedings of the thiry-fourth annual ACM Symposium on Theory of Computing. STOC \u201902, pp. 152\u2013161. ACM, New York (2002)","DOI":"10.1145\/509907.509933"},{"key":"9918_CR7","doi-asserted-by":"crossref","unstructured":"Gilbert, A.C., Muthukrishnan, S., Strauss, M.: Improved time bounds for near-optimal sparse Fourier representations. In: Proceedings of Wavelets XI conference, pp. 398\u2013412 (2005).","DOI":"10.1117\/12.615931"},{"key":"9918_CR8","doi-asserted-by":"crossref","unstructured":"Hassanieh, H., Indyk, P., Katabi, D., Price, E.: Nearly optimal sparse Fourier transform. In: Proceedings of the 44th Symposium on Theory of Computing, STOC \u201912, pp. 563\u2013578. ACM, New York (2012)","DOI":"10.1145\/2213977.2214029"},{"key":"9918_CR9","doi-asserted-by":"crossref","unstructured":"Hassanieh, H., Indyk, P., Katabi, D., Price, E.: Simple and practical algorithm for sparse Fourier transform. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201912, pp. 1183\u20131194. SIAM (2012).","DOI":"10.1137\/1.9781611973099.93"},{"key":"9918_CR10","unstructured":"Heider, S., Kunis, S., Potts, D., Veit, M.: A sparse Prony FFT. In: Proceedings of Tenth International Conference on Sampling Theory and Applications, SampTA 2013, pp. 572\u2013575 (2013)"},{"key":"9918_CR11","unstructured":"Helson, H.: Harmonic Analysis (2nd edn.). Hindustan Book Agency, New Delhi (1995)."},{"key":"9918_CR12","doi-asserted-by":"crossref","unstructured":"Hua, Y., Sarkar, T.: On SVD for estimating generalized eigenvalues of singular matrix pencil in noise. In: Proceedings of the IEEE Transactions on Signal Processing, vol. 39(4), pp. 892\u2013900 (1991)","DOI":"10.1109\/78.80911"},{"issue":"3","key":"9918_CR13","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/s10208-009-9057-1","volume":"10","author":"M Iwen","year":"2009","unstructured":"Iwen, M.: Combinatorial sublinear-time Fourier algorithms. Found. Comput. Math. 10(3), 303\u2013338 (2009)","journal-title":"Found. Comput. Math."},{"issue":"6","key":"9918_CR14","doi-asserted-by":"crossref","first-page":"1331","DOI":"10.1137\/0222080","volume":"22","author":"E Kushilevitz","year":"1993","unstructured":"Kushilevitz, E., Mansour, Y.: Learning decision trees using the Fourier spectrum. SIAM J. Comput. 22(6), 1331\u20131348 (1993)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9918_CR15","doi-asserted-by":"crossref","first-page":"1920","DOI":"10.1137\/100790094","volume":"33","author":"T Peter","year":"2011","unstructured":"Peter, T., Potts, D., Tasche, M.: Nonlinear approximation by sums of exponentials and translates. SIAM J. Sci. Comput. 33(4), 1920\u20131947 (2011)","journal-title":"SIAM J. Sci. Comput."},{"issue":"5","key":"9918_CR16","doi-asserted-by":"crossref","first-page":"1631","DOI":"10.1016\/j.sigpro.2009.11.012","volume":"90","author":"D Potts","year":"2010","unstructured":"Potts, D., Tasche, M.: Parameter estimation for exponential sums by approximate Prony method. Signal Process. 90(5), 1631\u20131642 (2010)","journal-title":"Signal Process."},{"key":"9918_CR17","doi-asserted-by":"crossref","unstructured":"Vetterli, M., Marziliano, P., Blu, T.: Sampling signals with finite rate of innovation. In: Proceedings of the IEEE Transactions on Signal Processing, vol. 50(6), pp. 1417\u20131428 (2002)","DOI":"10.1109\/TSP.2002.1003065"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9918-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9918-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9918-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,12]],"date-time":"2019-08-12T21:43:04Z","timestamp":1565646184000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9918-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7,22]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,10]]}},"alternative-id":["9918"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9918-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,7,22]]}}}