Academic Journal
Finding Significant Fourier Transform Coefficients Deterministically and Locally
| العنوان: | Finding Significant Fourier Transform Coefficients Deterministically and Locally |
|---|---|
| المؤلفون: | Adi Akavia |
| المساهمون: | The Pennsylvania State University CiteSeerX Archives |
| المصدر: | http://people.csail.mit.edu/akavia/FQSFT.pdf. |
| سنة النشر: | 2008 |
| المجموعة: | CiteSeerX |
| الوصف: | Computing the Fourier transform is a basic building block used in numerous applications. For data intensive applications, even the O(N logN) running time of the Fast Fourier Transform (FFT) algorithm may be too slow, and sub-linear running time is necessary. Clearly, outputting the entire Fourier transform in sub-linear time is infeasible, nevertheless, in many applications it suffices to find only the τ-significant Fourier transform coefficients, that is, the Fourier coefficients whose magnitude is at least τ-fraction (say, 1%) of the energy (i.e., the sum of squared Fourier coefficients). We call algorithms achieving the latter SFT algorithms. In this work we present a deterministic algorithm that finds the τ-significant Fourier coefficients of functions f over any finite abelian group G in time polynomial in log|G|, 1/τ and L1 ( ̂f) (for L1 ( ̂f) denoting the sum of absolute values of the Fourier coefficients of f). Our algorithm is robust to random noise. Our algorithm is the first deterministic and efficient (i.e., polynomial in log|G|) SFT algorithm to handle functions over any finite abelian groups, as well as the first such algorithm to handle functions over ZN that are neither compressible nor Fourier-sparse. Our analysis is the first to show robustness to noise in the context of deterministic SFT algorithms. Using our SFT algorithm we obtain (1) deterministic (universal and explicit) algorithms for sparse Fourier approximation, compressed sensing and sketching; (2) an algorithm solving the Hidden Number Problem with advice, with cryptographic bit security implications; and (3) an efficient decoding algorithm in the random noise model for polynomial rate variants of Homomorphism codes and any other concentrated & recoverable codes. |
| نوع الوثيقة: | text |
| وصف الملف: | application/pdf |
| اللغة: | English |
| Relation: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.169.4135; http://people.csail.mit.edu/akavia/FQSFT.pdf |
| الاتاحة: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.169.4135 http://people.csail.mit.edu/akavia/FQSFT.pdf |
| Rights: | Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
| رقم الانضمام: | edsbas.F2D6D6A6 |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |