基于边膨胀图的压缩感知理论  

Compressive Sensing Theory Based on Edge Expander Graphs

作　　者：伍政华[1] 王强[1] 刘劼[1,2] 孙明健[1] 沈毅[1] 

机构地区：[1]哈尔滨工业大学控制科学与工程系,哈尔滨150001 [2]美国微软研究院,美国雷德蒙德98052

出　　处：《自动化学报》2014年第12期2824-2835,共12页Acta Automatica Sinica

基　　金：国家自然科学基金(61174016,61201307,61371045);中央高校基本科研业务费专项资金(HIT.NSRIF.2013132)资助~~

摘　　要：膨胀图(Expander graphs,EG)理论与压缩感知(Compressive sensing,CS)理论相结合是近几年发展起来的一个新方向,其优点在于能设计出具有确定结构的0-1测量矩阵,且可根据膨胀图的结构协同设计重建算法,相当于在重建算法中引入了先验知识,能更快更准确地重构出稀疏信号.本文从非均匀采样的必要性和合理性分析出发,在已有的膨胀图压缩感知理论基础上,将膨胀图的定义拓展到左顶点度数不相等的边膨胀图,并建立起边膨胀图邻接矩阵与有限等距性质(Restricted isometry property,RIP)条件之间的联系,又进一步给出了边膨胀图邻接矩阵的列相关系数的上限值.同时根据边膨胀图的特性,协同设计了两种压缩感知重建算法.通过仿真实验对比边膨胀图代表的非均匀采样模式与现有膨胀图代表的均匀采样模式,以及本文设计的算法与传统算法在重建稀疏信号上的性能,实验结果验证了边膨胀图压缩感知理论的有效性.It is a new research direction to explore expander graphs for compressive sensing （CS）. Using expander graphs for compressive sensing has several advantages, such as incorporating 0-1 deterministic structure measurement matrices, and fast and accurate recovery of sparse signals by leveraging prior knowledge. In this paper, we extend the notion of expanders with irregular left vertices degrees for non-uniform sampling. Through analyzing the relationship between adja- cent matrices in edge expander graph and restricted isometry property （RIP）, we obtain the upper limit of the coherence of the adjacent matrices. Based on these results, we design two algorithms for non-uniform sampling and correspond- ing sparse signal recovery. We evaluate the algorithms with numerical experiments. Finally, the experimental results demonstrate that the proposed non-uniform sampling pattern together with the algorithms have better performances on recovering sparse signals with known support set, as compared to the previous approaches.

关 键 词：压缩感知 边膨胀图 非均匀采样 邻接矩阵 稀疏重建 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]