189818
20190316235723.0
doi
10.1109/Allerton.2013.6736669
CONF
A Fast Hadamard Transform for Signals with Sub-linear Sparsity
2013
2013
Conference Papers
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^α), scales sub- linearly in N for some 0 < α < 1. Assuming a random support model for the nonzero transform domain components, the algorithm reconstructs the WHT of the signal with a sample complexity O(K log2(N/K)), a computational complexity O(K log2(K) log2(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 nonzero 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” (α ∈ (0, 1/3]) and the “less sparse” regime (α ∈ (1/3,1).)
Walsh-Hadamard
Transform
sparse
sparse FFT
sub-linear
peeling decoder
246726
Scheibler, Robin
161208
244475
Haghighatshoar, Saeid
200157
240184
Vetterli, Martin
107537
51st Annual Allerton Conference on Communication, Control, and Computing
Allerton Retreat Center, Monticello, Illinois
October 2-4, 2013
https://github.com/LCAV/SparseFHT
URL
1810440
http://infoscience.epfl.ch/record/189818/files/1310.1803.pdf
n/a
n/a
252056
LCAV
U10434
252199
LCM
U10428
oai:infoscience.tind.io:189818
conf
IC
GLOBAL_SET
161208
161208
161208
161208
161208
161208
161208
161208
222073
161208
EPFL-CONF-189818
EPFL
REVIEWED
PUBLISHED
CONF