第１期
２０１１年１月
电
ＡＣ½Ａ
子
学
报
ＳＩＮＩＣＡ
Ⅷ．３９
Ｎ½．１
ＥＬＥ½：ＴＲＯＮ½ＣＡ
Ｊ½½．２０１１
压缩传感理论与重构算法
杨海蓉１，一，张成１，丁大为１，韦穗１
（１．安½大学计算智½与信号处理教育部重点实验室。安½合肥２３００＂３９；
２．合肥师范学院数学系，安½合肥２３００６１）
摘要：
压缩传感Ｊ靴（Ｃ½½½½½½½½½½
Ｓ½½½½½½，ＣＳ）以远½于Ｎ½½½½½½采样频率的非适应性测量和优化方法高概率重
压缩传感；稀疏表示；信号恢复；无线传感½络；模拟一信息½换
文献标识码：
Ａ
构信号．本文介绍了½Ｓ的基本理论、重构算法，包括贪婪、凸优化方法及我们提出的ＭＢＯＯＭＰ算法；同时，采用½½组
成的随机信号进行性½比较的模拟实验，结果表明我们的算法优于传统的ＯＭＰ算法．
关键词：
中图分类号：ＴＮ½½½．７２
文章编号：０３７２．２１１２（２０１１）０１－０１４２－０７
Ｔ½½
Ｔ½½½½½ ½½ Ｃ½½½½½½½½½ Ｓ½½½½½½ ½½½
Ｒ½½½½½½½½½½½½½
Ａ½½½½½½½½
ＹＡＮＧ Ｈ½½．½½½½Ｉ ½，ＺＨＡＮＧ Ｃ½½½９１，ＤＩＮＧ
Ｄ½－½½½Ｉ，ＷＥＩ
Ｓ½½½
（１．研／½／，½½½½½½½
½½½½½½½／½½½
½。呷½妇½＆Ｓ匆以№抛，Ａ½½½／Ｕ½／½½½½½½，哟瓴，加托２３００３９，踟Ⅺ；
２．Ｍ½½Ａ½½½Ａ½伪Ⅻ咖酬，Ｈ扣Ｎ½½½／№毋，她触，加觚２３００６１．秭如）
½
½½
½［删½½
½½½ ½½½½
Ａ½½½½½½½：½∞叩½涵½½
½½½½½½½，½½
½咖½½
½½½ ½½½－½½½½½½½½ ½朗捌把½既吐½ ½½½½ ½½½½ ½½½½½ ½½½ Ｎ½½½½½½ ½½½½½½½½½ ½½½
½½½½½½½，魁：０½吣呲½
½½删½½½½
½½½½ ½½½½½½½½½½½．Ｉ½ ½Ｉ½½½ ½½½½½，½½ ½½½½½½½½½ ½½½
½½½½½山∞叮½½
½½Ｗ½黜½
½½½½½½½ ½½½
½½½½
½½
½½ ½½½
½删髓½½½½∞½½½½½½½½½½．½½½½½½½½½
½½½½½½½ ½½½½½½½½½½
½½½
½½½½½½½½
ＭＢＣＯＭＰ ½½½½½½½½½．Ｍ½½½½½½½½，½½½
½½½・
½½½
½½½½½½½ ½½ ½½½½½ ½½½½½½ ½½½½½ ½½ ½½½½½½½½ ½½ ０ ½½½ １
½½½½½½ ½½½½ ½½½½½½½
ＯＭＰ
½½½½½½½½½．
½½Ｉ½础½½
½½½½½½½ ½½½½½
½½币砌皿½∞．Ｉ½
½½ ½½½½½ ½½½½
½½½½½½½½½ ½½
½½∞
脚½Ｄ陆：½½½印∞½½½½½
½½½½½½½；½½½½½½
½½½嫩½½½½½½½；½½½½½／½½½½½½½½；½½½½½½½½脚∞眺；½½½½½½－½½－½½½½½½½½½
½½½½—
１引言
传统的Ｓ½½½½½½／Ｎ½½½½½½采样定理指出，带限信号的
采样频率必须大于其带½的两倍才½确保完全重构原
始信号．近几年来，½为Ｓ½½½½½½／Ｎ½½½½½½采样定理的另
一种选择，压缩传感（ＣＳ）理论备受大家关注．此理论最
初是由Ｄ½½½½½（美½科学院院士）、Ｅ
Ｃ½½½½½（Ｒ½½½½½½½，
Ｃ½½½½½½½创始人）及华裔科学家Ｔ Ｔ½½（陶哲½，２００６年菲
尔茨奖获得者）等人提出，２００６年ＩＥＥＥ
Ｉ½½½½½½½½½½
Ｔ½½½½½½½½½½½
½½
框架，它把物理、计算和数值方法有机地结合起来去解
决大而复杂的问题．其随机编码过程非常简单，仅需要
计算非相干投½而不做任½其它的处理，采用“少采样，
巧计算”的原则，把技术负担从传感器½移到后台处理
器．Ｃ½的研究思想挑战了Ｓ½½½½½½／Ｎ½½½½½½采样定理的
理论极限．对信号的测量数量远小于传统Ｓ½½½½½½／
Ｎ½½½½½½采样数鼍，½½带信号的处理更加有效．而ＣＳ
理论精确蕈建原始信号依赖于两个先验：信号的稀疏性
和测量矩阵与测量基之间的非相干性，测量矩阵的限制
等容条件（Ｒ½½½½½½½½½
建提供了理论保证．
½½主要思想是对一类具有稀疏先验的信号，先经
小部分非线性采样，其包含足够信息良½逼近信号，再
通过一定类型的线性或非线性解码机制就町高概率精
确重建原始信号（见图½‘７ Ｊ），我们采用稀疏投½矩阵和
非常稀疏投½矩阵为测量矩阵。利用基于½．模最小化
模型½½½½½Ｉ
½忆½．½．氨＝Ｙ，Ｎ＝４０９６，小½½图像稀疏
Ｉ½½½½½½½
Ｔ½½½½½上发表的“Ｃ½½½½½½½½½
Ｓ½½½½½½”Ｌ½
½的文
Ｐ½½½½½½½，Ｒ伊）旧。也为精确重
章中首次被系统地论述．该理论一经提出，在信号处理
的多个领域得到高度关注和应用，并被美½科技评论评
为２００７年度十大科技进展．且ＣＳ理论已发展了分布½½
理论。２，３１（Ｂ刮½½½½等提出）、½—ＢＩＴ ＣＳ理论．４ Ｊ（Ｂ½½½½½½½等提
出）、Ｂ½½½½½½½
ＣＳ理论一１（Ｃ½½½½等提出）、无限维½½理论
（Ｅ½½½等提出）等，成为数学领域和工程应用领域的一大
研究热点．½½理论是信号处理领域新近发展的一种新
收稿日期：２１）０９－１１－０３；修回日期：２００９—１２．３０
基金项目：教育部博士点基金（Ｎ½．２００７０３５７００３）；。新一代½带无线移动通信½”½家科技重大专项（№．２００９ＺＸ½½Ｂ００６－００１４１２）
万方数据
第１期
杨海蓉：压缩传感理论与重构算法
１４３
度Ｋ＝４２４，（图像来自计算机视觉图像库（½½½½：／／½½½½½．
½½½½½½½．½½½．½½／一½½½½）））．
个病态的求逆问题．½是，原始信号½很强的稀疏性给
出了从Ｍ个测量中审建工的希望．事实上，可以通过寻
找满足Ｊ，中Ｍ个测量向量的最稀疏信号，即信号工是
下列Ｚ。最小化问题的解
½＝½＇½
½½½½１ ½½½½
½．½
Ｙ
２锄
（４）
½是，众所周知，解决½０最小化问题是一个ＮＰ．问
题【８１．因此，Ｄ½½½½½在文献［９½中提出了基于最小化Ｚ½
模的等价线性优化模型，也就是利用基于线性规划的
基½踪（Ｂ½½½½ Ｐ½½½½½½，ＢＰ）方法求解：
½＝½½½ ½½½
圈Ｉ利用稀疏投½矩阵和非常稀琉投½矩阵的小½½的
重建结果
Ｃ½理论的三个组成要素是信号的稀疏变换（目前
的稀疏变换有离散½弦变换（ＤＣＴ），小波（½½½½½½½）。
½½½½½½½½，过完备原子分解（½½½½½½½½½½½½
½½½½
½½½½½½½½½—
½½½½）等）；稀疏信号的非相干测鼍（目前的测量方式为线
性测量）及稀疏信号的重建算法．其中，快速稳定的重
建算法是将½½推向实用化的关键之一，也是Ｃ½的主
要研究内容之一．
Ｉ½工ＩＩ
Ｉ Ｂ．½
Ｙ＝½
（５）
其中咖应该满足限制等容条件（ＲＩＰ）１６Ｊ，即
定义２（限制等容条件）
称一个测最矩阵满足①
具有参数（Ｋ，½），￡∈（０，１）的限制等容条件（ＲＩＰ），若对
所有的Ｋ一稀疏向鼍，有（１一½）０口ＩＩ
２≤Ｉ½咖½Ｉ
２≤（１
＋½）½Ｉ移Ｉ½２．限制等容条件声明口的每个Ｋ列集合近
似一个正交系统．
通常，基于线性规划的解码器求解需要承个投
½，其中½—½½½½（１＋Ｎ／Ｋ）［引，重建复杂度为０（Ｎ３）【引．
Ｃ½½½各½和Ｔ舯。½½½证明了在一个更强（数量）的条件下，稀
疏恢复问题等价于问题（４）和（５）；即
定理。１０Ｊ（限制等容条件下的稀疏恢复）．假设测
（１）
量矩阵。满足具有参数（２½，０．２）的限制等容条件．则
每一个½一稀疏向最工（上面表示为½，）½够½为凸优
２背景知识
定义１（稀疏信号）给定一组基甲＝½戗½墨１（为简
单起见，假设½为标准正交基），如果信号工可以表示
成甲中Ｋ个基向量的线性组合½式：
Ⅳ
膏
工＝∑口拟（或甄）＝∑％如。
½＝Ｉ
』；１
则称工为Ｋ稀疏信号．其中系数％＝（½，以）＝妒缸，可
见对同一信号而言，工和Ⅱ是该信号的两种等价描述½
式，工为信号在时间域上的表述，口为其在甲变换域上
的表述．
事实上，真实和模拟的信号在任½正交基上½未
必有精确的稀疏描述，而是在适½选择的基上具有某
种可压缩的性质．我们称½用Ｋ项向量的线性组合良
½逼近的信号为可压缩信号；即
化问题（６）的唯一解从其测量呶中被精确重建．
３信号重建的贪婪算法
从背景知识介绍中，我们知道快速稳定的重建算
法是将ＣＳ推向实用化的关键之一．目前蓖建算法主要
地算法包括三类：凸优化方法。贪婪算法和组合算法．
目前文献中提出的凸优化方法有内点方法。１１½、预
计梯度法Ｌ２ Ｊ、以及迭代阈值１３Ｊ３、迭代硬阈值（１½’）１４．６Ｊ、
占
工一½量＝己口（。）妒（。）
（２）
基于上面的概念，所谓的ＣＳ理论为：在适½选择
的基甲＝（妒½。仍，…，“）上具有Ｋ稀疏描述的，、½采样
基于布雷格曼（Ｂ½½½½½½）距离的Ｂ½½½½½½迭代【１２ Ｊ等．凸
优化方法½够高概率得到信号的精确重建，通过解决
一个凸优化问题，用其极小化逼近目标½数．
贪婪算法的主要思想是通过迭代计算工的支撑．
主要包括匹配½踪（ＭＰ）１９½，正交匹配½踪（ＯＭＰ）１１３ Ｊ（我
们改进的ＭＢＯＯＭＰ算法【１４ Ｊ），以及正则化的正交匹配½
踪（ＲＯＭＰ）Ｌ１
５Ｊ、逐步正交匹配½踪（Ｓ＇ＩＯＭＰ）¨６Ｊ、压缩采
信号½Ｅ四Ⅳ，可通过它在另一组非相干基½＝（料，孵，
…，％）上的Ｍ（Ｋ≤肼《Ｎ）个线性投½（测量）Ｙ（½）＝
＜膏，辨＞，½∈½½，２，…，肘½获得精确重建．即
其中，½为测量基．倒称为传感系统，Ｙ为测量向量，
由测量基Ｄ构成的Ｍ×Ｎ维矩阵为测最矩阵．为方便
起见，本文中假设稀疏基甲由单½向最构成，故我们的
目标是通过Ｍ（肘《／½）维测鼍向量Ｙ精确重建或者逼
近信号工．
由条件Ｋ≤Ｍ《Ⅳ看出½Ｓ理论主要解决的是欠采
样情况下的信号重建Ｉ’½Ｊ题，信号工的恢复本质上是一
Ｙ＝撅＝½％
（３）
样匹配½踪（½½½½ＭＰ）¨７Ｉ、子宅问½踪（ＳＰ）协Ｊ等．
组合算法要求对信号高度结构化地采样。经由群
测试快速恢复支撑．这类算法包括傅立叶采样Ｌ５ Ｊ、链½
踪。悖Ｊ、ＨＨＳ½踪。∞Ｊ以及Ｃ½½½½Ｍ½．Ｍ½½½½½½½½½½卸【½４１和Ｉ．
½½½汪¨的一些算法．
本文中。我们梳理了有关箅法，特别是目前½用频
率比较高并且有代表性的凸优化算法和贪婪算法，详
万方数据
１４４
电
子
学
报
２０１１矩
细阐述了主要算法的数学框架．
３．１匹配½踪（ＭＰ）与正交匹配½踪（ＯＭＰ）
以＝矗一Ｉ＜以，％＞１２，½。＝Ｉ
½。１２／½½；
（３）令½＝½＋１，寻找索引Ａ。，½得Ａ。＝½瑗½掣８。，记
Ａ。＝Ａ。一½
我们的目标是从Ｙ＝呶重建最稀疏的½，这两种
算法均通过确定。的哪一列参于测量向量Ｙ中来确定
工的支撑，运用贪婪模式去确定每一列．在每次迭代中，
选择①中与Ｙ的剩½部分最相关的列，然后从½中½
取该列对Ｙ的贡献再对其冗½迭代．
在表１至表７中，＾表示残差，½表示迭代次数，ＡＩ
表示½次迭代的索引集合
表１
ＭＰ重建算法：
（１）初始化：½０＝Ｙ，½＝１
（２）找索引Ａ－，½得：Ａ½２
Ｕ½Ａ。½．记：ＩＩ
Ｒ
０ ２＝ＩＩ
Ｒ½—½
ＩＩ
２一½½．，以＝
亮肛乏・
（４）对½＝１，…，½一１计算新的投½和分解系数：
½＝½一晟＜仇。，风＞，Ｃ。＝Ｃ。一＜仇．，½＞ＣＩ
（５）重复（２）．（４）直到对于给定的小正数艿，满足
½½袁。０ ２≤艿时，迭代停止．
（６）对于，½＝½，…，Ｐ，我们依次计算；＝（帚，
½½½』：黑“Ｉ＜½½－½，Ｑ＞Ｉ
（３）计算新的近似毛和残差＾：毛＝＜½Ｉ．１．蛾。＞，＿＝½—Ｉ一毛
（４）Ｉ＿Ｉ
４－１．如果½＜Ｋ．返回第（２）步．
薷，…，薷）’，消除；中½—½个最小的系数，并消除
这个系数对应的原子，从而获得新系数向量工。＝
ＭＰ算法由于信号在已选定原子（测量矩阵的列向
量）集合上的投½的非正交性½得收敛可½需要经过
较多次迭代．常用的正交匹配½踪算法（ＯＭＰ）则通过
递½地对已选择原子集合进行正交化以保证迭代的最
优性，从而减少了迭代次数．
裹２
ＯＭＰ重建算法：
（１）初始化½½＝，，，Ａ½＝声，½＝½
（２）找到索引Ａ。，½得：Ａ。＝½½½
（帚，帚，…，青）Ｔ和原子集合钒，．『＝１，…，½・
在这几种基本迭代算法中，每次迭代均只选择与
残差最相关的一列，自然人们会想：“每次迭代是否可
以多选几列呢？”基于这种思想，许多基于ＯＭＰ的迭代
方法在近几年被提出．
３．２正则化的正交匹配½踪（ＲＯＭＰ）
ＲＯＭＰ结合了贪婪算法的速度、简便和凸优化方法
艘，½＜＾．１’嘭＞Ｉ
的强力保证．在具有参数（２Ｋ，０．０３Ａ／½½½Ｋ）的限制等
容条件下，ＲＯＭＰ½从它的测量Ｙ中精确地恢复一个½
稀疏信号工．特别地，ＲＯＭＰ的运行时间与ＯＭＰ在理论
上是相½的，½在实际中½于ＯＭＰ．
ＲＯＭＰ算法：
（３）令Ａ。＝ＡＩ－½Ｕ½Ａ。½
（４）计算½嘲：Ａ∈＾。½张成空间的正交投½只
（５）计算新的近似毛和残差½½：≈＝．Ｐ∥，Ｉ＂½＝Ｙ一氟
（６）Ｉ－½＋½，如果½＜Ｋ，返回第（２）步．
（７）获得的估计五在索引Ａ½½½的元非零．且在该½½的测量向
量逼近为：妇＝∑；扁
＾∈ＡＫ
ＯＭＰ算法的运行时间是第二步决定，总的耗费是
Ｄ（拖½／、½）．
针对ＯＭＰ中原子选择机制相对新的冗½误差的非
最优性，文献［２８½中采用ＯＯＭＰ的选择准则来代替ＯＭＰ
中的选择准则．½由于ＯＯＭＰ算法没有限制迭代次数，
因此一般有Ｐ≥½，也就是说存在误选原子．因此我们
提出一种新的原子选择机制称为改进的后退型最优
ＯＭＰ算法：１４½（ＭＢＯＯＭＰ），逐步向后剔除多½的原子，直
到剩½原子个数与稀疏度相同为止．（ＭＢＯＯＭＰ算法如
下：
（１）初始化½½＝Ｙ，记靠＝％，½＝½，…，Ⅳ，取索引
爆羧翥蠹集…Ｊ½Ｃ…Ｊ中：徘½（½）Ｋ
Ｉ（３）选择：
Ｉ（２）鉴定：计算Ｈ＝＜½—½，½＞
Ｉ标，选两者小的那个，设为．
Ｅ½Ｊ
½（４）则化：在所有具有可比较坐标的子
个最大的非零坐标构成的集合或者它的所有非零坐Ｉ
Ｊ½
”
Ｊ
½（５）更新：增加如到指标集：
½零Ｉ引
≤Ｉ
Ｉ：ＩＩ＝卿½＜％，，，＞Ｉ，索引集合ＡＩ＝½．；½½½，正交投½
½数妒½＝仇．＝½½和分解系数膏½－＜仇．，½＞，迭代计
数Ｉ＝½；
（２）对½＝１，…，Ⅳ，分别计算：以＝靠一识＜识，％
＞，½。＝＜靠，，，＞
万方数据
第１期
裹４
½Ｐ算法
杨海蓉：压缩传感理论与重构算法
１４５
关于此算法的迭代停止标准，亦可以用一个固定
的迭代次数，实际上也有一些其它简单的停止标准．
（１）初始化：Ａ＝Ｉ相应口。½绝对值最大的Ｋ个指标½。½，＝蒯
（½．½＾）：＝½一吼½½
（２）迭代：若竹＝０。退出迭代；否则继续．
（３）½＝Ａ
Ｕ½½’弗绝对值最大的Ｋ个指标½。‰’＝口½，，，Ａ’＝
½相应½。’最大元的Ｋ个指标½，½，＝½½／（½，½½，）
（４）更新：若½½
½，０＞ＩＩ弗０，退出迭代；否则，设Ａ＝Ａ’以及弗＝
４信号重建的凸优化方法
解决ＣＳ问题的另一种受欢迎的方式是½。模最小
化模型：
工＝½½½½½½½½½½ ０
½
８．½
½＝∞譬
（６）
４．１迭代硬阈值（ＩＨＴＢ）
迭代硬阈值算法½有效减少每次迭代中的误差，
在一个可达到的最½误差估计的一个常数因子内被保
证．事实上，这个算法需要一个固定的迭代数目，仅仅
依赖于信噪比率的一个½式的算法．
裹７
；，，继续迭代．
输出：满足；１１．…．Ⅳ½．＾：０以及如＝口如的估计信号；
３．４逐步正交匹配½踪（鲫脚）
ＳＴＯＭＰ的目标是从测最向量Ｙ中重建实际信号工，
得到工的一个逼近解；，其中测量矩阵。来自于ＵＳＥ
（Ｕ½½½½½½
Ｓ½½½½½½½½
Ｅ½½½½½½½），½的列是单½球上的独立
Ｉ眠算法
（１）初始‘解’知＝０，初始残差½½＝，。计数器Ｉ＝０．
（２）计算½Ｉ＋½＝髫Ｉ＋口’½（，一ＩＩ却½‘）
同分布点）．
裹５
ＳＴＯＭＰ算法：
（１）初始‘解’工＝０。初始残差½½＝，，计数器½－½－
（２）计算½＝０７
½½—Ｉ＿＜½，½½．Ｉ＞
（３）选择最大的Ｋ个元：½。＋１－肌（４。＋Ｉ）
其中见是硬阈值算子，保持数量大小的最大的½个元，设½
其它的元为零．
（４）满足迭代停止条件，否则½－½＋１．返回第（２）步
注：这里迭代停止条件可选择具½的适代次教．
（３）通过阈值产生“大”坐标的一个集合：＾＝½Ｊ：Ｉ ½Ｉ（，）Ｉ＞½矶½，
以是一个噪音水平，½½是一个阁值参数．
（４）更新支撑估计：＾。＝ＡＩ－½ Ｕ＾，在支撑＾．上得到新的逼近氟，
４．２布雷格曼（Ｂ½½½½½½）迭代
布雷格曼迭代正则化由Ｏ½½½½等在图像处理的背
景下提出，可应用到压缩传感上．对标准的½Ｉ最小化问
为（毛）＾＝（½Ｘ饥）“口½，．其中饥表示。中仅取支撑，对应
的列构成的新矩阵．
（５）更新残差为：½½＝，一毗
（６）检查终止条件（例如½＝１０）．若还没到停止时间，假设½：＝½＋
½，½到步骤（２），若到了停止时间，五＝毛．
注：规范噪音水平仉＝０＾ＩＩ ２／／½。典型的阚值参数取值范围为
２≤½½≤３．
题：½½½½½½½工忆½锄＝½½，Ｂ½½½½½½迭代方法在一个有限
的步骤内产生精确的解，呈现数值结果．
裹８
３．５可压缩采样的匹配½踪（Ｃ½Ｓ½ＭＰ）
Ｃ½Ｓ½ＭＰ算法本质上是一种贪婪算法．它结合了组
合算法中的思想以保证速度，提供了严格的误差界旧Ｊ．
这个分析来源于ＲＯＭＰ上的工½以及Ｃ½½½爸½－Ｒ½½½½½½－
Ｔ½½在凸优化方法上的实现保证．
假设测量矩阵口具有限制等容常数乱，Ｇ０．１．
注：Ｄ；（“．口）＝Ｊ（Ⅱ）一．，（口）一＜Ｐ．½一口＞。½（½）＝产０
½
０ Ｉ为
Ｂ½½½½½½½距离，½口∈½½（口）是可½½数，在点＂的次梯度中的一个元。
这里遮代根据具½的误盖要求确定进代停止务件．
５模拟实验
我们知道，通常自然图像本身可½非稀疏．½通过
变换，它们可在某种基下稀疏或可压缩．所以基的选择
会对整个Ｃ½理论恢复原始图像的质量有较大½响．本
文中，为了在同等条件下客观地反映上述算法的重构
性½．我们采用本身稀疏的０一½随机信号来进行比较，
这也是文献中通常采用的方法．
本节中，我们做了½种验证．首先是对本身稀疏的
０一½随机信号，用表２至表８的７种算法进行重建性½
万方数据
１４６
电
子
学
报
２０１１年
验证（见图２）；其次，由于重建中测量矩阵的随机性，通
过多次实验来比较上述７种算法以及我们改进的
ＭＢＯＯＭＰ算法的苇建结果．比较的标准仍然是测量次
数以及稀疏度和算法成功概率之问的关系，比较的结
果如图３和４．
大，相比较而言，Ｃ½Ｓ½ＭＰ以及½Ｐ算法精确恢复原始信
号所需测量次数相对较少．从图３和图４中可发现，我
们的Ｍ½½½½½算法½然沿用ＯＭＰ算法每次迭代取一个
元的机制，½在同等稀疏度或者测量次数条件下，信号
重构效果明显½于ＯＭＰ算法．
÷Ｅ臣三垩匠巨更匹四
．；Ｅ基量王珏王匾至三王翌
；Ｅ匿三匹匠豆正里丑
．
½½Ｓ½ＭＰ
½½½½½½½½½½½
½½½＝５．３０７Ｉ½．０Ｉ ５
Ｓ½（）ＭＰ
½½½½½½½½½½½
½½＇：７．７５２１½．０１５
Ｓ½½½½½½½ Ｋ
．；Ｅ墨三歪巫王匾至三王丑
Ｂ½½½½½½
½½½½½½½½½½½
．½
Ｅ匿量至匠墨正翌丑
½½½－－４．７９９４½－０½ ５
圈３
Ｎ＝２５６，Ｍ＝１２８时，改变信号的稀疏度，ＯＭＰ，ＲＯＭＰ，Ｃ½Ｓ½ＭＰ，
Ｓ½ＯＭＰ，ＩＨＴ，Ｂ½½½½½½，ＳＰ，ＭＢＯＯＭＰ算法重建结果的比较
１
½Ｅ玉主兰里玉丑曼匠翌三巨壬丑
Ｓ½½½½½½½ Ｐ½½½½½½
½½½½½½½½½½½
½½½½½½½½½．一½½ＴＩ－½½½½½½½½½½
½½½½½½½½½½½
½½Ｆ２．９７
Ｉ Ｉ ½．００７
０９
０ ８
Ｏ ７
Ｏ ６
０ ５
Ｏ
４
．½Ｅ匿三王匠墨芷里丑
½½½＝４ ８５８４½一０ Ｉ ５
刀
萎－＊－－黧½½½Ｔ∥／斗
Ｍ½½½½½
½ＴＴ一３．５６８３½．０１ ５
１日玉王翌墨翌½王翌
圈２
０ ３
０ ２
Ｎ＝５１２，Ｋ＝４０，Ｍ＝２５６时，ＯＭＰ．ＲＯＭＰ．Ｃ½Ｓ½ＭＰ，ＳＴＯＭＰ，
Ｂ½½½½½½，½½½½，ＳＰ，ＭＢＯＯＭＰ算法的重建结果
基隶忸½督镁岳魏林聪蝴嚣½½
０
１
首先，假设信号长度Ｎ＝５１２，稀疏度Ｋ＝４０，测量
次数Ｍ＝２５６，采用高斯随机测量矩阵咖∈∥一：½（½，
图４
Ｊ）＝了１½纷，其中仇．，一Ｎ（０，１），上述算法均高概率重
Ｖ肘
建原始信号，如图２所示．
从图２可看出，在充分的测量次数下，各种算法均
高概率恢复信号，为了进一步比较各种算法之间的重
建效果和信号稀疏度以及测量次数之间的关系，我们
再次采用本身稀疏的０—１随机信号，通过假设Ｎ＝
２．５６，Ｍ＝１２８，改变信号稀疏度，以及假设Ｎ＝２５６，Ｋ＝
３０，改变测量次数，分别来进行５００次模拟实验，所得结
果如图３、图４所示．
从图３可看出，测量次数一定，随着信号稀疏度的
增加，信号蕈建的概率逐渐减小，在信号非常稀疏的情
况下，均高概率精确蓖建原始信号，½ＯＭＰ，ＲＯＭＰ成功
Ｎ＝２５６，½＝３０时，改变测量次数，ＯＭＰ，ＲＯＭＰ。Ｃ½Ｓ½ＭＰ，ＩＨＴ，
ＳＴＯＭＰ。Ｂ½½½½½½，ＳＰ，ＭＢＯＯＭＰ算法重建结果的比较
：◆
：；２胪矿拶
一涩型．Ｉ
Ｍ½½½½½½½½½½½＾，
／髟／／½
６总结和展望
本文主要梳理了重构计算中主要的贪婪算法和凸
优化算法，并通过模拟和比较实验进一步验证了各种
算法的优缺点．我们认为，½然此综述不是穷½的，½
是可以为有关研究和应用提供工具．我们进一步的方
向是寻找更优Ｃ½测鼍矩阵类；发展更有效和½复杂度
算法．与此同时，我们将高度莺视有关应用．例如Ｒ½½½
大学的Ｊ½½½½
Ｒ½曲½½
等人在文献［２２½中提出压缩传感理论直接模拟一信息
Ｎ
½½【½以及密西根大学的Ｔ½½½½
变为可½，给出模拟一信息½换的一个框架，并为原型
ＡＩＣ提出一个完全的晶½管级实现，此项目由ＤＡＢＰＡ
的模拟．信息通过美½海军研究计划拨款（Ｎ６６００１－０６－１
２０１１）．美½威斯康星大学麦迪逊分校的½
Ｈ½½½½，Ａ Ｍ
½８½½½½和Ｒ
Ｕ
概率相对较小，而½０渊Ｐ，ＳＰ算法则以相对较高概率
精确重建原始信号，随着稀疏度的增加，Ｃ½Ｓ½ＭＰ算法的
渐近效果却远差于其它算法，而从图４我们也发现稀疏
度一定，随着测量次数增多，信号重建的概率逐渐增
Ｂ½½帅，Ｊ
Ｎ½½½½等人在文献［２３—２７½中依
次提出分布式信源．通道匹配的通讯机制，被用来估计
万方数据
京公网安备 11010802033920号
Copyright © 2005-2024 EEWORLD.com.cn, Inc. All rights reserved
评论