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 Tools annual

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 monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The Fast Fourier Transform (FFT) is the most efficiently known way to computethe Discrete Fourier Transform (DFT) of an arbitrary n-length signal, and has acomputational complexity of O(n log n). If the DFT X of the signal x has only knon-zero coefficients (where k < n), can we do better? In [1], we addressedthis question and presented a novel FFAST (Fast Fourier Aliasing-based SparseTransform) algorithm that cleverly induces sparse graph alias codes in the DFTdomain, via a Chinese-Remainder-Theorem (CRT)-guided sub-sampling operation ofthe time-domain samples. The resulting sparse graph alias codes are thenexploited to devise a fast and iterative onion-peeling style decoder thatcomputes an n length DFT of a signal using only O(k) time-domain samples andO(klog k) computations. The FFAST algorithm is applicable whenever k issub-linear in n (i.e. k = o(n)), but is obviously most attractive when k ismuch smaller than n.  In this paper, we adapt the FFAST framework of [1] to the case where thetime-domain samples are corrupted by a white Gaussian noise. In particular, weshow that the extended noise robust algorithm R-FFAST computes an n-lengthk-sparse DFT X using O(klog ^3 n) noise-corrupted time-domain samples, inO(klog^4n) computations, i.e., sub-linear time complexity. While ourtheoretical results are for signals with a uniformly random support of thenon-zero DFT coefficients and additive white Gaussian noise, we providesimulation results which demonstrates that the R-FFAST algorithm performs welleven for signals like MR images, that have an approximately sparse Fourierspectrum with a non-uniform support for the dominant DFT coefficients.

A robust sub-linear time R-FFAST algorithm for computing a sparse DFT