Summary
The 2018 International Symposium on Information Theory and Its Applications　(ISITA2018)
2018
Session Number:Tu-PM-1-4
Session:
Number:Tu-PM-1-4.2
Recovery Guarantee of Sparse Binary Sensing Matrices under Greedy Algorithm
Wen-Yao Chen, Wen-Yao Chen,
pp.423-426
Publication Date:2018/10/18
Online ISSN:2188-5079
DOI:10.34385/proc.55.Tu-PM-1-4.2
PDF download
Summary:
The theory of compressed sensing was established independently by Donoho and by Cand`es et al.. The main result of compressed sensing is that one can recover a high-dimensional sparse signal through a small number (far less than the signal dimension) of linear random measurements by convex optimization. It means that a sparse high dimensional signal can be compressed as a low dimensional signal. Orthogonal matching pursuit (OMP) and l1-minimization are two main reconstruction algorithms. The OMP algorithm is an iterative greedy algorithm and has the advantage of easy implementation. In this paper, we use a class of structured sparse binary matrices to be measurement matrices and study their recovery guarantee under the greedy OMP algorithm. These matrices are parity-check matrices of LDPC codes. It was reported that according to simulation results, parity-check matrices constructed by progressive edge-growth (PEG) algorithm can have better recovery rate than random Gaussian matrices under the OMP algorithm. But there is still no literature about theoretical analysis on this topic. In this paper, we show that the OMP algorithm does not provide the same recovery guarantee as l1-minimization for general parity-check matrices of LDPC codes. A modified OMP algorithm that reaches the same recovery guarantee as l1-minimization is proposed.