Robust sublinear complexity Walsh-Hadamard transform with arbitrary sparse support

Xu Chen, Dongning Guo

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

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 log3 K log N over K) operations and O (K log2 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.

Original languageEnglish (US)
Title of host publicationProceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2573-2577
Number of pages5
ISBN (Electronic)9781467377041
DOIs
StatePublished - Sep 28 2015
EventIEEE International Symposium on Information Theory, ISIT 2015 - Hong Kong, Hong Kong
Duration: Jun 14 2015Jun 19 2015

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2015-June
ISSN (Print)2157-8095

Other

OtherIEEE International Symposium on Information Theory, ISIT 2015
CountryHong Kong
CityHong Kong
Period6/14/156/19/15

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Robust sublinear complexity Walsh-Hadamard transform with arbitrary sparse support'. Together they form a unique fingerprint.

Cite this