Abstract-We ger en algoritm för 2/ 2 gles återställning från Fourier mätningar med hjälp av O(k log N ) prover, som matchar den nedre gränsen av Do Ba-Indyk-Price-Woodruff'10 för icke-adaptiva algoritmer upp till konstanta faktorer för alla k ≤ N 1−δ. Algoritmen körs i Õ(N ) tid. Vår algoritm sträcker sig till högre dimensioner, vilket leder till prov komplexitet av O d (k log N ), vilket är optimal upp till konstanta faktorer för alla d = O(1). Dessa är det första provet optimala algoritmer för dessa problem. En preliminär experimentell utvärdering visar att vår algoritm har empirisk provtagnings komplexitet jämförbar med andra återvinningsmetoder som är kända i litteraturen, samtidigt som den ger starka bevisbara garantier för återvinningens kvalitet.
Indyk m.fl. REF, den föreslagna algoritmen uppnår O(k log N ) prov komplexitet och O(N log c N )
Sample-Optimal Fourier Sampling in Any Constant Dimension
{'venue': '2014 IEEE 55th Annual Symposium on Foundations of Computer Science', 'journal': '2014 IEEE 55th Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}