A Fast Hadamard Transform for Signals with Sub-linear Sparsity in the Transform Domain

Abstract

A new iterative low complexity algorithm has been presented for computing the Walsh-Hadamard transform (WHT) of an $N$ dimensional signal with a $K$-sparse WHT, where $N$ is a power of two and $K=O(N^{\alpha })$, scales sub-linearly in $N$ for some $0<\alpha <1$. Assuming a random support model for the non-zero transform domain components, the algorithm reconstructs the WHT of the signal with a sample complexity $O(K{\log }_2(\frac{N}{K}))$, a computational complexity $O(K{\log }_2(K){\log }_2(\frac{N}{K}))$ and with a very high probability asymptotically tending to 1. The approach is based on the subsampling (aliasing) property of the WHT, where by a carefully designed subsampling of the time domain signal, one can induce a suitable aliasing pattern in the transform domain. By treating the aliasing patterns as parity-check constraints and borrowing ideas from erasure correcting sparse-graph codes, the recovery of the non-zero spectral values has been formulated as a belief propagation (BP) algorithm (peeling decoding) over a sparse-graph code for the binary erasure channel (BEC). Tools from coding theory are used to analyze the asymptotic performance of the algorithm in the very sparse ($\alpha \in (0,\frac{1}{3}]$) and the less sparse ($\alpha \in (\frac{1}{3},1)$) regime.

17 pages. 11 figures. A shorter version was submitted to the 51st Allerton Conference on Communication, Control and Computing (2013)

Cited by in corpus (8)

• Efficient estimation of Pauli channels
• Approximate amplitude encoding in shallow parameterized quantum circuits and its application to financial market indicator
• Fast Estimation of Sparse Quantum Noise
• Fourier Analysis-based Iterative Combinatorial Auctions
• SPRIGHT: A Fast and Robust Framework for Sparse Walsh-Hadamard Transform
• Computing a k-sparse n-length Discrete Fourier Transform using at most 4k samples and O(k log k) complexity
• Practical Tera-scale Walsh-Hadamard Transform
• Sketching sparse low-rank matrices with near-optimal sample- and time-complexity using message passing