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

If you recall this entry on How to spot a compressive sensing system: the case of the Randomized MALDI TOF MS/MS system, featuring Hadamard Transform Time-of-Flight Mass Spectrometry, you'll remember that there are detectors that interact with sparse signals (as opposed to being compressible signals) because the signal represents particles of matter. As it turns out, Robin Scheibler just sent me the following: 

Dear Igor,

Just wanted to let you know that we have released the implementation of our fast Hadamard transform for data sparse in the transform domain (http://arxiv.org/abs/1310.1803). The algorithm is similar to the recent sparse FFT in that we use a fast Hadamard hashing procedure followed by a low-complexity peeling type decoder. The paper contains the analysis of the algorithm as well as simulation results. The C implementation and mex files to use it in Matlab are available in our github repository (http://lcav.github.io/SparseFHT/). I hope this code can be useful and am available if anyone need help getting started with it.

.....

Best regards,

Robin Scheibler

Thanks Robin !. Here is the paper: A Fast Hadamard Transform for Signals with Sub-linear Sparsity in the Transform Domain by Robin Scheibler, Saeid Haghighatshoar, Martin Vetterli

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 nbsp="" span="" style="background-color: white; font-family: 'Lucida Grande', helvetica, arial, verdana, sans-serif; font-size: 14.399999618530273px; line-height: 20.15999984741211px; text-align: start;">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(Klog2(NK)), a computational complexity O(Klog2(K)log2(NK)) 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 (α∈(0,1/3]) and the less sparse (α∈(1/3,1)) regime.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.