DocumentCode
85615
Title
Deterministic Sparse Fourier Approximation Via Approximating Arithmetic Progressions
Author
Akavia, Adi
Author_Institution
Tel-Aviv Yaffo Acad. Coll., Tel-Aviv, Israel
Volume
60
Issue
3
fYear
2014
fDate
Mar-14
Firstpage
1733
Lastpage
1741
Abstract
We present a deterministic algorithm for finding the significant Fourier frequencies of a given signal f ∈ CN and their approximate Fourier coefficients in running time and sample complexity polynomial in log N, L1(f̂)/||f̂||2, and 1/τ, where the significant frequencies are those occupying at least a τ-fraction of the energy of the signal, and L1(f̂) denotes the L1-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 CN. As a central tool, we prove there is a deterministic algorithm that takes as input N, ε and an arithmetic progression P in ZN, runs in time polynomial in ln N and 1/ε, and returns a set AP that ε-approximates P in ZN in the sense that |Ex∈APe2πiω/N - Ex∈Pe2πiωx/N| <; ε for all ω = 0,..., N-1. In other words, we show there is an explicit construction of sets AP of size polynomial in lnN and 1/ε that ε-approximate given arithmetic progressions P in ZN. This extends results on small-bias sets, which are sets approximating the entire domain, to sets approximating a given arithmetic progression; this result may be of independent interest.
Keywords
Fourier transforms; deterministic algorithms; polynomial approximation; signal processing; Fourier frequencies; Fourier transform; additive random noise; approximate Fourier coefficients; approximating arithmetic progressions; compressible/Fourier sparse signals; deterministic algorithm; deterministic sparse Fourier approximation; running time; sample complexity polynomial; size polynomial; time polynomial; Approximation algorithms; Approximation methods; Complexity theory; Discrete Fourier transforms; Noise; Polynomials; Zinc; Algorithm design and analysis; combinatorial mathematics; computational efficiency; discrete Fourier transforms; fast Fourier transforms; noise; signal processing algorithms; signal reconstruction; signal sampling;
fLanguage
English
Journal_Title
Information Theory, IEEE Transactions on
Publisher
ieee
ISSN
0018-9448
Type
jour
DOI
10.1109/TIT.2013.2290027
Filename
6657776
Link To Document