{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,5]],"date-time":"2025-04-05T10:40:10Z","timestamp":1743849610361,"version":"3.40.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,7,26]],"date-time":"2012-07-26T00:00:00Z","timestamp":1343260800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Numer Algor"],"published-print":{"date-parts":[[2013,6]]},"DOI":"10.1007\/s11075-012-9621-7","type":"journal-article","created":{"date-parts":[[2012,7,25]],"date-time":"2012-07-25T02:42:26Z","timestamp":1343184146000},"page":"239-263","source":"Crossref","is-referenced-by-count":16,"title":["Improved sparse fourier approximation results: faster implementations and stronger guarantees"],"prefix":"10.1007","volume":"63","author":[{"given":"Ben","family":"Segal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. A.","family":"Iwen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,7,26]]},"reference":[{"key":"9621_CR1","unstructured":"Akavia, A.: Deterministic sparse fourier approximation via fooling arithmetic progressions. In: 23rd Conference on Learning Theory (2010)"},{"key":"9621_CR2","doi-asserted-by":"crossref","unstructured":"Akavia, A., Goldwasser, S., Safra, S.: Proving hard-core predicates using list decoding. In: Annual Symposium on Foundations of Computer Science, vol. 44, pp.\u00a0146\u2013159 (2003)","DOI":"10.1109\/SFCS.2003.1238189"},{"issue":"1","key":"9621_CR3","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1137\/110835864","volume":"33","author":"J Bailey","year":"2012","unstructured":"Bailey, J., Iwen, M.A., Spencer, C.V.: On the design of deterministic matrices for fast recovery of fourier compressible functions. SIAM J. Matrix Anal. Appl. 33(1), 263\u2013289 (2012)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"3","key":"9621_CR4","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/j.acha.2009.04.002","volume":"27","author":"T Blumensath","year":"2009","unstructured":"Blumensath, T., Davies, M.E.: Iterative hard thresholding for compressed sensing. Appl. Comput. Harmon. Anal. 27(3), 265\u2013274 (2009)","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"9621_CR5","volume-title":"Chebyshev and Fourier Spectral Methods","author":"JP Boyd","year":"2001","unstructured":"Boyd, J.P.: Chebyshev and Fourier Spectral Methods. Dover, New York (2001)"},{"key":"9621_CR6","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1109\/TIT.2005.862083","volume":"52","author":"E Candes","year":"2006","unstructured":"Candes, E., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52, 489\u2013509 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"8","key":"9621_CR7","doi-asserted-by":"crossref","first-page":"1207","DOI":"10.1002\/cpa.20124","volume":"59","author":"E Candes","year":"2006","unstructured":"Candes, E., Romberg, J., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59(8), 1207\u20131223 (2006)","journal-title":"Commun. Pure Appl. Math."},{"issue":"12","key":"9621_CR8","doi-asserted-by":"crossref","first-page":"5406","DOI":"10.1109\/TIT.2006.885507","volume":"52","author":"E Candes","year":"2006","unstructured":"Candes, E., Tao, T.: Near optimal signal recovery from random projections: universal encoding strategies? IEEE Trans. Inf. Theory 52(12), 5406\u20135425 (2006)","journal-title":"Inf. Theory"},{"key":"9621_CR9","unstructured":"Chazelle, B.: The Discrepancy Method: Randomness and Complexity. Brooks\/Cole (1992)"},{"issue":"1","key":"9621_CR10","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1090\/S0894-0347-08-00610-3","volume":"22","author":"A Cohen","year":"2008","unstructured":"Cohen, A., Dahmen, W., DeVore, R.: Compressed sensing and best k-term approximation. J. Am. Math. Soc. 22(1), 211\u2013231 (2008)","journal-title":"J. Am. Math. Soc."},{"key":"9621_CR11","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1090\/S0025-5718-1965-0178586-1","volume":"19","author":"J Cooley","year":"1965","unstructured":"Cooley, J., Tukey, J.: An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19, 297\u2013301 (1965)","journal-title":"Math. Comput."},{"key":"9621_CR12","doi-asserted-by":"crossref","unstructured":"Cormode, G., Muthukrishnan, S.: Combinatorial algorithms for compressed sensing. In: Structural Information and Communication Complexity, pp. 280\u2013294 (2006)","DOI":"10.1007\/11780823_22"},{"issue":"3","key":"9621_CR13","doi-asserted-by":"crossref","first-page":"711","DOI":"10.1137\/060676258","volume":"6","author":"I Daubechies","year":"2007","unstructured":"Daubechies, I., Runborg, O., Zou, J.: A sparse spectral method for homogenization multiscale problems. Multiscale Model. Simul. 6(3), 711\u2012740 (2007)","journal-title":"Multiscale Model. Simul."},{"key":"9621_CR14","doi-asserted-by":"crossref","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","volume":"52","author":"D Donoho","year":"2006","unstructured":"Donoho, D.: Compressed sensing. IEEE Trans. Inf. Theory 52, 1289\u20131306 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9621_CR15","doi-asserted-by":"crossref","first-page":"1368","DOI":"10.1137\/0914081","volume":"14","author":"A Dutt","year":"1993","unstructured":"Dutt, A., Rokhlin, V.: Fast Fourier transforms for nonequispaced data. SIAM J. Sci. Comput. 14, 1368\u20131383 (1993)","journal-title":"SIAM J. Sci. Comput."},{"issue":"2","key":"9621_CR16","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1109\/JPROC.2004.840301","volume":"93","author":"M Frigo","year":"2005","unstructured":"Frigo, M., Johnson, S.: The design and implementation of fftw3. Proc. IEEE 93(2), 216\u2013231 (2005)","journal-title":"Proc. IEEE"},{"key":"9621_CR17","doi-asserted-by":"crossref","unstructured":"Gilbert, A., Guha, S., Indyk, P., Muthukrishnan, S., Strauss, M.: Near-optimal sparse Fourier estimation via sampling. In: ACM STOC, pp. 152\u2013161 (2002)","DOI":"10.1145\/509931.509933"},{"key":"9621_CR18","doi-asserted-by":"crossref","unstructured":"Gilbert, A., Muthukrishnan, S., Strauss, M.: Improved time bounds for near-optimal sparse Fourier representations. In: Proceedings of SPIE Wavelets XI (2005)","DOI":"10.1117\/12.615931"},{"issue":"2","key":"9621_CR19","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1109\/MSP.2007.915000","volume":"25","author":"A Gilbert","year":"2008","unstructured":"Gilbert, A., Strauss, M., Tropp, J.: A tutorial on fast fourier sampling. IEEE Signal Process. Mag. 25(2), 57\u201366 (2008)","journal-title":"IEEE Signal Process. Mag."},{"key":"9621_CR20","doi-asserted-by":"crossref","unstructured":"Gilbert, A.C., Strauss, M.J., Tropp, J.A., Vershynin, R.: One sketch for all: fast algorithms for compressed sensing. In: Proc. 39th ACM Symp. Theory of Computing (2007)","DOI":"10.1145\/1250790.1250824"},{"issue":"3","key":"9621_CR21","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/s10208-009-9057-1","volume":"10","author":"MA Iwen","year":"2010","unstructured":"Iwen, M.A.: Combinatorial sublinear-time fourier algorithms. Found. Comput. Math. 10(3), 303\u2013338 (2010)","journal-title":"Found. Comput. Math."},{"key":"9621_CR22","author":"MA Iwen","year":"2012","unstructured":"Iwen, M.A.: Improved approximation guarantees for sublinear-time Fourier algorithms. Appl. Comput. Harmon. Anal. (2012). doi: 10.1016\/j.acha.2012.03.007","journal-title":"Appl. Comput. Harmon. Anal."},{"issue":"4","key":"9621_CR23","doi-asserted-by":"crossref","first-page":"981","DOI":"10.4310\/CMS.2007.v5.n4.a13","volume":"5","author":"MA Iwen","year":"2007","unstructured":"Iwen, M.A., Gilbert, A.C., Strauss, M.J.: Empirical evaluation of a sub-linear time sparse DFT algorithm. Commun. Math. Sci. 5(4), 981\u2013998 (2007)","journal-title":"Commun. Math. Sci."},{"key":"9621_CR24","doi-asserted-by":"crossref","unstructured":"Kirolos, S., Laska, J., Wakin, M., Duarte, M., Baron, D., Ragheb, T., Massoud, Y., Baraniuk, R.: Analog-to-information conversion via random demodulation. In: Proc. IEEE Dallas Circuits and Systems Conference (2006)","DOI":"10.1109\/DCAS.2006.321036"},{"issue":"6","key":"9621_CR25","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1007\/s10208-007-9005-x","volume":"8","author":"S Kunis","year":"2008","unstructured":"Kunis, S., Rauhut, H.: Random sampling of sparse trigonometric polynomials II\u2014orthogonal matching pursuit versus basis pursuit. Found. Comput. Math. 8(6), 737\u2013763 (2008)","journal-title":"Found. Comput. Math."},{"issue":"6","key":"9621_CR26","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. SICOMP 22(6), 1331\u20131348 (1993)","journal-title":"SICOMP"},{"key":"9621_CR27","doi-asserted-by":"crossref","unstructured":"Laska, J., Kirolos, S., Massoud, Y., Baraniuk, R., Gilbert, A., Iwen, M., Strauss, M.: Random sampling for analog-to-information conversion of wideband signals. In: Proc. IEEE Dallas Circuits and Systems Conference (2006)","DOI":"10.1109\/DCAS.2006.321048"},{"issue":"6","key":"9621_CR28","doi-asserted-by":"crossref","first-page":"1182","DOI":"10.1002\/mrm.21391","volume":"58","author":"M Lustig","year":"2007","unstructured":"Lustig, M., Donoho, D., Pauly, J.: Sparse MRI: The application of compressed sensing for rapid MR imaging. Magn. Reson. Med. 58(6), 1182\u20131195 (2007)","journal-title":"Magn. Reson. Med."},{"key":"9621_CR29","volume-title":"A Wavelet Tour of Signal Processing","author":"S Mallat","year":"2003","unstructured":"Mallat, S.: A Wavelet Tour of Signal Processing. Academic, New York (2003)"},{"key":"9621_CR30","doi-asserted-by":"crossref","unstructured":"Mansour, Y.: Learning Boolean functions via the Fourier transform. In: Theoretical Advances in Neural Computation and Learning, pp. 391\u2013424 (1994)","DOI":"10.1007\/978-1-4615-2696-4_11"},{"issue":"2","key":"9621_CR31","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1137\/S0097539792239291","volume":"24","author":"Y Mansour","year":"1995","unstructured":"Mansour, Y.: Randomized approxmation and interpolation of sparse polynomials. SIAM J. Comput. 24(2), 357\u2013368 (1995)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9621_CR32","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/j.acha.2008.07.002","volume":"26","author":"D Needell","year":"2009","unstructured":"Needell, D., Tropp, J.A.: CoSaMP: iterative signal recovery from incomplete and inaccurate samples. Appl. Comput. Harmon. Anal. 26(3), 301\u2013321 (2009)","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"9621_CR33","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1007\/s10208-008-9031-3","volume":"9","author":"D Needell","year":"2009","unstructured":"Needell, D., Vershynin, R.: Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit. Found. Comput. Math. 9, 317\u2013334 (2009)","journal-title":"Found. Comput. Math."},{"issue":"2","key":"9621_CR34","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1109\/JSTSP.2010.2042412","volume":"4","author":"D Needell","year":"2010","unstructured":"Needell, D., Vershynin, R.: Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit. IEEE J. Sel. Topics Signal Process. 4(2), 310\u2013316 (2010)","journal-title":"IEEE J. Sel. Topics Signal Process."},{"key":"9621_CR35","series-title":"Radon Series Comp. Appl. Math.","first-page":"1","volume-title":"Theoretical Foundations and Numerical Methods for Sparse Recovery","author":"H Rauhut","year":"2010","unstructured":"Rauhut, H.: Compressive sensing and structured random matrices. In: Theoretical Foundations and Numerical Methods for Sparse Recovery, pp. 1\u201392. Radon Series Comp. Appl. Math., vol. 9. de Gruyter, Berlin (2010)"},{"key":"9621_CR36","doi-asserted-by":"crossref","unstructured":"Rudelson, M., Vershynin, R.: Sparse reconstruction by convex relaxation: Fourier and gaussian measurements. In: 40th Annual Conference on Information Sciences and Systems (CISS) (2006)","DOI":"10.1109\/CISS.2006.286463"},{"issue":"12","key":"9621_CR37","doi-asserted-by":"crossref","first-page":"4655","DOI":"10.1109\/TIT.2007.909108","volume":"53","author":"J Tropp","year":"2007","unstructured":"Tropp, J., Gilbert, A.: Signal recovery from partial information via orthogonal matching pursuit. IEEE Trans. Inf. Theory 53(12), 4655\u20134666 (2007)","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Numerical Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11075-012-9621-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11075-012-9621-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11075-012-9621-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,5]],"date-time":"2025-04-05T10:07:25Z","timestamp":1743847645000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11075-012-9621-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7,26]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,6]]}},"alternative-id":["9621"],"URL":"https:\/\/doi.org\/10.1007\/s11075-012-9621-7","relation":{},"ISSN":["1017-1398","1572-9265"],"issn-type":[{"type":"print","value":"1017-1398"},{"type":"electronic","value":"1572-9265"}],"subject":[],"published":{"date-parts":[[2012,7,26]]}}}