Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. A Fast Hadamard Transform for Signals with Sub-linear Sparsity in the Transform Domain
 
research article

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

Scheibler, Robin  
•
Haghighatshoar, Saeid  
•
Vetterli, Martin  
2015
IEEE Transactions on Information Theory

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_2(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.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

journal_2015_hadamard.pdf

Type

Publisher's Version

Version

http://purl.org/coar/version/c_970fb48d4fbd8a85

Access type

openaccess

Size

729.04 KB

Format

Adobe PDF

Checksum (MD5)

81af05848a3f1ef305be1d62c910e853

Loading...
Thumbnail Image
Name

sfht_long_final.pdf

Type

Preprint

Version

http://purl.org/coar/version/c_71e4c1898caa6e32

Access type

openaccess

Size

1.18 MB

Format

Adobe PDF

Checksum (MD5)

e2596f6823a6219d4da8071f752dfee9

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés