ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2014, Vol. 51 ›› Issue (9): 2101-2107.doi: 10.7544/issn1000-1239.2014.20131148

Previous Articles     Next Articles

Detouring Matching Pursuit Algorithm in Compressed Sensing

Pei Tingrui1,2, Yang Shu1,2, Li Zhetao1,2,3,Xie Jingxiong1,2   

  1. 1(College of Information Engineering, Xiangtan University, Xiangtan, Hunan 411105);2(Key Laboratory of Intelligent Computing & Information Processing (Xiangtan University), Ministry of Education, Xiangtan, Hunan 411105);3(School of Computer, National University of Defense Technology, Changsha 410073)
  • Online:2014-09-01

Abstract: Detouring matching pursuit (DMP) is a greedy algorithm of reconstructive sparse signals with low computational complexity, high accuracy and low column-correlation demand for sensing matrix. The increasing and deceasing formulas of the submatrix's inner-product and the coefficient matrix in the DMP are put forward and proved. By using the inverse of submatrix's inner-product and the coefficient matrix, DMP could reduce the amount of calculation of residual error's variable quantity and obtain light computation complexity in the end. In addition, by using the method of decreasing firstly, and then increasing the element of the assumed support set one by one optimally, DMP could improve the reconstructive accuracy and broaden the range of sparsity of reconstructing the sparse signal. The analysis of algorithmic complexity shows that the algorithmic complexity of getting, deceasing and increasing the assumed support set is O(K2N), O(b(K-b)N) and O(b(K-b)N), respectively. The experiment of indirect reconstructive weighted 0-1 sparse signal shows the reconstructive accuracy of the DMP, greedy pursuit algorithm (GPA), subspace pursuit (SP), compressive sampling matching pursuit (CoSaMP) and orthogonal matching pursuit (OMP) are 99%, 65%, 0%, 0% and 13% separately for 0-1 sparse signal with M/2 sparsity. The experiments of sparse signals in which the non-zero values obey normal distribution also show the reconstruction accuracy of DMP has obvious superiority.

Key words: compressed sensing, greedy algorithm, detouring matching pursuit, block matrix, sparse solution

CLC Number: