000189818 001__ 189818
000189818 005__ 20190812205721.0
000189818 0247_ $$2doi$$a10.1109/Allerton.2013.6736669
000189818 037__ $$aCONF
000189818 245__ $$aA Fast Hadamard Transform for Signals with Sub-linear Sparsity
000189818 269__ $$a2013
000189818 260__ $$c2013
000189818 336__ $$aConference Papers
000189818 520__ $$aA 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).)
000189818 6531_ $$aWalsh-Hadamard
000189818 6531_ $$aTransform
000189818 6531_ $$asparse
000189818 6531_ $$asparse FFT
000189818 6531_ $$asub-linear
000189818 6531_ $$apeeling decoder
000189818 700__ $$0246726$$g161208$$aScheibler, Robin
000189818 700__ $$0244475$$g200157$$aHaghighatshoar, Saeid
000189818 700__ $$aVetterli, Martin$$g107537$$0240184
000189818 7112_ $$dOctober 2-4, 2013$$cAllerton Retreat Center, Monticello, Illinois$$a51st Annual Allerton Conference on Communication, Control, and Computing
000189818 8564_ $$zURL$$uhttps://github.com/LCAV/SparseFHT
000189818 8564_ $$zn/a$$yn/a$$uhttps://infoscience.epfl.ch/record/189818/files/1310.1803.pdf$$s1810440
000189818 909C0 $$xU10434$$pLCAV$$0252056
000189818 909C0 $$0252199$$xU10428$$pLCM
000189818 909CO $$qGLOBAL_SET$$pconf$$pIC$$ooai:infoscience.tind.io:189818
000189818 917Z8 $$x161208
000189818 917Z8 $$x161208
000189818 917Z8 $$x161208
000189818 917Z8 $$x161208
000189818 917Z8 $$x161208
000189818 917Z8 $$x161208
000189818 917Z8 $$x161208
000189818 917Z8 $$x161208
000189818 917Z8 $$x222073
000189818 917Z8 $$x161208
000189818 937__ $$aEPFL-CONF-189818
000189818 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000189818 980__ $$aCONF