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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the well-studied Sparse Fourier transform problem, where one aimsto quickly recover an approximately Fourier $k$-sparse vector $\widehat{x} \in\mathbb{C}^{n^d}$ from observing its time domain representation $x$. In theexact $k$-sparse case the best known dimension-independent algorithm runs innear cubic time in $k$ and it is unclear whether a faster algorithm like in lowdimensions is possible. Beyond that, all known approaches either suffer from anexponential dependence on the dimension $d$ or can only tolerate a trivialamount of noise. This is in sharp contrast with the classical FFT of Cooley andTukey, which is stable and completely insensitive to the dimension of the inputvector: its runtime is $O(N\log N)$ in any dimension $d$ for $N=n^d$. Our workaims to address the above issues.  First, we provide a translation/reduction of the exactly $k$-sparse FTproblem to a concrete tree exploration task which asks to recover $k$ leaves ina full binary tree under certain exploration rules. Subsequently, we provide(a) an almost quadratic in $k$ time algorithm for this task, and (b) evidencethat a strongly subquadratic time for Sparse FT via this approach is likelyimpossible. We achieve the latter by proving a conditional quadratic time lowerbound on sparse polynomial multipoint evaluation (the classical non-equispacedsparse FT) which is a core routine in the aforementioned translation. Thus, ourresults combined can be viewed as an almost complete understanding of thisapproach, which is the only known approach that yields sublinear timedimension-independent Sparse FT algorithms.  Subsequently, we provide a robustification of our algorithm, yielding arobust cubic time algorithm under bounded $\ell_2$ noise. This requires provingnew structural properties of the recently introduced adaptive aliasing filterscombined with a variety of new techniques and ideas.

Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms