Abstract

(MATH) We give an algorithm for finding a Fourier representation R of B terms for a given discrete signal signal A of length N, such that $\|\signal-\repn\|_2^2$ is within the factor (1 +ε) of best possible $\|\signal-\repn_\opt\|_2^2$. Our algorithm can access A by reading its values on a sample set T ⊆[0,N), chosen randomly from a (non-product) distribution of our choice, independent of A. That is, we sample non-adaptively. The total time cost of the algorithm is polynomial in B log(N)log(M)ε (where M is the ratio of largest to smallest numerical quantity encountered), which implies a similar bound for the number of samples.

Keywords

Fourier transformSIGNAL (programming language)Sampling (signal processing)MathematicsRepresentation (politics)Product (mathematics)Distribution (mathematics)Set (abstract data type)AlgorithmNyquist–Shannon sampling theoremBinary logarithmPolynomialSample (material)Discrete-time signalDiscrete Fourier transform (general)Fourier seriesCombinatoricsDiscrete mathematicsFourier analysisComputer scienceAnalog signalSignal transfer functionShort-time Fourier transformDigital signal processingMathematical analysisGeometry

Affiliated Institutions

Related Publications

The finite Fourier transform

J.W. Cooley , Peter Lewis , P. D. Welch

The finite Fourier transform of a finite sequence is defined and its elementary properties are developed. The convolution and term-by-term product operations are defined and the...

1969 IEEE Transactions on Audio and Electr... 197 citations

Publication Info

Year
2002
Type
article
Pages
152-161
Citations
271
Access
Closed

External Links

View on DOI.org

Social Impact

Altmetric
PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

271
OpenAlex

Cite This

Anna C. Gilbert, Suvajyoti Guha, Piotr Indyk et al. (2002). Near-optimal sparse fourier representations via sampling. , 152-161. https://doi.org/10.1145/509907.509933

Identifiers

DOI
10.1145/509907.509933