SPRIGHT: A Fast and Robust Framework for Sparse Walsh-Hadamard Transform

2015/08/26 by Xiao Li, Joseph K. Bradley, Li, Xiao +5
Computer Science · Engineering · #Advanced MIMO Systems Optimization #Advanced Wireless Communication Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #Wireless Communication Networks Research

paper · pdf · doi:10.48550/arxiv.1508.06336

openalex publication_date 2015/08/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the problem of computing the Walsh-Hadamard Transform (WHT) of some N-length input vector in the presence of noise, where the N-point Walsh spectrum is K-sparse with K = O(N^δ) scaling sub-linearly in the input dimension N for some 0

Citations

• Hadamard Matrices and Their Applications
• Computing a k-sparse n-length Discrete Fourier Transform using at most\n 4k samples and O(k log k) complexity

Related

• Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform
• Faster Walsh-Hadamard and Discrete Fourier Transforms From Matrix Non-Rigidity
• Characterizing and Enumerating Walsh-Hadamard Transform Algorithms
• Sparse Reconstruction with Multiple Walsh matrices
• Multiallelic Walsh transforms