Robust sublinear complexity Walsh-Hadamard transform with arbitrary sparse support

In this paper, we propose algorithms for computing Walsh-Hadamard transform with arbitrary K-sparse support. When K is sublinear in the dimension N of the time-domain signal, the algorithms achieve vanishing error probability as K increases without bound and involve sublinear computational complexity. Specifically, under the noiseless setting, an algorithm based on random hashing and successive cancellation is proposed, where O (K log K log N over K) operations on O(K log N over K) samples of the signal suffice. Under the noisy setting, a fast algorithm using the same framework is also proposed, which needs O (K log³ K log N over K) operations and O (K log² K log N over K) samples. The latter algorithm reduces the complexity from superlinear in existing work to sublinear. The enabling idea is to relate the random hashing design to coding over a binary symmetric channel or a binary-input additive white Gaussian noise channel, whose quality depends on the noise level of the observations. Such inherent connection allows us to leverage well-established capacity-approaching codes to obtain the transform-domain signal with sublinear complexity.