A Generalized LDPC Framework for Robust and Sublinear Compressive Sensing

Abstract

Compressive sensing aims to recover a high-dimensional sparse signal from a relatively small number of measurements. In this paper, a novel design of the measurement matrix is proposed. The design is inspired by the construction of generalized low-density parity-check codes, where the capacity-achieving point-to-point codes serve as subcodes to robustly estimate the signal support. In the case that each entry of the $n$-dimensional $k$-sparse signal lies in a known discrete alphabet, the proposed scheme requires only $O(k\log n)$ measurements and arithmetic operations. In the case of arbitrary, possibly continuous alphabet, an error propagation graph is proposed to characterize the residual estimation error. With $O(k{\log }^{2}n)$ measurements and computational complexity, the reconstruction error can be made arbitrarily small with high probability.

arXiv commentaccepted to ICASSP 2016

References in corpus (4)

• Construction of a Large Class of Deterministic Sensing Matrices that Satisfy a Statistical Isometry Property
• Sub-linear Time Support Recovery for Compressed Sensing using Sparse-Graph Codes
• Computing a k-sparse n-length Discrete Fourier Transform using at most 4k samples and O(k log k) complexity
• SHO-FA: Robust compressive sensing with order-optimal complexity, measurements, and bits