Abstract-Ges en n-längd ingångssignal x, är det välkänt att dess Discrete Fourier Transform (DFT), X, kan beräknas i O (n log n) komplexitet med hjälp av en Fast Fourier Transform. Om spektrumet X är exakt k-sparse (där k < < < n), kan vi göra bättre? Vi visar att asymptotiskt i k och n, när k är sublinear i n (dvs., k  till n δ där 0 < δ < 1), och stödet av icke-noll DFT koefficienter är enhetligt slumpmässigt, kan vi utnyttja denna sparhet på två grundläggande sätt (i) prov komplexitet: vi behöver bara M =rk deterministiskt utvalda prover av ingångssignalen x (där r < 4 när 0 < δ < 0,99); och (ii) beräkning komplexitet: vi kan tillförlitligt beräkna DFT X med hjälp av O (k log k) operationer, där konstanterna i den stora Oh är små. Vår algoritm lyckas med hög sannolikhet, med sannolikheten för att fel försvinner till noll asymptotiskt i antalet prov förvärvade, M. Vår strategi är baserad på filterlös subsampling av ingångssignalen x med hjälp av en liten uppsättning noggrant utvalda enhetliga subsampling mönster guidade av den kinesiska rester Theorem (CRT). Speciellt, vår subsampling operation på x är utformad för att skapa aliasing mönster på spektrumet X som "ser ut som" paritet-kontroll begränsningar av bra radering-korrigerande sparse-graf koder. Vi visar hur computing the sparse DFT X är likvärdigt med avkodning av dessa sparse-graf koder och är låg i både prov komplexitet och avkodning komplexitet. Vi dub vår algoritm FFAST (Snabb Fourier Aliasing-baserade Sparse Transform) algoritm. I vår analys kopplar vi rigoröst samman våra CRT-baserade grafkonstruktioner med slumpmässiga sparsegraph-koder baserade på en ball-and-bins-modell och analyserar konvergensbeteendet hos de senare med hjälp av välstuderade densitetsutvecklingstekniker från kodningsteori. Vi tillhandahåller simuleringsresultat i avsnitt IV som bekräftar våra teoretiska resultat och validerar FFAST-algoritmens empiriska prestanda.
I FFAST-algoritmen REF används endast O(K)-prover och O(K log K)-operationer för alla gleshetsregimer K = O(N δ ) och δ  ska (0, 1).
Computing a k-sparse n-length Discrete Fourier Transform using at most 4k samples and O(k log k) complexity
{'venue': '2013 IEEE International Symposium on Information Theory', 'journal': '2013 IEEE International Symposium on Information Theory', 'mag_field_of_study': ['Mathematics', 'Computer Science']}