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

We consider the problem of computing a k-sparse approximation to the Fourier transform of a length N signal. Our main result is a randomized algorithm for computing such an approximation (i.e. achieving ℓ2/ℓ2 sparse recovery guarantees using Fourier measurements) using Od(klogNloglogN) samples of the signal in time domain and Od(klogd+3N) runtime, where d≥ 1 is the dimensionality of the Fourier transform. The sample complexity matches the Ω(klog(N/k)) lower bound for non-adaptive algorithms due to [DIPW] for any k≤ N1−δ for a constant δ>0 up to an O(loglogN) factor. Prior to our work a result with comparable sample complexity klogN logO(1)logN and sublinear runtime was known for the Fourier transform on the line [IKP], but for any dimension d≥ 2 previously known techniques either suffered from a (logN) factor loss in sample complexity or required Ω(N) runtime.

Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time