（信号与信息处理专业论文）压缩传感理论研究及其在图像纹理分割中的应用.pdf

摘 要 i 摘摘 要要 奈奎斯特-香农（nyquist - shannon）采样定理要求信号的采样率必须高于信 号最高频率的两倍，原信号才能从采样值里得到不失真的重构。但是对于稀疏信 号而言，原信号压缩后的数据量仅为原信号数据量的一部分。因此这种先采样后 压缩的信号处理模式会造成资源的浪费。压缩传感理论作为一种新兴理论，将集 采样和压缩同时进行。它指出对于可压缩或稀疏信号，可在远少于传统采样值的 情况下精确的重构原信号。压缩传感理论以信号的稀疏性为前提，为传统的信号 处理带来了革命性的突破。本文的主要工作和贡献如下： 1. 在稀疏基为冗余基的情况下，设计测量矩阵，使得稀疏基和测量矩阵组 成的压缩传感矩阵具有最优的性能。 首先对近年来该研究方向的研究成果和最新 进展进行搜集、整理和总结。然后针对 m. elad 提出的最优投影（optimized projection，op）算法进行了改进，使得压缩传感矩阵有更好的性能，即相同稀 疏度的前提下，能用最少的测量值进行重构；或者在相同测量值的情况下，重构 出来的信号与原信号之间的误差最小。 2. 由 s. rosset 和 j. zhu 在 2007 年提出来的分段线性路径解算法 （piecewise linear regularized solution paths）由于涉及了矩阵的求逆问题，因此该算法只能 在矩阵满秩的情况下运行。在矩阵欠秩的情况下该算法是失效的。我们受到 ch. ong, s. shao， j. yang 对 t. hastie，s. rosset，j. zhu 提出的支持向量机规则化 路径算法修正方法的启发。对分段线性路径解算法中的矩阵求逆问题进行了修 正。并通过实验验证了改进的分段线性解算法的优越性。 3. 将压缩传感理论引入纹理分割问题。首先，将纹理图像看作是某些纹理 基元有轻微差别的循环， 因此纹理识别问题可以看作是多线性回归模型中的一个 分类问题。其次，用压缩传感理论中 1 ? -最小化方法将纹理块分解成过完备集的 一个线性组合，并将纹理块在该完备集上的稀疏系数作为纹理的特征量。然后， 对该特征量采用一定的准则对其识别。当纹理类被识别后，我们再利用纹理的连 续性把属于该纹理类的所有非边缘部分分割出来。 最后通过细分割把边缘部分分 割出来。 关键字关键字：压缩传感 冗余基 纹理分割 恢复算法 abstract iii abstract as we known, the nyquist - shannon sampling theorem points out the conditions needed for the signal exact reconstruction without distortion is that the sampling rate of the signal must be at least twice as the highest frequency. as for sparse signals, the compressed data of the original signal is only part of the original signal data. the mode of first sampling then compressing will cause waste of resources. the theory of compressed sensing as an emerging theory, offers a joint compression and sensing process for the sparse or compressible signal. the signal can be exactly reconstructed though the measurements which are much less than conventional sampling data. as for the compressed sensing theory, the sparsity of the signal is required. a revolutionary breakthrough has been brought to the traditional signal processing from the compressed sensing theory. the main work we have down is as follows: 1. if the redundant dictionary is fixed, how to design a suitable measurement matrix so that the compressed sensing matrix composed by the measurement matrix and redundant dictionary has the optimal performance. we firstly investigate the newest academic achievements and progress at home and abroad in this direction. we improved the optimal projection proposed by m. elad, making the compressed sensing matrix has optimal performance. the optimal performance is that, for the signals with the same sparsity, it can reconstruct the signal using the least measurements. in the other words, with the same measurements, the compressed sensing matrix can reconstruct the signal with the smallest error. 2. the piecewise linear regularized solution paths algorithm proposed by s. rosset and j. zhu in 2007 is valid based on the premise that the matrix is full rank. inspired by the method that ch. ong, s. shao and j. yang have used for modifying the entire regularization path algorithm for the support vector machine proposed by t. hastie, s. rosset and j. zhu. we improved this algorithm by solving the problem of the inversion of singular matrix. the new algorithm is verified through experiment. 3. the compressed sensing theory is introduced into the texture segmentation problem. we firstly consider the texture image as a cycle-extension of small texture atom. we cast the texture recognition problem as one of classifying among multiple linear regression models. secondly, the texture image is decomposed as a linear combination of the overcomplete dictionary by 1 ? -minimization in the compressed abstract iv sensing theory and the coefficients of the image is considered as the feature vector. then, this texture class will be recognized by some criteria on the feature vector. afterwards, as the texture class has been recognized, we are able to use the texture images structure feature, consistency, to segment all the parts of the texture image belonging to this class. the edges will be segmented by the fine segmentation. key word: compressed sensing, redundant dictionary，texture segmentation, reconstruction algorithm 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文,是本人在导师指导下进行研究工作所取得的 成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 作者签名：_ 签字日期：_ 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入中 国学位论文全文数据库等有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内 容相一致。 保密的学位论文在解密后也遵守此规定。 公开 保密（_年） 作者签名：_ 导师签名：_ 签字日期：_ 签字日期：_ 第 1 章 绪论 1 第第 1 章章 绪论绪论 压缩传感理论又称压缩采样理论（compressed sensing or compressed sampling, cs） ，它是由著名的数学家 d. donoho 与 e. candes 在 2006 年提出的 1,2。该理论一提出就引起了巨大的轰动，这是因为压缩传感理论的应用前提已 不再是带限信号，取而代之的是稀疏信号。它指出对于满足条件的稀疏信号可在 远少于奈奎斯-香农采样定理要求的采样值的情况下精确的重构原信号。这种集 采样压缩为一体的信号处理新模式，为信号处理领域带来了革命性的突破，因此 得到了研究人员的广泛关注。本章首先论述压缩传感理论的研究背景及意义；然 后介绍压缩传感理论基本原理和国内外的研究现状； 最后简要阐述本文的主要工 作内容。 1.1 研究背景及意义 传统的信号处理的过程主要包括采样、压缩、传输和解压缩四个部分，如图 1.1 所示。奈奎斯特-香农采样定理是信号处理领域的基石，它揭示了模拟信号与 数字信号之间相互转换的规律，同时给出了信号时域与频域之间的关系。该定理 由美国电信工程师 h. 奈奎斯特在 1928 首先提出来的，因此用奈奎斯特来命名 该定理。 苏联工程师科捷利尼科夫在 1933 年首次用公式严格的表述了这一定理， 因此该定理又称为科捷利尼科夫采样定理。1948 年，信息论的创始人 c.e.香农 对这一定理加以明确说明并正式作为定理引用，因此该定理被称为奈奎斯特-香 农采样定理。 采样信号压缩传输恢复原信号原始信号 图图 1.1 传统信号处理过程 采样定理有许多表述形式， 其中最基本的表述方式有时域采样定理和频域采 样定理这两种。本文中采用的表述方式则是我们最常用的时域采样定理，即：原 始的模拟信号能够不失真重构的条件是该模拟信号的采样频率必须大于或等于 该模拟信号最高频率的两倍。因而对于一个最高频率为 m f 的模拟信号 x ? 来讲， 第 1 章 绪论 2 其最小采样频率 s f 必须大于或等于 m 2f，即 m 2 s ff。等号成立时的采样频率 称为奈奎斯特-香农采样率。该过程我们可以用图 1.2 来说明。 j c c 0 m m s s s t1 () mcsm )(h 0 )(tf )(tfs 连续信号 抽样信号 )(jh )( 0 tf 理想低通滤波器 恢复信号 )( )( t ts s t = )(jfs 图图 1.2 奈奎斯特-香农采样定理图示 图注图注:2 mm f=,2 ss f=,2 cc f=， m f是信号的最高频率， s f是抽样频率， c f是低 通滤波频率。 奈奎斯特-香农采样定理是数字遥测系统、时分遥测系统、数字信号处理领 域、数字通信领域的基础理论，决定着模拟信号和数字信号之间的相互转换。奈 奎斯特-香农采样定理描述了两个过程：一是采样，这一过程将模拟信号转换为 数字信号；二是信号的重建，这一过程将数字信号还原成模拟信号。我们知道过 去的信号几乎都是低频信号，因此信号的采样率不高，获得的采样值也不多，这 对存储设备的存储能力构不成威胁。但是随着频谱资源中低频段资源的耗尽，现 在可用频谱资源的频率越来越高，这就使得信号的采样率也越来越高，信号的采 样值也越来越多，这就使得信号的存储设备面临着巨大的压力。因此奈奎斯特- 香农采样定理对信息领域发展的制约也越来越明显。 下面我们从两个方面来说明 奈奎斯特-香农采用定理对信息领域发展的制约。 （1）数据的采样 我们首先从采样过程来说明奈奎斯特-香农采样定理对信息领域发展的制 约。奈奎斯特-香农采样定理作为模拟信号到数字信号转换的指导理论，是数字 信号处理领域的基石。对于基带信号而言，它的采样率要大于信号带宽的两倍， 此时信号的采样值相对于现在的存储技术来讲不足以构成巨大的威胁。 但是对于 中心频率未知的高频带通信号而言，由于信号的采样率要大于最高频率的两倍， 第 1 章 绪论 3 因此采样产生的采样值的数据量巨大，这就对数据的存储造成了巨大的压力。以 传感器网络为例，数据的采集需要成千上万的传感器在固定的地点连续采样。这 种不间断的采样产生的数字信号不仅数量巨大而且具有很大冗余度。 这就为采样 信号的存储带来了巨大的挑战，制约着信号处理领域的快速发展，成为了亟待解 决瓶颈。 （2）数据的压缩、存储和传输 信号的传输模式分为两类：模拟传输和数字传输。模拟传输是一种不考虑内 容的传输方式，而数字传输则与信号的内容紧密相关。但是无论哪种传输方式， 在传输一定距离之后信号都会衰减。为了克服这种衰减，模拟传输系统用放大器 来增加信号的能量，但是这样会使噪音得到同倍数的放大；而数字传输系统则通 过中继器，将信号再生后再传输，这样就避免了噪声功率的增加。因此我们采用 的传输模式一般都是数字传输模式。通过前面的分析我们看到，对于高频信号来 讲，信号的采样值数量巨大，如果直接传输不仅耗时，而且容易出现传输错误。 因此在传输之前我们需要对信号的采样数据进行压缩。经典的数据压缩技术，例 如视频压缩的 mpeg（moving picture experts group）标准，音频压缩的 mp3 （mpeg-1 layer iii）标准，图像压缩的 jpeg（joint photographic experts group） 标准等，都是从数据本身的特性出发，寻找并剔除数据中隐含的冗余度，从而达 到压缩的目的。而且对于稀疏信号而言，压缩后的数据量能比压缩前的数据量少 几个数量级。因此这种先采样后压缩的信号处理模式造成了很大的存储资源浪 费。在大多数情况下，数据采集和预处理的设备，往往是廉价、省电、计算能力 较低的便携设备， 例如傻瓜相机、 录音笔、 遥控监视器等等。 而负责处理信息 （即 解压缩过程）的通常是具有高效计算能力的大型计算机。也就是说，我们是在用 计算能力低效的设备来处理复杂的计算任务， 而用高效的设备来处理相对简单的 计算任务。这种压缩和解压缩的不对称性恰好同人们的需求相反，随着信号频率 的增长，这个矛盾将更加尖锐，成为制约信号领域发展的瓶颈。 因此我们可以看到以奈奎斯特-香农采样定理为支撑的传统信号处理模式有 一个令人诧异的数据处理过程。首先，信号在采样阶段要服从奈奎斯特-香农采 样定理，此时的高速采样产生了巨大的采样数据量。然后，信号在压缩阶段将会 产生数量相对较少的压缩数据。由于压缩过程发生在采样过程之后，因此这种先 采样后压缩的信号处理模式造成了很多的资源浪费。 我们自然而然的就想到了这样的一个问题： 既然数据量巨大的采样信号通过 压缩后会变成数据量较小的压缩数据， 那么我们能不能在可以完全重构原信号的 前提下， 集采样和压缩与一体， 在采样的同时也完成了对数据的压缩？如果可以， 那么就可以解除信号先采样后压缩模式带来的存储上的压力， 提高信号处理的能 第 1 章 绪论 4 力和效率，推动信息领域进一步往前发展的关键。 众所周知： （1）奈奎斯特-香农采样定理是信号精确复原的充分不必要条件。 （2）现实中的大多数信号除带宽外，都拥有大量的结构信息。我们可以通过贝 叶斯理论利用信号的结构信息来降低数据采集量。 （3）johnson-lindenstrauss 定 理表明：我们可以用1k +次测量值以接近 1 的概率来恢复n维空间的k-稀疏信 号3。这三个条件就为新的信号处理模式的出现提供了理论支持。 压缩传感理论就是在这样的一个背景和需求下应运而生的， 它相对于传统的 信号处理模式来讲是一个新颖的信号处理模式。它对稀疏或可压缩信号（此处的 信号是图像和信号的统称），可以从比传统采样值少很多的测量值中以接近 1 的概率来精确的重构原信号。我们可以看到这是一种更普遍的数据获取方法。它 的采样过程和压缩过程同时进行， 这个过程是通过采集信号的非自适应线性投影 值（即测量值）来实现的。因此压缩传感理论避免了信号采样后压缩前的采样值 的存储，避免了不必要的资源浪费。 1.2 压缩传感理论简介 压缩传感理论是信号处理领域近年来新兴的理论。在该理论的框架下，采样 过程和压缩过程合并进行，并通过信号的非自适应线性投影同时实现。因此与传 统的信号处理过程相比，减少了传统数据采样后压缩前数据存储的花销。压缩传 感理论的基本思想就是对于稀疏或可压缩信号， 通过一个观测矩阵将高维稀疏或 可压缩信号投影得到低维观测值， 然后通过解优化问题来以接近 1 的概率重构原 信号。因此我们可以看到信号的稀疏性是压缩传感理论的前提条件；非自适应线 性投影是压缩传感理论的核心，它实现了信号的压缩和采样；优化问题是压缩传 感理论的信号重构手段。压缩传感理论的框架可以用图 1.3 来说明。 原始信号压缩采样信号重构信号 非线性投影过程 优化问题 图图 1.3 信号在压缩传感理论下的框架 由图 1.3 可以看到：压缩传感理论由信号的稀疏表示，信号的非自适应线性 第 1 章 绪论 5 测量以及信号的重建这三个步骤组成。 目前压缩传感理论的研究也围绕着这三个 方面展开的。 （1） 对于给定的信号 n xr ， 寻找或设计某个正交基或者冗余基 n m dr作 为能稀疏表示该信号的稀疏基，使得信号有稀疏表示， n mm =xd 。 光滑信号的傅里叶系数、小波系数，有界差变信号的全变差分范数4，振 荡信号的 gabor 系数以及不连续边缘图像的曲波变换系数等都是稀疏或者可压 缩的5。我们可以看到信号的多样性以及自身的独特性，决定了能稀疏表示信 号的稀疏基不是固定的。因此出现了依据训练图像来自适应设计稀疏基的算法 6。 （2）在信号的稀疏基一定的情况下，如何设计一个测量矩阵p，使得稀疏 基和测量矩阵构成的压缩传感矩阵具有最好的性能7-10。 首先定义压缩传感矩阵 cs ，它是由测量矩阵p和稀疏基d组成 csn nn m =pd。原信号能够精确重构的一个充分不必要条件是：压缩传感矩阵 cs 必须满足限制等容性（restricted isometry property, rip） 。判断矩阵 cs 的限 制等容性是一个遍历的组合问题，计算复杂度很高。目前已知满足该条件的压缩 传感矩阵有伯努利矩阵、部分傅里叶矩阵以及部分阿达玛矩阵（hadamard matrix）等。此外如果测量矩阵p和稀疏基矩阵d是不相关的话，此时的压缩传 感矩阵 cs 以很大概率满足限制等容性。 （3）如何设计快速重构算法。 重构算法在压缩传感理论中是至关重要的一步， 压缩传感理论的成败就是由 信号的重构算法决定的。因为压缩传感的前提条件是信号具有稀疏性，而信号的 稀疏度与信号中非零值的个数密切相关， 所以我们首先想到的目标函数为最小化 信号的 0 ? -范数： 0 0 arg min=，. .s t=ypdxd，。虽然该目标函数理解 起来很容易，但是这是一个组合问题，不可能在有限时间内遍历出该组合问题的 解 。 但 是 我 们 却 知 道 目 标 函 数 （ 最 小 化 信 号 的 1 ?- 范 数 ） 1 1 arg min. . cs s t=ydxpd，是一个凸优化问题，用凸优化工具 就能精确的求解出原信号。因此如果能够探索出两种目标函数之间的联系，那么 我们就可以用最小化信号 1 ? -范数的目标函数来替代最小化信号 0 ? -范数的目标 函数。所幸的是，科研者已经证明了当压缩传感矩阵满足一定的条件时上面的两 第 1 章 绪论 6 个目标函数的解不仅是唯一的，而且还是相等的。这就为重构算法开辟了一个新 的可行的发展方向。目前已知的凸优化工具箱有凸优化工具箱（covex optimization，cvx）11，sedumi 工具箱等12。此外研究者们也提出了很多 实用的迭代重建算法，例如：基追踪算法（basis pursuit, bp）13、正交匹配追 踪算法（orthogonal matching pursuit, omp）14、迭代门限算法（iterative thresholding）15等，并证明了这些算法的收敛性16,17。 1.3 压缩感知的发展现状 2005 年 2 月 e. candes，j. romberg 和 t. tao 共同提出了一种从既不完整也 不精确的测量值中精确重构原信号的新办法。 同时证明了原始信号可以通过它的 部分傅立叶变换系数精确重构。这就为压缩传感理论奠定了数学理论基础18。 随后 e. candes 和 d. donoho 在此基础上于 2006 提出了压缩传感理论1,2。该 理论指出：对于稀疏或压缩的信号而言，我们可以从相对于奈奎斯特-香农采样 定理要求的采样值少很多的测量值中以接近 1 的概率来精确的重构原信号。 我们 可以看出压缩传感理论为信号处理领域提供了新的发展方向，该理论一经提出， 就受到了广大科研工作者的关注19,20。 并在 2007 被评选为年度十大科技进步。 虽然压缩传感理论尚处于理论研究阶段， 但是它已经成为了数学领域和工程 应用领域的一大研究热点，在信息论、信号处理、图像处理、医疗成像、模式识 别、地质勘探、光学/雷达成像、无线通信等领域都受到了高度关注。目前压缩 传感理论衍生发展了分布压缩传感理论21， 1-bit 压缩传感理论22， 贝叶斯压 缩传感理论23，等等。 此外压缩传感理论也引起了世界各个著名大学科研工作者的关注。例如：麻 省理工学院，斯坦福大学，普林斯顿大学，莱斯大学，杜克大学，慕尼黑工业大 学，爱丁堡大学等知名大学都成立了专门的课题组对压缩传感理论进行研究。英 特尔、谷歌、微软等知名公司也开始组织研究压缩传感理论。就连美国空军实验 室也联合杜克大学对压缩传感理论进行研究。 近几年随着压缩传感理论的深入研究， 压缩传感理论在实际中的应用也越来 越多。2006 年莱斯大学的 d. takhar，j. laska，m. wakin 等人提出了一种新型的 基于域压缩的图像压缩照相机框架， 称为单像素相机24， 该相机的构成由图 1.4 来说明。此外他们依此新型相机为模型发表了用于视频表示和编码的压缩图像 成型模型一文25。文章提出了一种新的基于直接获取光域图像的随机投影值 而不是光域像素值的新型数字图像和视频照相机的压缩图像成型模型。 该新型照 相机是用一个数字微镜芯片（digital micromirror device, dmd）替代传统的光 第 1 章 绪论 7 学镜头来完成图像在伪随机二进制模型上的线性投影的光学计算。 它最大的优点 在于集采样和压缩与一体，获得的是原图像的一个采样压缩图像，该图像的数据 量远少于原图像的数据量。其他的优点包括通用性、鲁棒性、可测量性、渐进性 和计算的不对称性。此外，由于新型照相机依赖于一个单独的光探测器，所以它 能够适应各种波长的图像， 而这种性质对于当前的电荷耦合器件 （charge coupled device, ccd）以及互补金属氧化物半导体（complementary metal oxide semiconductor, cmos）是不可能实现的。 透镜 1：将图像以合适 的大小投射到 dmd上 dmd： 用于将图像的某些随机的部分反射到单点传感器。 其整个面积就是图像的大小，维数是图像的分辨率。 图图 1.4 单像素相机的原理 2007 年 12 月 j. haupt， w. bajwa， m. rabbat 和 r. nowak 提出了基于传 感器网络的无线压缩传感技术26。传感器网络是一个具有成百上千的传感器节 点组成的网络。每个传感器节点都能产生数据和传输数据。然后通过一个融合中 心来汇合各个传感器节点的信号信息。 该新型的无线压缩传感技术基于压缩传感 理论提出了一种分散匹配源信道的通信机制。由于该新型机制是传感器节点数 量、功率失真以及等待时间的函数，而且不用考虑数据的先验知识，因此这种新 型的机制具有很强的普适性。 近年来国内大量的科研机构和科研者也开始对压缩传感理论也进行了研究。 西安电子科技大学课题组基于压缩传感理论提出了采用超低速率采样检测超宽 带回波信号的理论27。安徽大学的课题组提出了基于非常稀疏随机矩阵和亚高 斯随机矩阵投影的图像重建方法28,29。 上海理工大学的研究者傅迎华将压缩传 感理论应用到了图像的重构， 通过改变测量矩阵的奇异值从而提高了算法的重构 效率，提高了图像质量30。燕山大学的课题组基于压缩传感理论对 ct 图像的 第 1 章 绪论 8 代数重建算法和手写字符识别方法进行了研究和改进， 并通过实验验证了压缩感 知的优越性31,32。 厦门大学的研究者们将压缩传感理论应用到一维和二维的图 像数据重建， 使得压缩后的图像比传统的先采样后压缩得到的图像有更高的压缩 比，且压缩误差更小33； 1.4 本文工作和文章组织 通过对压缩传感理论的研究和学习，见识了压缩传感理论的优越性。我们从 三个方面展开了工作：首先对已存在的测量矩阵的设计优化算法进行的学习、比 较和研究， 并对其中的一个算法进行了改进； 然后对由 s. rosset 和 j. zhu 在 2007 年提出来的分段线性路径解算法进行了改进； 最后将压缩传感理论应用到图像纹 理分割。本文内容共分为五章，各章节的安排如下： 第一章绪论，论述压缩传感理论的研究背景及意义；然后介绍压缩传感理论 的基本组成和框架；简要阐述压缩传感理论的研究现状，最后介绍本文的主要工 作内容的安排。 第二章介绍压缩传感理论的数学理论基础。 第三章首先介绍并分析最优矩阵设计算法7、有效矩阵设计算法8以及基 于 k-svd 的同时优化算法9这三种测量矩阵的设计算法。然后再针对最优矩阵 设计算法进行改进。 第四章针对 s. rosset 和 j. zhu 在 2007 年提出来的分段线性路径解算法进行 了改进，使其具有更高的普适性。 第五章将压缩传感理论应用到图像纹理分割问题， 并与各种传统的方法做比 较。 第六章是总结与展望，首先总结本论文的主要工作，然后对压缩传感理论进 一步的研究方向和未来的发展趋向进行展望。 第 2 章 压缩传感理论的理论基础 9 第第 2 章章 压缩传感理论的理论基础压缩传感理论的理论基础 压缩传感理论是信号处理领域的一个新兴理论。 它指出对于一个稀疏或者可 压缩的信号，能精确重构该信号所需的观测值要远远少于奈奎斯特-香农采样定 理规定的采样值。这就为信号处理领域的发展提供了新的理论基础。本章首先介 绍压缩传感理论的模型，信号精确重建遵循的几个原则和定理。然后介绍压缩传 感理论的鲁棒性，即在信号的测量值存在被污染的情况时，信号也能高质量的重 构。最后通过一系列的实验验证了压缩传感理论的优越性以及鲁棒性。 2.1 压缩传感的基本模型 2.1.1 信号的稀疏性 假设信号 n xr 是一个我们打算获取和重构的未知信号。 在通常的采样过程 中，该信号需要n个采样值。但是如果x的一个先验知识已经知道，即x是稀疏 或是可压缩的信号，那么在压缩传感理论的框架下，我们仅需要nn个线性测 量值就可以以接近 1 的概率来精确的重构原信号。 信号的稀疏性是压缩传感理论的先决条件， 此外信号的稀疏性还决定着信号 的有效估计、有效压缩、降维和有效模型。因此，在运用压缩传感理论之前我们 首先要确定信号是不是稀疏或者是可压缩的。 首先给出稀疏的几种数学定义。 第一种定义：如果信号x变换系数的支撑集为:0 i ii=，且该支撑集 的势小于等于s，即is。那么我们可以称信号x是s-稀疏的4。 第二种定义：信号x在正交基:,1 j jn=dd下有如下表示：=xd， , ii = x d1。假如对于02p，对于每个充分小的参数0以及过抽样因子，测量矩阵 n n pr对 所有满足条件 /in， （2.6） 的子集i以最小概率 () / 1 o n 来服从 ()() minmax 13 22 tt iiii nn nn p pp p。 （2.7） 其中矩阵 t i p是矩阵 i p 的转置矩阵。 另一种定价表达方式为： 22 13 22 i nn nn xp xx。 （2.8） 那么测量矩阵p就满足一致不确定性原则。 其中矩阵 i p 是提取子集i中索引 对应的矩阵p中的列构成的矩阵，而 max 和 min 分别是矩阵 t ii p p的最大和最小奇 异值。其中常数对 1 3 , 2 2 是使这个定义具体化的一对常数而已，我们可以用在 0 到正无穷之间的两个常数(), a b来代替它们34。 为了更好的理解式（2.6）的内容，我们假设测量矩阵p是部分傅里叶矩阵， 信号x的支持集i满足/in，那么式（2.7）说明信号在频域上投影的能量 最多是 2 3 2 n n x。因此我们可以看到稀疏信号的能量无法同时集中在时域和频域 上，也就是说压缩传感理论也服从信号的不确定性原理35。 第 2 章 压缩传感理论的理论基础 12 2.2.2 精确重建原则 定义定义 2.2 精确重建原则（exact reconstruction principle, erp） ：对于测量矩 阵 n n pr和过抽样因子来讲，如果对所有充分小的参数0，对于服从式 （2.6）的子集i以及在i上的符号矢量( ),1,iii =。具有以下性质的矢量 n sr以接近 1 概率存在。 1. ( )( ),iiii=s。 2. s是测量矩阵p中行矢量的线性组合（例如： t =sp a，a是长度为k的 矢量） 。 3. ( ) 1 ,: 0,1 2 c iiinis。 那么测量矩阵p就服从精确重建原则33。 为了理解精确重建条件与信号重构之间的关系，我们假设x是支持集i上的 信号。那么根据双元性理论（duality theory） ，目标函数（2.5）有唯一解的条件 是存在一个矢量s满足上面的条件。 定理定理 2.1 令测量矩阵 n n pr是满足一致不确定性原则和精确重建原则， 两个原则中的过抽样因子分别为 1 和 2 ，设() 12 max, =，n；假设信号 n xr 在01p。 （2.13） 证明：假设i是 # x 中前i个最大项的集合，那么 # x 满足式（2.12） 。记 m e 是 # x 中前m个最大项的集合，显然有 c m eimi，所以有 () () # 1 c m eimm mixix x () 1 1/ # 11 c c m p i ei xc i x 因此式（2.12）得证。 下面我们证明定理 2.1。 令集合 0 i 和 1 i 分别是x和 # x 里面绝对值项前s最大值的集合。且有 01 iii=，我们假定2sis，且/in，由引理 2.1 得到 ( ) () ( ) 0 0 # 1 11 1 1/ c cc i ii p p ci + xxxx 。 （2.14） 由引理 2.2 得 ( ) () ( ) 0 0 # 1/ c cc i ii p c i + xxxx 。 （2.15） 综上所述 () 1/2 1/ # 2 c p i c i xx。 2.3 压缩传感理论的鲁棒性 在实际应用中，一方面由于观测过程不理想，另一方面由于数据处理的精度 第 2 章 压缩传感理论的理论基础 15 不一样，因此造成了观测信号的不精确。那么压缩传感理论是否能从这些不精确 的观测值中精确的重构出原信号呢？答案是肯定的， 这就说明压缩传感理论具有 一定的鲁棒性36-38。 为了简化情况，我们假设 n xr 为单位阵上的稀疏信号，它的支撑集为i。 此时x的观测值y已经被污染， 即=+ypxe，p是()nn nn?的测量矩阵，e是 误差项，其上界是有限的，即 2 e，0。则此时的目标函数演变为 12 min. .s txpxy。 （2.16） 定义定义2.3 矩阵的s-限制等容常数 s ：对于所有is的子集i以及实系数 矢量, j xji，使得不等式成立的最小常量。 ()() 222 222 11 sis +xp xx （2.17） 其中,1, i inp是一个ni的子矩阵， 它是通过提取集合i中索引对应的测 量矩阵p中的列组成的。其中文献3,39已经证明如果 23 1 sss +， （2.18） 那么我们可以通过目标函数（2.16）来解任意满足is的稀疏信号。 定理定理2.2 如果测量矩阵p服从一致不确定性原则，x为支撑集为i， 且满足 is的充分稀疏信号。令s使得 34 32 ss +成立，那么对于满足 2 e的扰 动e，目标函数（2.16）的解 # x服从以下关系。 #