煤矿物联网中压缩感知理论算法研究.pdf

南京邮电大学 硕士学位论文 煤矿物联网中压缩感知理论算法研究 姓名杜娟 申请学位级别硕士 专业信号与信息处理 指导教师邱晓晖 2011-03 南京邮电大学硕士研究生学位论文摘要 I 摘要 煤矿物联网作为一个新兴的热点研究领域，集成了传感器技术、微机电系统技术、无 线通信技术和分布式信息处理技术等。它将物联网技术应用在煤矿环境中，提高井下作业 的可见性与安全性，改变了传统的矿井作业方式。 压缩感知理论为信号采集技术带来了革命性的突破，以远低于奈奎斯特频率对信号进 行采样，通过数值最优化的方法准确重构出原始信号。尽管压缩感知理论还不完善，但它 的出现已在信号处理及其他领域掀起了一股研究热潮，为目前许多尚未解决的难题提供了 新思路和新方法。压缩感知理论有着强大的生命力，将会开创更加广阔的应用前景。 本文从压缩感知算法入手，介绍了压缩感知理论相对于其他的数据融合技术在煤矿物 联网中的应用优势， 并分析了压缩感知理论尚存在的问题。 针对煤矿物联网这个应用环境， 提出了改进方法，即基于小波变换的 LSC-CS 理论，该算法通过对具有逻辑相关性的数据 构成的矩阵分别进行小波行变换和小波列变换去除数据的时间相关性和空间相关性，对降 低数据在传输、存储等方面的能量消耗具有重要意义。 最后，基于 Matlab 仿真平台，模拟矿井下环境，用基于小波变换的 LSC-CS 算法对温 度、湿度等数据进行仿真，测试改进后的算法在能耗、可靠性和有效性等方面的性能，并 与传统算法进行比较分析，证明改进的算法对提高信号重构精度有明显效果，对能耗方面 也有明显的提高。 关键词关键词煤矿物联网、压缩感知、贝叶斯估计、逻辑空间相关性 南京邮电大学硕士研究生学位论文Abstract II Abstract As a new hot research field, Internet of ThingsIoT in mine integrates sensor technology, microelectronicssystems,wirelesscommunicationanddistributedinationprocessing technology.It used WSN technology into coal mine environment and increases the security and visibility of the mine,so it changed the traditional mining practices. Compressed sensing theoryCSbrings revolutionary breakthrough for signal acquisition. Through well below Nyquist sampling frequency of the signal and accurate reconstructed by numerical optimization problems.CS theory has set off a wave in signal processing and other areas though it isnt very perfect,It provided new idea and s for many unsolved problems.CS theory has strong vitality and will create a more broad application prospects. This paper introduced the advantages of CS theory that used in IoT of mine by compared with other data fusion technology,and analysised the remaining problems.For the mine environment, the paper introduced a improved scheme, namely WT-LSC CS theory.This algorithm removed the time and spatial correlation of LSC data matrix respectively through wavelet trans.Itcan reduce the energy consumption issues of data compression, communication and other aspects. Finally,the paper used temperature and humidity data to simulate the improved WT-LSC CS theory in this paper based on matlab plat to test the reliability and validity,then compared with traditional algorithm.The result showed that the improved algorithm can improve the accuracy of the signal reconstruction and reduce energy consumption obviously. KeywordsKeywordsKeywordsKeywordsIoT of mine;Compressed sensing;Bayesian estimation;LSC 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送 交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论 文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布（包括刊登）论文的全部或部分内容。 论文的公布（包括刊登）授权南京邮电大学研究生院（筹）办理。 研究生签名_____________ 日期____________ 研究生签名____________ 导师签名____________ 日期_____________ 南京邮电大学硕士研究生学位论文第一章 绪论 1 第一章第一章 绪绪 论论 1.11.1 本课题的研究意义本课题的研究意义 煤矿物联网是指将物联网理论应用煤矿行业中。物联网Internet of Things又称传感器 网络， 是指将各种信息传感设备或装置与互联网、 无线专网结合起来形成的一个巨大网络。 物联网是在互联网基础上延伸和扩展起来的网络，将物联网用户端延伸和扩展到矿井下进 行信息交换和通信，就形成了煤矿物联网。 据世界主要产煤国家煤矿安全状况及事故案例[1]和历年全国煤矿事故分析报告 [2][3]等统计显示，煤炭井工开采我国占95，印度占12，美国占30.5，俄罗斯占32，南 非占51。煤炭井下开采会受到瓦斯、煤尘、顶板、水、火等多种灾害影响，安全程度远 远低于露天开采。露天矿的百万吨死亡率很低，几近于零。近年来，我国煤矿安全生产形 势虽逐年好转，但是与世界其他主要产煤国相比，仍有一定差距。2008年我国井工煤矿百 万吨死亡率是美国的13.5倍，南非的7.9倍，俄罗斯的2.1倍，印度的0.97倍。从这些统计 数据可以看出，之所以会造成这样的死亡率，除井工开采量高达95、生存条件差、灾害 严重、小煤矿多等原因外，机械化、信息化程度低也是主要原因。由于煤矿井下工作环境 特殊,有大量的传感器检测各类信号,如瓦斯浓度、风压、温度等，每个节点处理的数据量 也很庞大，但是节点能量有限，且补充能量实现起来非常困难，因此从延长节点生命周期 的角度考虑，如何节省信息传输量和节点的计算量，是目前解决这一问题的主要途径。 压缩感知（Compressive Sensing，或Compressed Sampling，简称CS） ，是近几年流行起 来的一个介于数学和信息科学的新的研究方向。2004年由Candes、Terres Tao等人提出，它 所代表的基本思想是从尽量少的数据中提取尽量多的信息，是一种有着极大理论和应用前 景的想法[4]。它从诞生之日起到现在发展迅速，其影响已经席卷了大半个应用科学。它是 在传统信息论基础上的一个延伸，成为了一门崭新的子分支。压缩感知理论为信号采集技 术带来了革命性的突破，它采用非自适应线性投影来保持信号的原始结构，以远低于奈奎 斯特频率对信号进行采样，通过数值最优化问题准确重构出原始信号。 煤矿物联网对井下人员定位及煤矿井下的环境监测起着非常重要的作用。节点的能量 不仅关系到节点自身的工作时间、网络的可靠性，也决定了整个网络的生命周期。压缩感 知理论对少量数据进行采集，降低了能耗，提高网络的可靠性、延长网络的生命周期。虽 然CS理论的研究尚属于起步阶段，但已表现出了强大的生命力，并已发展了分布CS理论、 南京邮电大学硕士研究生学位论文第一章 绪论 2 1-BIT CS理论、Bayesian CS理论、无限维CS理论、变形CS理论等。 研究煤矿物联网数据 压缩感知理论对提高应用系统的性能、缩短数据获取的时间、降低数据获取的耗能、减少 数据的存储空间、提高数据的传输速度等等有重要作用，当然也对促进煤矿安全生产具有 十分重大的实际意义。 1.21.2 国内外的研究现状国内外的研究现状 煤矿物联网的研究和开发都还尚处于起步阶段，不同领域的专家学者对煤矿物联网研 究的起点各不相同，有关煤矿物联网的系统模型、体系架构和关键技术都还缺乏清晰化的 界定。我国的煤矿物联网发展也尚未走出“概念”阶段，缺乏顶层蓝图规划。而压缩感知 理论的应用领域已经涉及到数据压缩、模拟信息的转换、压缩成像、信道编码、信道估计、 生物传感、语音识别、雷达成像、雷达遥感、学习理论及模式识别等诸多领域[5]。其中， 在压缩成像方面，RICE 大学已经成功研制了“单像素”压缩数码照相机，该相机不像传 统相机那样获取原始信号的 N 个像素值，而是直接获取 M 个随机线性观测值，在实践中为 取代传统相机迈出了实质性的一步； 在通信领域， 由于无线多径信道一般情况下是稀疏的， 因此常常利用少量的导频就能获取未知信道的频域响应估计。此外，压缩感知理论还可用 于通信信道的错误检测[6]、传感网络的分布式信源编码[7]、认知无线电中频频感知等。目 前，国内外对压缩感知理论的研究已经有了一些成果，但是将压缩感知理论应用在煤矿物 联网中的文献还是少之又少。 在煤矿物联网中，数量众多的传感器节点产生了海量的数据，而网络中只有有限的能 量和传输带宽，难以适应大量数据的收集。数据压缩是一项能有效减少数据量的网内数据 处理技术。数据压缩感知算法概括起来分为三步信号的稀疏表示；观测矩阵的设计；信 号的重构算法。虽然压缩感知理论的应用前景很被看好，但是仍有许多有待改进的地方， 主要有以下方面如何设计快速有效的稀疏分解算法；便于硬件实现和优化算法实现的测 量矩阵的设计；非 1 l范数驱动的可压缩信号的重建理论；含有噪声时信号的快速准确重构 算法的设计；针对矿井下的应用环境，基于 CS 理论的软硬件设计等等，并且仅仅压缩是 不够的，在煤矿物联网应用中还需要较高精度的数据以便了解矿井下事件的细节信息，比 如矿井下传感器的监测任务有范围外的数据，也就是安全数据；范围内的数据，需要时 刻监测；报警数据，需要采取相关措施。尽管可以调整传感器节点的采样频率以适应不同 应用对不同数据精度的要求，但这会导致传感器网络和应用过于相互依赖，影响网络的扩 展性。因此，如何有效地减少网络内部的数据量，从而延长网络中节点的生命周期是无线 南京邮电大学硕士研究生学位论文第一章 绪论 3 传感器网络数据收集研究面临的一个重要研究方向。将无线传感器网络监测到的原始数据 变换到小波域来进行处理是解决这一难题的一种有效方法。 目前，WSN中基于小波变换的数据压缩研究已有一些基础性的工作。WISDEN[8]和 RACE[9]在单个节点内运行， 通过挖掘时间相关性减少冗余数据的传输， 但没有考虑邻近节 点间数据的空间相关性；HU HAIFENG[10]考虑到邻近节点间数据具有空间相关性，但没有 挖掘时间相关性；DIMENSIONS层次系统[11][12]先在底层节点挖掘数据间的时间相关性， 然 后在上一层簇首节点挖掘底层各节点数据间的空间相关性，但在底层节点与簇首间仍存在 冗余数据的传输。值得注意的是，也有研究分别提出了基于5/3小波提升方案和Harr小波的 分布式压缩算法[13][14][15]，这些算法通过在邻近的节点间交换信息，在数据传送到sink节点 前分布式挖掘网络中数据的空间相关性，大大减少了冗余数据的传输。由于在不同的应用 系统下监测到的数据往往具有不同的统计特性，因此需要选择不同性质的小波函数进行处 理。另一方面，虽然分布式压缩算法可以有效地减少了网络中冗余数据的传输，但是节点 间需要交换信息，由此产生的能量消耗等网络性能尚需要在理论上进行深入的定量分析。 同时，如何设计一种有效的算法以同时挖掘网络内部数据的时间相关性与空间相关性还鲜 有文献涉及。 1.31.3 本文的主要研究工作本文的主要研究工作 根据上述对压缩感知理论的研究现状分析，本文在原有压缩感知算法的基础上，主要 做了以下工作 （1）详细研究了压缩感知理论的基本原理， 较详细地分析了压缩感知理论的三个部分 及存在的不足之处，并介绍了几种经典的压缩感知算法，为后文的改进算法做准备。 （2）针对煤矿环境下采集到的温度、湿度等数据在相关性方面的特点进行分析，描述 本算法的应用环境，为后面的压缩算法做准备。 （3）结合矿井下的工作条件，针对以往研究中对空间相关性概念存在的不足，提出了 逻辑空间相关性的概念。 （4）基于小波变换的数据压缩感知算法进行改进方案基于小波变换的LSC-CS算 法，使之更加适用于煤矿物联网中。 （5）基于Matlab7.0，建立模拟环境，设计仿真实验，分别对32组符合矿井情况下采集 到的温度、湿度的数据用上述理论从算法的能耗与重构误差效果两方面进行仿真，通过分 析实验结果，评价该改进算法的优劣性。 南京邮电大学硕士研究生学位论文第一章 绪论 4 1.41.4 论文的章节安排论文的章节安排 第一章绪论 主要介绍煤矿物联网的发展状况及压缩感知理论的国内外研究现 状、技术上存在的问题及有待改进的方向，并对本文所做的主要研究工作进行概括。 第二章煤矿物联网中的压缩感知理论 分析了压缩感知理论在无线传感器网络 中的应用优势及压缩感知理论的理论框架、Bayes 压缩感知理论和分布式压缩感知理论的 基本原理。 第三章基于小波变换的数据压缩感知算法研究介绍 Mallat 多分辨率分析、 连续小波变换及 Harr 小波变换的相关理论，通过分析小波基函数的性质选取 Harr 小波为 小波基函数，并在此基础上分析基于小波变换的数据压缩与重构的过程。 第四章基于小波变换的压缩感知理论的改进算法研究 分析煤矿物联网中原始 数据的特点，给出了逻辑空间相关性的概念，分析了通过对小波行变换及列变换去除数据 的时间相关性和空间相关性，并给出了详细的算法流程图。 第五章仿真模型及仿真结果分析 针对一阶无线仿真模型，对两组 32 个具有相 关性的数据进行仿真，验证改进的算法在能量消耗方面和重构误差方面的性能，并对测试 结果进行分析。 第六章总结与展望 总结全文，指出有待进一步研究的工作。 南京邮电大学硕士研究生学位论文第二章 压缩感知理论算法研究 5 第二章第二章 压缩感知理论算法研究压缩感知理论算法研究 本章内容将分析CS理论在煤矿物联网中的应用优势，并对CS理论的三个重要部分分别 作详细的描述，接着就其中几种常用算法进行详细的说明。 2.12.1 压缩感知理论在煤矿物联网中的优势压缩感知理论在煤矿物联网中的优势 对压缩感知理论在煤矿物联网中的应用优势要从两方面来分析一方面是从算法本身 的优势；另一方面从煤矿物联网的特殊应用条件。 2.1.1 算法方面的分析 传统的信号获取和处理过程主要包括采样、压缩、传输和解压缩四个部分。如图2.1 所示 采 样变 换、压 缩 编 码 信 号X 编 码 端 Y 解 码 端 接 收 数 据Y 解 压 缩、反 变 换 恢 复 信 号X 图2.1 传统编解码理论的框图 其采样过程必须满足香农采样定理,即采样频率不能低于模拟信号频谱中最高频率的2 倍。奈奎斯特采样定理指出，采样速率必须达到信号带宽的两倍以上才能精确重构信号。 然而随着人们对信息需求量的增加，携带信息的信号带宽越来越大，以此为基础的信号处 理框架要求的采样速率和处理速度也越来越高，对宽带信号处理的困难也在日益加剧。另 一方面，在实际应用中，为了降低存储、处理和传输的成本，人们常采用压缩的方式以较 少的比特数来表示信号，大量的非重要的数据则被抛弃，但是这种高速采样再压缩的过程 浪费了大量的采样资源。 然而压缩传感的优点就恰恰在于信号的投影测量数据量远远小于传统采样方法所获的 数据量,突破了香农采样定理的瓶颈,使得高分辨率信号的采集成为可能。压缩传感理论框 架如图2.2所示。 南京邮电大学硕士研究生学位论文第二章 压缩感知理论算法研究 6 图2.2 压缩感知理论 在信号压缩中,先对信号进行某种变换,如离散余弦变换或小波变换,然后对少数绝对 值较大的系数进行压缩编码,舍弃零或接近于零的系数。测量值并非信号本身，而是从高 维到低维的投影值，从数学角度出发，每个测量值都是传统意义下的每个样本信号的组合 函数[18]，即一个测量值包含了所有样本信号的少量信息。通过对数据进行压缩,舍弃了采 样获得的大部分数据,却不影响感知效果。例如,在运用数百万像素的数码相机对场景进行 成像时,就会得到海量的像素信息,但通过压缩编码后,只对其中少量信息进行存储和传输, 最后通过相应的解压缩算法对原始图像进行重构。如果信号本身是可压缩的,那么能否直 接获取其压缩表示即压缩数据,从而略去对大量冗余信息的采样呢Cands在2006年已 经证明出可以从部分傅立叶变换系数中精确重构出原始信号,为压缩传感奠定了理论基础 [17]，接着 Cands 和 Donoho 在相关研究基础上于 2006 年正式提出了压缩传感的概念[18]。 其核心思想是采样、压缩编码发生在同一个步骤,首先采集信号的非自适应线性投影测量 值,然后根据相应的重构算法由测量值重构原始信号。 通过研究，已经得知只要信号是可压缩的或在某个变换域是稀疏的，那么就可以用一 个与变换基不相关的观测矩阵将变换得到的高维信号投影到一个低维空间上，然后通过求 解一个最优化问题从这些少量的投影中以高精确度重构出原信号，可以证明这样的投影值 包含了重构信号的足够信息。在该理论框架下，采样速率主要决定于信息在信号中的稀疏 性和非相关性，而不决定于信号的带宽。 2.1.2 应用环境方面的分析 矿井下无线传感器网络由于其特殊的应用环境条件，具有如下的一些特点 （1）网络内节点分布稠密。为了获取精确的信息，在监测区域通常密集部署大量功能 不同的传感器节点，有监测温度、湿度、瓦斯浓度、风速等，以降低对单个节点传感精度 的要求。大量冗余节点的存在，也使得网络具有较强的容错性能，并且能增大网络覆盖的 南京邮电大学硕士研究生学位论文第二章 压缩感知理论算法研究 7 监测区域，减少盲区。 2传感器节点的能量、存储空间和计算能力非常有限。传感器节点依靠电池供电， 在 矿井下，节点散布之后其能源通常无法补充。作为一种微型嵌入式设备，传感器节点价格 低、功耗小，这些限制导致其携带的处理器比较弱，存储器容量比较小。技术的进步会降 低器件的成本，但就目前而言传感器节点资源紧张的状况很难得到迅速的缓解。 3能耗是被首要考虑的因素。 由于WSN的工作环境所限， 当能量耗尽的节点达到一定 数量，传感器网络也就死亡了。因此，降低和平衡节点能耗，延长网络的生存时间就成为 无线传感器网络研究中的一个关键点。 鉴于以上的分析，我们可以分析得到节点所能运行的压缩算法必定受到节点处理能力 和存储空间等限制。虽然现有的数据压缩技术已经有许多成熟实用的无损压缩和有损压缩 算法，但大多都不是针对 WSN 这类资源受限系统的应用而设计的。节点硬件资源不同使 其对数据压缩的性能要求不同。节省每一个要传送的字节都有益于节能，但数据压缩是以 增加数据处理的能耗来降低总能耗，算法所能获得的压缩率、数据精度等性能还受到能量 和存储空间的制约。这里的面向 WSN 的数据压缩与普通数据压缩有所不同，前者需要在 简单有效的压缩方法的基础上，研究能在资源受限的硬件平台上实现数据压缩的算法。 相对于其他的数据融合技术，CS特别适合应用于WSN中，主要因为 1编码的低计算复杂度。信号只需要在随机观测矩阵上进行线性投影，便可计算出压 缩后的观测向量。 2优异的压缩性能。对于−k稀疏的N维信号只需要4 ≥cckm维的观测向量 NM） ，便可重构信号。 3编解码相互独立性，对于相同的编码方案，可以采样不同的解码技术。 上述优点使得CS特别适用在资源受限的煤矿物联网中，只要节点感知到的数据是可压 缩的，即在某些正交基上可以稀疏表示，便可在节点侧运行低计算开销的编码算法，Sink 节点通过收集节点感知数据的观测向量，运行较为复杂的CS解码算法，进行数据压缩和重 构，实现了以非协作方式，即节点间不需要进行数据交换，显著减少了网络开销。 2.22.2 CSCS 理论算法的问题描述理论算法的问题描述 考虑一个实值有限长的一维离散时间信号X，可以看做是一个 N R空间1N维的列向 量，记为[ ]NnnX,, 3 ,2, 1,⋯。 N R 空间的任一信号都可以用1N维的基向量{}N i1i ψ作 南京邮电大学硕士研究生学位论文第二章 压缩感知理论算法研究 8 为列向量形成NN的基矩阵[] N21 ,,ψψψψ，于是任意信号X都可以表示为 ΨΘΨ∑ Xor N i i 1 i Xθ2.1 其中{ }{} ii XΨΘ,θ是投影系数，1N维的列向量。显然，X和Θ是同一个信号 的等价表示，不同之处在于X是信号在时域的表示，Θ则是信号在Ψ 域的表示。如果Θ的 非零个数远小于N，则表明该信号是可压缩的（系数中 0 的个数越多，表示该信号稀疏性 越大，该信号可压缩） 。一般而言，可压缩信号是指可以用 K 个大系数很好地逼近的信号， 即它在某个正交基下展开的系数按照一定量级呈现指数衰减，具有非常少的大系数和大量 的小系数，这种通过变换实现压缩的方法称为变换编码，其基本思路是在数据采样系统 中，信号是可压缩的，由高采样速率得到N点采样信号X；通过X T ΨΘ变换后计算出 完整的变换系数集合{ } i θ； 确定 K 个大系数的位置和量值， 然后扔掉KN−个小系数； 对K 个大系数的值和位置进行编码，从而进行信号重构。 压缩感知理论指出，设长度为 N 的信号 X 在某组正交基或紧框架Ψ 上的变换系数是 稀疏的，如果我们用一个与变换基Ψ不相关的观测基NNMMΦ对系数向量进行 线性变换，并得到观测集合1MY，那么就可以利用最优化求解方法从观测集合中精确 或高概率地重构出信号 ∧ X。 通过以上的分析，我们了解到压缩感知理论主要涉及以下三个方面问题的讨论 （1）信号的稀疏表示问题对于信号 N RX∈，如何找到某个正交基或者紧框架 Ψ ， 使其在Ψ 上的表示是稀疏的； （2）信号低速采样问题如何设计一个平稳的、与变换基Ψ 不相关的NM维的观测 矩阵Φ，保证稀疏向量Θ从 N 维降维到 M 维时重要信息不遭破坏； （3）信号重构问题 如何设计快速的重构算法， 从线性观测XAY CS 中恢复信号 （其 中 TCS AΦΨ） 。 本章将对这三方面问题分别进行详细分析。 2.2.1 信号的稀疏表示 从傅里叶变换到小波变换再到后来兴起的多尺度几何分析， 科学家们研究的出发点均 南京邮电大学硕士研究生学位论文第二章 压缩感知理论算法研究 9 是为了如何在不同的函数空间为信号提供一种更为简洁、直接的分析方式。所有的这些变 换都旨在发掘信号的特征并如何稀疏表示它，或者说旨在提高信号的非线性函数逼近能 力，进一步研究用基空间的一组基来表示信号的稀疏程度[19]。 稀疏性在现代信号处理领域一直起着至关重要的作用，例如基于稀疏性的估计、逼近、 压缩、降维等。与信号带宽相比，稀疏性能更直观且本质地表达信号的信息。 稀疏的数学定义如前所述，离散时间信号X可以看作为一个 N R空间的1N维列向 量[] T Nxxx,2,1 ⋯。 N R空间的任一信号都可以用1N维的基向量{}Ni i ⋯,2, 1|ϕ的 线性组合来表示[20]。为简化问题，假定这些基向量是规范正交基。 在文献[18]中这样定义稀疏性在正交基Ψ 下的变换系数向量为X T ΨΘ，假如对于 20R，这些系数满足 R P i P i p ≤⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ≡Θ ∑ 1 θ （2.2） 则说明系数向量Θ在某种意义下是稀疏的。而在文献[20]中给出另一种定义在前面 公式（2.1）中的定义，当信号X在某个正交基Ψ 上仅有NK个非零系数（或远大于零 的系数） i θ时，称Ψ 为信号X的稀疏基，当信号X在正交基Ψ 上是K-稀疏的，此时（2.1） 式就是X的稀疏表示。 找到信号最佳的稀疏域是压缩感知理论的基础和前提。只有选择合适的基表示信号才 能够保证信号的稀疏度，进而保证信号的恢复精度。在研究信号的稀疏表示时，可以通过 变换系数衰减的速度来衡量变换基的稀疏表示能力，Cands、Terres Tao研究表明满足具有 幂次速度衰减的信号[21]，可利用压缩感知理论得到恢复，并且重构误差满足 r r NKCXXE − ∧ ≤− 6 2 log2.3 其中，1 0 , 211−ppr。 光滑信号的Fourier系数、小波系数、有界变差函数的全变差范数、振荡信号的Gabor 系数及具有不连续边缘的图像信号的Curvelet系数等等都具有足够的稀疏性， 都可以通过压 缩感知理论恢复信号。如何找到或构造适合某一类信号的正交基，以求得信号的最稀疏表 示，仍是一个有待进一步研究的问题。 最近几年来，对稀疏表示研究的另一个热点是信号在冗余字典下的稀疏分解。这是一 种全新的信号表示理论[22]用超完备的冗余函数库取代基函数，称之为冗余字典，字典里 南京邮电大学硕士研究生学位论文第二章 压缩感知理论算法研究 10 的元素被称为原子。在选择字典时，准则是尽可能好的符合被逼近信号的结构，对其构成 没有任何限制。从冗余字典中找到具有最佳线性组合的K项原子来表示一个信号，称作信 号的稀疏逼近。目前，信号在冗余字典下的稀疏表示的研究主要集中在两个方面一方面 是如何构造出一个适合某一类信号的冗余字典；另一方面是如何设计快速有效的稀疏分解 算法。这两个问题也一直是该领域研究的热点。从非线性逼近角度来讲，信号的稀疏逼近 包括两个关键步骤 （1）根据目标函数从一个给定的基库中挑选好的或最好的基； （2）从 这个好的基中挑选出最佳的K项原子组合。 2.2.2 观测矩阵的设计 压缩感知理论中，通过变换得到信号的稀疏系数向量X T ΨΘ后，需要设计压缩采样 系统的观测矩阵Φ， 观测矩阵的作用是如何采样得到M个观测值， 并保证从中能重构出长 度为N的信号X或者基Ψ 下等价的稀疏系数向量Θ [23][24]。通常观测矩阵Φ与正交基Ψ 是 不相关的。观测过程实际上就是利用NM维的观测矩阵中的M个行向量{ } M j j 1 ϕ对稀疏系 数向量进行投影，即计算Θ和各个观测向量{ } M j j 1 ϕ之间的内积，得到M个观测值 , 2 , 1,Mjy jj ⋯Θϕ。记观测集合 M yyyY⋯,, 21 ，则有 XAXY csT ΦΨΦΘ（2.4） 这里采样过程是非自适应的， Φ无须根据信号的变化而变化。由于NM，即方程 的个数远少于未知数的个数，一般来讲是无确定解的，但是如果Θ具有K-项稀疏性 MK） ，则该问题有望求出解，只要设法确定出Θ中的K个非零系数 i θ的合适位置。 由于观测向量Y是这些非零系数 i θ对应Φ中的K个列向量的线性组合，从而可以形成一个 KM的线性方程组来求解这些非零项的具体值。 对此， 有限等距性质 （Restricted Isometry Property,简称RIP）给出了存在确定性解的充要条件[25] 信号完全重构的充要条件是观测矩阵不会把两个不同的−K项稀疏信号映射到同一个 采样集合中，这就要求从观测矩阵中抽取的每M个列向量构成的矩阵都是非奇异的。 这和稀疏信号在观测矩阵作用下需要保持的几何特性相一致。从中可以看出，问题的 关键是如何确定非零系数的位置和值来构造出一个可解的KM线性方程组。但是，判断 给定的 T ΦΨ是否具有RIP性质是一个组合复杂度的问题[26]，因此研究指出如果可以确保观 南京邮电大学硕士研究生学位论文第二章 压缩感知理论算法研究 11 测矩阵Φ和稀疏基Ψ 不相关，则 T ΦΨ 在很大概率上是满足RIP性质的，因此上述的组合复 杂度问题在一定程度上得到缓解。 其中的不相关概念是指向量{ } j ϕ不能用{ } i ψ稀疏表示[27]， 不相关性越强，互相表示时需要的系数越多。 随机高斯矩阵Φ具有一个非常有用的性质[26]对于一个NM的随机高斯矩阵Φ，可 以证明当KNcKMlog≥时， TCS AΦΨ在很大概率下具有RIP性质（其中c是一个很小 的常数） 。 因此选择高斯随机矩阵Φ作为观测矩阵，就可以保证观测矩阵Φ和稀疏基Ψ 的不相关 性和RIP性质， 从M个观测值 M yyyY,,, 21 ⋯中以很高的概率去恢复长度为N的−k稀疏 信号。总之，随机高斯矩阵与大多数固定正交基构成的矩阵不相关，这一特性决定了选它 作为观测矩阵Φ，其它正交基作为稀疏变换基时， CS A满足RIP性质。在有些研究中，为了 进一步简化观测矩阵Φ， 在某些条件下， 以随机 1 为元素构成的Rademacher矩阵也可以证 明具有RIP性质和普适性[28]。 目前，对于观测矩阵的研究是压缩感知理论的一个重要方面。在研究中，对观测矩阵 的约束是比较宽松的[4]， 大部分一致分布的随机矩阵都可以作为观测矩阵， 例如部分Fourier 集、部分Hadamard集、一致分布的随机投影集等，这与对RIP性质进行研究得出的结论是 一致的。但是上述的观测矩阵仅能保证以很高的概率去恢复信号，而不能保证完全无误差 的重构信号，如果对信号复原精度要求很高的精度的话，对于是否存在一个真实的确定性 的观测矩阵仍是需要考究。 2.2.3 信号重构 目前，关于重构算法的研究主要有三类[29] （1）贪婪追踪算法 这类方法是通过每次迭代时选择一个局部最优解来逐步逼近原始 信号。代表算法有MP算法，OMP算法等； （2）凸松弛法这类方法通过将非凸问题转化为凸问题求解找到信号的逼近，如BP 算法，内点法，梯度投影法和迭代阈值法。 （3）组合算法 这类方法要求信号的采样支持通过分组测试快速重建， 如傅里叶采样， 链式追踪和HHS（Heavg Hitters on Steroids）追踪等。 每种算法都存在缺点，重构算法和所需的观测次数密切相关。信号重构问题的研究主 要集中在如何构造稳定的、计算复杂度较低的、对观测数量要求较少的重构算法来精确地 南京邮电大学硕士研究生学位论文第二章 压缩感知理论算法研究 12 恢复原始信号。 在压缩感知理论中，由于观测数量M远小于信号长度N，表面上看求解欠定方程组 XAXY CST ΦΨ是无望的， 但是由于信号X具有稀疏性或者是可压缩的， 在这个前提下， 欠定问题就有解了，也为从M个观测值中精确恢复信号提供了理论保证。接着本文描述基 于压缩感知理论的信号重构问题。 首先定义信号{} n xxxX⋯,, 21 的−p范数为 P n i p i p xX 1 1 ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ∑ （2.5） 当0p时得到0-范数，它实际上表示X中非零项的个数。于是，问题转化为最小0- 范数问题 YxtsX TT ΦΨΨ. .min 0 （2.6） 它需要列出X中所有非零项位置的 k N C种可能的线性组合，才能得到最优解。因此， 求 解式（2.6）的数值计算极不稳定，而且是NP-hard问题。Chen,Donoho和Saunders指出，求 解一个更加简单的 1 l优化问题会产生同等的解（前提满足Φ和Ψ 不相关） YxtsX TT ΦΨΨ. .min 1 （2.7） 这样问题就转变成了一个凸优化问题，可以方便的简化为线性规划问题，典型的算法 有BP算法。但是这种算法在实际应用中被发现存在两个问题[30]，一是算法的复杂度高， 重 构计算的复杂度量级在 3 NO；二是由于1-范数无法区分稀疏系数尺度的位置，所以尽管 整体上重构信号在欧氏距离上逼近原信号，但存在低尺度能量搬移到了高尺度的现象，从 而容易出现一些人工效应， 如一维信号会在高频出现振荡[31]。 基于上述问题， Tropp和Gilbert 提出利用匹配追踪（MP）[32]和正交匹配追踪（OMP）算法[33]来求解优化问题重构信号， 进一步提高了信号重构的精度和求解的速度，且这两种算法易于实现，所以在很多实际应 用研究中被广泛采用，成为压缩感知理论中信号重构部分的代表性算法。 （1）匹配追踪算法（Matching Pursuit，简称MP算法） 假定 H 表示 Hilbert 空间， 定义 H 中的原子库， 且1 r g。 令信号HX∈， 为了逼近X， MP 首先从过完备原字库中选择最为匹配的一个原子，即满足 r r r gXgX,sup, 0 Γ∈ 。这样 信号X可以分解为如下形式 南京邮电大学硕士研究生学位论文第二章 压缩感知理论算法研究 13 XRggXX rr 1 00 ,2.8 其中，XR1表示原子， 0 r g表示信号X所产生的误差，显然 0 r g与XR1是正交的，所以 可以得到 2 1 2 2 , 0 XRXgX r 2.9 为了使得逼近误差的能量最小，必须选择Hgr∈ 0 使得 0 , r gX最大。在无穷维或高维 的情况下，由于计算复杂度的限制，通常无法找到 0 , r gX的极值，只能选择在某种意义 上的近似最佳原子 0 r g，使得 r r r gXgX,sup, 0 Γ∈ ≥α2.10 其中α为优化因子，满足10≤，若满足，则迭代停止；若不满足，则执行第一步。 OMP 算法保证了每次迭代的最优性，减少了迭代次数。但是它在每次迭代中仅选择一 个原子来更新原子集合，这样必然会延长重构所需的时间，迭代次数与稀疏度 K 或采样个 数 M 之间密切相关，随着 K 或 M 的增大，耗时也将大幅增加。因此之后相继出现了改进 的匹配追踪算法，如 ROMP、STOMP、CoSaMP 等。但 OMP 作为经典的算法，它的思想 影响了之后的种种算