English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

In this paper we consider sparse Fourier transform (SFT) algorithms for approximately computing the best s-term approximation of the discrete Fourier transform (DFT) \({\hat{\mathbf {f}}}\in {{\mathbb {C}}}^N\) of any given input vector \(\mathbf {f}\in {{\mathbb {C}}}^N\) in just \(\left( s \log N\right) ^{{{\mathcal {O}}}(1)}\)-time using only a similarly small number of entries of \(\mathbf {f}\). In particular, we present a deterministic SFT algorithm which is guaranteed to always recover a near best s-term approximation of the DFT of any given input vector \(\mathbf {f}\in {{\mathbb {C}}}^N\) in \({{\mathcal {O}}} \left( s^2 \log ^{\frac{11}{2}} (N) \right) \)-time. Unlike previous deterministic results of this kind, our deterministic result holds for both arbitrary vectors \(\mathbf {f}\in {{\mathbb {C}}}^N\) and vector lengths N. In addition to these deterministic SFT results, we also develop several new publicly available randomized SFT implementations for approximately computing \({\hat{\mathbf {f}}}\) from \(\mathbf {f}\) using the same general techniques. The best of these new implementations is shown to outperform existing discrete sparse Fourier transform methods with respect to both runtime and noise robustness for large vector lengths N.

A New Class of Fully Discrete Sparse Fourier Transforms: Faster Stable Implementations with Guarantees