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 problem of computing the Walsh-Hadamard Transform (WHT) ofsome $N$-length input vector in the presence of noise, where the $N$-pointWalsh spectrum is $K$-sparse with $K = {O}(N^{\delta})$ scaling sub-linearly inthe input dimension $N$ for some $0<\delta<1$. Over the past decade, there hasbeen a resurgence in research related to the computation of Discrete FourierTransform (DFT) for some length-$N$ input signal that has a $K$-sparse Fourierspectrum. In particular, through a sparse-graph code design, our earlier workon the Fast Fourier Aliasing-based Sparse Transform (FFAST) algorithm computesthe $K$-sparse DFT in time ${O}(K\log K)$ by taking ${O}(K)$ noiseless samples.Inspired by the coding-theoretic design framework, Scheibler et al. proposedthe Sparse Fast Hadamard Transform (SparseFHT) algorithm that elegantlycomputes the $K$-sparse WHT in the absence of noise using ${O}(K\log N)$samples in time ${O}(K\log^2 N)$. However, the SparseFHT algorithm explicitlyexploits the noiseless nature of the problem, and is not equipped to deal withscenarios where the observations are corrupted by noise. Therefore, a questionof critical interest is whether this coding-theoretic framework can be maderobust to noise. Further, if the answer is yes, what is the extra price thatneeds to be paid for being robust to noise? In this paper, we show, quiteinterestingly, that there is {\it no extra price} that needs to be paid forbeing robust to noise other than a constant factor. In other words, we canmaintain the same sample complexity ${O}(K\log N)$ and the computationalcomplexity ${O}(K\log^2 N)$ as those of the noiseless case, using our SParseRobust Iterative Graph-based Hadamard Transform (SPRIGHT) algorithm.

SPRIGHT: A Fast and Robust Framework for Sparse Walsh-Hadamard Transform