Julia implementations of coding-theoretic sparse Walsh-Hadamard and Fourier transforms
Author aditya-sengupta
5 Stars
Updated Last
1 Year Ago
Started In
September 2020


Implementations of and extensions to the SPRIGHT (SParse Robust Iterative Graph-based Hadamard Transform) algorithm in Julia, and potentially the FFAST (Fast Fourier Aliasing-based Sparse Transform) algorithm too.

Authors and Acknowledgements

This package was written by Aditya Sengupta (@aditya-sengupta), Tynan Sigg (@trsigg), Catherine Huang (@thecatherinehuang) and Ben Hoberman (@bhoberman) as the final project for EECS 229A at UC Berkeley in Fall 2020, with advice from Orhan Ocal, Amirali Aghazadeh, and Kannan Ramchandran.


[1] Li, X., Ramchandran, K. (2015). An Active Learning Framework using Sparse-Graph Codes for Sparse Polynomials and Graph Sketching. NeurIPS,

[2] Li, X., Bradley, J., Pawar, S., Ramchandran, K. (2015). SPRIGHT: A Fast and Robust Framework for Sparse Walsh-Hadamard Transform. cs.IT.

[3] Pawar, S., Ramchandran, K. (2017). FFAST: An Algorithm for Computing an Exactly $k$-Sparse DFT in $O(k \log k)$ Time. IEEE,

Comments in the code referencing equation and page numbers refer to [2] unless otherwise specified.

Used By Packages

No packages found.