ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2014, Vol. 51 ›› Issue (9): 2101-2107.doi: 10.7544/issn1000-1239.2014.20131148

• 图形图像 • 上一篇    下一篇

压缩感知中迂回式匹配追踪算法

裴廷睿1,2,杨术1,2,李哲涛1,2,3,谢井雄1,2   

  1. 1(湘潭大学信息工程学院 湖南湘潭 411105);2(智能计算与信息处理教育部重点实验室(湘潭大学) 湖南湘潭 411105);3(国防科学技术大学计算机学院 长沙 410073) (chu5044130@sohu.com)
  • 出版日期: 2014-09-01
  • 基金资助: 
    基金项目:国家自然科学基金项目(61372049,61379115,61100215,61311140261,61070180);湖南省自然科学基金项目(13JJ8006,12JJ9021);湖南省科技厅科技计划项目(2011GK3200);湖南省重点学科建设项目

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

摘要: 迂回式匹配追踪(detouring matching pursuit, DMP)是一种计算复杂度低、准确率高、对传感矩阵列相关性要求低的贪婪重构稀疏信号算法.DMP中子内积逆和系数矩阵递增递减核心式被提出并证明,DMP利用子内积逆和系数矩阵减少残差误差变化量的计算量,达到降低计算复杂度的目的.另外,DMP采用先逐个最优缩减、后逐个最优扩增假定支撑集元素的方法提高重构准确率和扩大重构稀疏信号的稀疏度范围.DMP算法复杂度分析表明,DMP算法中获取、缩减和扩增假定支撑集的复杂度分别为O(K2N),O(b(K-b)N)和O(b(K-b)N).加权间接重构0-1稀疏信号实验结果表明,对于稀疏度为M/2的0-1稀疏信号,DMP、逐步贪婪追踪(greedy pursuit algorithm, GPA)、子空间追踪(subspace pursuit, SP)、压缩采样追踪(compressive sampling matching pursuit, CoSaMP)、正交匹配追踪(orthogonal matching pursuit, OMP)的重构准确率分别为99%,65%,0%,0%和13%.非零值服从正态分布的稀疏信号实验结果也表明DMP的重构准确率优势显著.

关键词: 压缩感知, 贪婪算法, 迂回式匹配追踪, 分块矩阵, 稀疏解

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

中图分类号: