Deterministic Constructions of Binary Measurement Matrices From Finite Geometry

DOI10.1109/TSP.2014.2386300MaRDI QIDQ4579753zbMATH OpenFDO

Authors Xin-Ji Liu, Yong Jiang, Haitao Zheng, Shutaong Xia

Publication date 22 August 2018

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.5952

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: Deterministic constructions of measurement matrices in compressed sensing (CS) are considered in this paper. The constructions are inspired by the recent discovery of Dimakis, Smarandache and Vontobel which says that parity-check matrices of good low-density parity-check (LDPC) codes can be used as {provably} good measurement matrices for compressed sensing under $el{l}_1$-minimization. The performance of the proposed binary measurement matrices is mainly theoretically analyzed with the help of the analyzing methods and results from (finite geometry) LDPC codes. Particularly, several lower bounds of the spark (i.e., the smallest number of columns that are linearly dependent, which totally characterizes the recovery performance of $el{l}_0$-minimization) of general binary matrices and finite geometry matrices are obtained and they improve the previously known results in most cases. Simulation results show that the proposed matrices perform comparably to, sometimes even better than, the corresponding Gaussian random matrices. Moreover, the proposed matrices are sparse, binary, and most of them have cyclic or quasi-cyclic structure, which will make the hardware realization convenient and easy.

Recommendations

• Deterministic Constructions of Compressed Sensing Matrices From Unitary Geometry
• Deterministic Construction of Sparse Sensing Matrices via Finite Geometry
• scientific article; zbMATH DE number 89638
• Deterministic constructions of compressed sensing matrices
• Deterministic construction of compressed sensing matrices over finite sets
• Complexity metric and structural measure on the class of deterministic matrices
• scientific article; zbMATH DE number 4039793
• Deterministic construction of compressed sensing matrices from codes
• Geometric search for Hadamard matrices
• Deterministic Construction of Binary, Bipolar, and Ternary Compressed Sensing Matrices

Cited in

(4)

• Sparse recovery properties of discrete random matrices
• Peeling decoding of LDPC codes with applications in compressed sensing
• Deterministic construction of sparse binary matrices via incremental integer optimization
• An effective algorithm for the spark of sparse binary measurement matrices

This page was built for publication: Deterministic Constructions of Binary Measurement Matrices From Finite Geometry

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4579753)