Name
Abstract | ||
|---|---|---|
We present a deterministic algorithm for finding the significant Fourier frequencies of a given signal $f\in\BBC^{N}$ and their approximate Fourier coefficients in running time and sample complexity polynomial in $\log N$, $L_{1}(\widehat f)/\Vert\widehat f\Vert_{2}$, and $1/\tau$ , where the significant frequencies are those occupying at least a $\tau$-fraction of the energy of the signal, and $L_{1}(\widehat f)$ denotes the $L_{1}$-norm of the Fourier transform of $f$. Furthermore, the algorithm is robust to additive random noise. This strictly extends the class of compressible/Fourier sparse signals efficiently handled by previous deterministic algorithms for signals in $\BBC^{N}$. As a central tool, we prove there is a deterministic algorithm that takes as input $N$ , $\varepsilon$ and an arithmetic progression $P$ in $\BBZ_{N}$, runs in time polynomial in $\ln N$ and $1/\varepsilon$, and returns a set $A_{P}$ that $\varepsilon$-approximates $P$ in $\BBZ_{N}$ in the sense that $\vert\mathop{\BBE}_{x\in A_{P}}e^{2\pi i\omega x/N}-\mathop{\BBE}_{x\in P}e^{2\pi i\omega x/N}\vert |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/TIT.2013.2290027 | IEEE Transactions on Information Theory |
Keywords | Field | DocType |
discrete fourier transforms,signal processing,signal sampling,noise,time polynomial,approximating arithmetic progressions,fourier transforms,computational efficiency,fourier frequencies,deterministic sparse fourier approximation,signal processing algorithms,running time,fast fourier transforms,combinatorial mathematics,deterministic algorithm,polynomial approximation,algorithm design and analysis,size polynomial,signal reconstruction,deterministic algorithms,fourier transform,compressible/fourier sparse signals,approximate fourier coefficients,additive random noise,sample complexity polynomial,approximation algorithms,polynomials,zinc | Discrete mathematics,Combinatorics,Polynomial,Prime-factor FFT algorithm,Arithmetic,Fourier inversion theorem,Fourier series,Discrete Fourier transform (general),Discrete Fourier transform,Deterministic algorithm,Mathematics,Arithmetic progression | Journal |
Volume | Issue | ISSN |
60 | 3 | 0018-9448 |
Citations | PageRank | References |
8 | 0.60 | 16 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Adi Akavia | 1 | 395 | 15.47 |