Golay meets Hadamard: Golay-paired Hadamard matrices for fast compressed sensing

This paper introduces Golay-paired Hadamard matrices for fast compressed sensing of sparse signals in the time or spectral domain. These sampling operators feature low-memory requirement, hardware-friendly implementation and fast computation in reconstruction. We show that they require a nearly optimal number of measurements for faithful reconstruction of a sparse signal in the time or frequency domain. Simulation results demonstrate that the proposed sensing matrices offer a reconstruction performance similar to that of fully random matrices.