{"entities":{"Q1762319":{"pageid":1773061,"ns":120,"title":"Item:Q1762319","lastrevid":69021651,"modified":"2026-04-13T03:47:17Z","type":"item","id":"Q1762319","labels":{"en":{"language":"en","value":"Improved approximation guarantees for sublinear-time Fourier algorithms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6110200"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1762319$007ED1B2-FB26-477A-B979-7B0D74E2769F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"77205e01b4e9e8f1d177e3354d67b1939b513827","datavalue":{"value":{"text":"Improved approximation guarantees for sublinear-time Fourier algorithms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1762319$C40BDB34-8D0F-4EB6-8396-A2B4B2AC40B0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b723225836d1023a4c1c72510085b8c9888d8e2d","datavalue":{"value":"1260.65115","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762319$ACE638B0-9D82-42FE-8C81-85180F946D31","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c86a8f4c64afb5222ff7a7f95c2d7eb3463b252e","datavalue":{"value":{"entity-type":"item","numeric-id":1762318,"id":"Q1762318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1762319$649784B7-F377-4BB8-B3DF-640FA2B077BF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e219ca58c5478bf431640db74af74d5c15bdb120","datavalue":{"value":{"entity-type":"item","numeric-id":107999,"id":"Q107999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1762319$3231EB6D-513A-4A8E-A7F8-A3AB784A8B9A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fa56dcb0002faa04710135fff394e601e7d30b8e","datavalue":{"value":{"time":"+2012-11-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1762319$98C32E90-7981-4A70-8BAB-E7CEE126C44C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"52de78242ead38d8bc369c74c3bfed9a67a77845","datavalue":{"value":"https://arxiv.org/abs/1010.0014","type":"string"},"datatype":"url"},"type":"statement","id":"Q1762319$A77476B9-7FA1-4F4F-8D4D-B33D18534995","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0e8f4dba563f6a5d451dc533a98481b5c77a2c06","datavalue":{"value":"This paper develops fast methods for finding near-optimal nonlinear approximations to the Fourier transform of a given continuous and periodic function \\(f:\\;[0,2\\pi]^D\\to\\mathbb C\\). Suppose that \\(f\\) is a band limited so that its Fourier transform, \\(\\hat f:\\;\\mathbb Z^D\\to \\mathbb C\\), is zero for all \\(\\omega\\notin [-N/2,N/2]^D\\), where \\(N^D\\) is large. An optimal \\(k\\)-term trigonometric approximation to \\(f\\) is given by  \\[  f_k^{\\text{opt}}({\\mathbf x})=\\sum_{j=1}^k\\hat f (\\omega_j)e^{i\\omega_j{\\mathbf x}},  \\]  where \\(\\omega_1,\\dots,\\omega_{N^D}\\in (-N/2,N/2]^D\\bigcap\\mathbb Z^D\\) are ordered by the magnitudes of their coefficients so that  \\[  |\\hat f(\\omega_1)|\\geq|\\hat f(\\omega_2)|\\geq\\dots\\geq |\\hat f(\\omega_{N^D})|.  \\]  The optimal \\(k\\)-term approximation error is then \\(\\|f-f_k^{\\text{opt}}\\|_2=\\|\\hat f-\\hat f_k^{\\text{opt}}\\|_2\\). Suppose \\(k\\in\\mathbb N\\) is given. The goal of this paper is to develop fast Fourier approximation schemes that are guaranteed to always return a near-optimal trigonometric polynomial, \\(y_k:\\;[0,2\\pi]^D\\to\\mathbb C\\), having \\(\\|f-y_k\\|_2\\approx\\|\\hat f-\\hat f_k^{\\text{opt}}\\|_2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1762319$F5B7790D-AAEC-4DD6-93E8-B06F558A30C5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b0d860fb28732fde166aa9d357a9ff887a1e333e","datavalue":{"value":{"entity-type":"item","numeric-id":483645,"id":"Q483645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1762319$B466FABA-A3DF-4F0A-B07F-0F9553BB69C3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c4603c40f3b09770fdbb70ee2650f252415f25c5","datavalue":{"value":"65T50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762319$135ED0F7-6478-4642-B400-32173E8A5474","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"588be99e69a86bc02ca9cc8ddd46725bc447e370","datavalue":{"value":"65T40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762319$716CD3A8-4634-4EF9-B6B0-9B0233D222FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9ece9bc63b7314d725c9be7c351612e465cf9932","datavalue":{"value":"42A38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762319$9F9BCFD2-7C2F-49B1-BC4B-37322D641FB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"420c721aa841b62396a405ab7bd03b5ed466ed48","datavalue":{"value":"42A10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762319$C1E7A620-8C5E-4587-B842-1E01B748E5C9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"eaaaf05c1784bec405b7b60c3ceb4df7edc74602","datavalue":{"value":"6110200","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762319$A5EA6A9A-895B-41CE-AD5F-43E51A05E00C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"17f28ee32dfba3199f61ce30a2f4ba0e143a8d7d","datavalue":{"value":"signal recovery","type":"string"},"datatype":"string"},"type":"statement","id":"Q1762319$A261FC3E-4A66-4E37-BE30-8E0A964BDA7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d13c32acaec0f55aa8967614669667bc52cd8f80","datavalue":{"value":"Fourier analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1762319$1907A9F3-5721-4D4D-A68F-A1ED96F07FB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b7b6162cbcb21d53ea3c1f92bac167bd1d60caa4","datavalue":{"value":"fast Fourier transforms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1762319$3B22FFF4-0EFA-4A93-858A-EAC1B4F95872","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1762319$207541AE-5A6E-4518-BC7B-3881C7854D76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"175ad8feb8daa2ab2b8cf7b774ce5bac340d1182","datavalue":{"value":"trigonometric approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1762319$064B73CC-4B15-4559-BF67-B40F9A1795F0","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1762319$83B1304E-216E-4ABD-9294-705A79DDC01E","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"7902577e0387b1975d80616fd7f52e500bc455a6","datavalue":{"value":"Q60204978","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762319$9097A6A7-8CA4-4D64-9550-898D49FEE2BE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"936123c4599cce1c6837e229201b79277cf5aec1","datavalue":{"value":"W1522894866","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762319$51CC3C32-B65C-42CF-9FDD-1A05A3233F40","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6c22fe57f27d2da1c2d822d9ffba59bf242d1cf3","datavalue":{"value":"10.1016/J.ACHA.2012.03.007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762319$D58C9850-C986-453E-90C5-D179C11A3832","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"604b8769b24056a606715b8e01178b98837934da","datavalue":{"value":{"entity-type":"item","numeric-id":2376358,"id":"Q2376358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50097fe52dd071e8c46b32a34e46b4f4455c9cec","datavalue":{"value":{"amount":"+0.8078522086143494","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762319$F2D3D9B5-F97D-4783-89A1-8A3BB0FBBB59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dac8b95ad4c8f0cd9563bba17b931d80cabb599f","datavalue":{"value":{"entity-type":"item","numeric-id":972615,"id":"Q972615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e1b8515ac50fbdc4d98678bb5dd4e457b915d52","datavalue":{"value":{"amount":"+0.7857773303985596","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762319$7607B59E-1017-4998-9033-5B97830FA7FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92fd8473b051c6a56c45b3cc5a88066ca0b16634","datavalue":{"value":{"entity-type":"item","numeric-id":5415501,"id":"Q5415501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"089fe86680f76ce463d12ba364c7040ed0e1938f","datavalue":{"value":{"amount":"+0.7802050709724426","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762319$E5EF4531-6F2A-41EE-9C90-CFECA765B020","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33bea693bdb3f7fbff3a7c4a1e77a24f463a4992","datavalue":{"value":{"entity-type":"item","numeric-id":4006300,"id":"Q4006300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1171a503cd9d75a3624c41953081379641bc3b48","datavalue":{"value":{"amount":"+0.7649552822113037","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762319$6A4A20AF-ED4C-4162-AEE0-EB3539E1930F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa997c5654b531a17fb357ae6de8056aa265f628","datavalue":{"value":{"entity-type":"item","numeric-id":2073139,"id":"Q2073139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c26ea033c6c2b00c1786fda9a078e02de2a8e043","datavalue":{"value":{"amount":"+0.7557113170623779","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762319$3677B3CD-5E37-4C00-88B6-BE965381F6C0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Improved approximation guarantees for sublinear-time Fourier algorithms","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Improved_approximation_guarantees_for_sublinear-time_Fourier_algorithms"}}}}}