SparseFHT

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

View the Project on GitHub LCAV/SparseFHT

This is the code for SparseFHT algorithm as presented in the following papers. The code is hosted on github.

[Long] R. Scheibler, S.Haghighatshoar, and M. Vetterli, A Fast Hadamard Transform for Signals with Sub-linear Sparsity in the Transform Domain, IEEE Trans. Inf. Theory, vol. 61, 2015.

[Short] R. Scheibler, S. Haghighatshoar, and M. Vetterli, A Fast Hadamard Transform for Signals with Sub-linear Sparsity, Allerton Conference on Communication, Control and Computing, 2013.

Abstract

In this paper, we design a new iterative low-complexity algorithm for computing the Walsh-Hadamard transform (WHT) of an N dimensional signal with a K-sparse WHT. We suppose that 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, our algorithm reconstructs the WHT of the signal with a sample complexity O(K log_(N/K)) and a computational complexity O(K log_2(K)log_2(N/K)). Moreover, the algorithm succeeds with a high probability approaching 1 for large dimension N.

Our approach is mainly based on the subsampling (aliasing) property of the WHT, where by a carefully designed subsampling of the time-domain signal, a suitable aliasing pattern is induced in the transform domain. We treat the resulting aliasing patterns as parity-check constraints and represent them by a bipartite graph. We analyze the properties of the resulting bipartite graphs and borrow ideas from codes defined over sparse bipartite graphs to formulate the recovery of the nonzero spectral values as a peeling decoding algorithm for a specific sparse-graph code transmitted over a binary erasure channel (BEC). This enables us to use tools from coding theory (belief-propagation analysis) to characterize the asymptotic performance of our algorithm in the very sparse (α ∈ (0,1/3]) and the less sparse (α ∈ (1/3,1)) regime. Comprehensive simulation results are provided to assess the empirical performance of the proposed algorithm.

Contact

Robin Scheibler (email) (homepage)

Please do not hesitate to contact me for help and support! I would be happy to help you run the code.

Plateform

The code has been tested on Mac OS X 10.7, 10.8, 10.9, and on Ubuntu linux.

Matlab mex wrappers were used for the code generating the figures in the paper. The core of the algorithm is implemented in C.

Run the code in Matlab

Reproduce the figures from the paper

To reproduce the figures from the paper, type in the following in a matlab shell:

cd <path_to_SparseFHT>/matlab/
make_mex_files
make_figures

Note

  1. The simulation is fairly time-consuming.
  2. To speed-up the simulation, the parallel toolbox was used. If you do not have the parallel toolbox, replace the parfor instructions by for in all the Sim scripts.

Mex files info

Reuse the C code

The makefile in ./C folder will compile all the code as well as a number of example/test files. This can be used as a basis to reuse the C code directly.

cd ../C
make all

The libraries included are:

License

2013-2015 (c) Robin Scheibler, Saeid Haghighatshoar, Martin, Vetterli.

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/4.0/.

The code is free to reuse for non-commercial and academic purposes. However, please acknowledge its use with the following citation.

@article{EPFL-JOUR-204991,
   author      = {Scheibler, Robin and Haghighatshoar, Saeid and Vetterli, Martin},
   title       = {A {F}ast {H}adamard {T}ransform for {S}ignals with
                 {S}ub-linear {S}parsity in the {T}ransform {D}omain},
   journal     = {IEEE Trans. Inf. Theory}
   volume      = 61,
   year        = 2015,
   ee          = {http://infoscience.epfl.ch/record/204991}
}

For any other purposes, please contact the authors.