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/

Zendy Plus

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

Zendy Tools

Zendy Open

We consider the problem of computing a $k$-sparse approximation to theFourier transform of a length $N$ signal. Our main result is a randomizedalgorithm for computing such an approximation (i.e. achieving the$\ell_2/\ell_2$ sparse recovery guarantees using Fourier measurements) using$O_d(k\log N\log\log N)$ samples of the signal in time domain that runs in time$O_d(k\log^{d+3} N)$, where $d\geq 1$ is the dimensionality of the Fouriertransform. The sample complexity matches the lower bound of $\Omega(k\log(N/k))$ for non-adaptive algorithms due to \cite{DIPW} for any $k\leqN^{1-\delta}$ for a constant $\delta>0$ up to an $O(\log\log N)$ factor. Priorto our work a result with comparable sample complexity $k\log N \log^{O(1)}\logN$ and sublinear runtime was known for the Fourier transform on the line\cite{IKP}, but for any dimension $d\geq 2$ previously known techniques eithersuffered from a polylogarithmic factor loss in sample complexity or required$\Omega(N)$ runtime.

Sparse Fourier Transform in Any Constant Dimension with Nearly-Optimal Sample Complexity in Sublinear Time