x 是 K -稀疏的信号，若存在常数 0 k 1 ，使得下面的式子成立：

其中 k 是等容常数， T 对应于矩阵 的列向量，那么就说测量矩阵 满足 ~ (K,k ) 的 K 阶 限制等容性。常用的满足限制等容性的测量矩阵有：随机高斯测量矩阵、部分傅立叶测量矩 阵和贝努利测量矩阵等。测量矩阵的设计已经成为了压缩感知理论中的一个重要的研究方向， 测量向量的选择直接影响着测量向量的好坏，如何选取更有效的测量矩阵从而使得的测量向 量在相同的重构算法中表现得更好是测量矩阵研究中关心的主要问题。论文网

2。3 图像重构算法

重构算法在压缩感知理论中至关重要，它直接影响着信号最终的重构效果。重构算法的 目标是期望达到利用尽可能低维度的测量向量来得到原始图像更为精准的重构效果。重构算 法主要包括：凸优化算法，贪婪算法和组合算法。目前文献中提出的凸优化方法有内点方法、 预计梯度法、以及迭代硬阈值(IHT)、基于布雷格曼(Bregman)距离的Bregman迭代等。贪婪算 法主要包括匹配追踪(MP)、正交匹配追踪(OMP)以及正则化的正交匹配追踪(ROMP)等，组合 算法主要包括傅立叶采样追踪等。

重构算法关心的是从少量的测量值中准确的恢复原始信号。即对于一个测量向量 y  CM  ，

重构就是从 M 维的测量向量中准确恢复出 N 维的原始信号 x RN ，其中 M N 。重构过程 就是要求解满足等式 y x 的信号 x ，很明显，因为 M N 所以求解过程是病态的，问题的 解有无限多个，无法直接求解。但如果加入信号 x 是稀疏的这个限制，则这个问题的求解过

程发生了变化。对于一个稀疏信号 x RN ，因为

x   反应了信号的稀疏性。

若得到原始信号的测量向量为 y RM  ，则其重构过程可以表达为：

其中 为测量矩阵。若原始信号不具有稀疏性，但可以在某个稀疏基上进行稀疏表示，则先 对信号进行稀疏表示。若变换矩阵为 ，变换后的等价稀疏向量为 s ，即 x s ，将 x s 带 入上面的约束条件中，并把测量矩阵和稀疏基的乘积记为感知矩阵 ，即问题（2。5）可以转 换为：

因为上面的目标函数 

是非凸的，想要直接求解这个问题是 NP 难的，因此可以用凸松弛函

数来代替上面的非凸目标函数，即：

问题（2。7）是凸的并且可以使用线性规划求解。 上面提到了只有当矩阵具有限制等容性时才能保证得到的测量值能准确的重构原始信

号，但是直接使用 RIP 条件判断是相当有难度的，可以使用不相干性替代限制等容性［14］。两 个矩阵之间的相干性可以由下面的函数描述：

这个函数表达了组成两个矩阵的向量之间不能相互表示。实验结果证明当变换矩阵和测量矩 阵的不相干度越强时，即当式（2。8）函数的值越接近于 1 时，重构的结果越准确。

本章介绍了压缩感知的基本概念和理论框架，下一章会介绍一种基于非局部低秩特性的 重构算法，并对算法原理进行详细的阐述。

3 基于非局部低秩正则化的压缩感知重构算法 

3。1 非局部相似模型

稀疏性或可压缩性是压缩感知理论成功的必要前提条件，正是因为加入了信号稀疏这样 的先验条件使得原本病态的重构问题变得可以求解。然而自然图像的结构多变，若仅使用固 定基下稀疏性会使得重构算法失去灵活性，对于不同类型的图像重构效果往往不稳定。而图 像的非局部相似性是运用在图像重构中比稀疏性更高阶的先验知识，它体现了图像像素点之 间的关系。通过对自然图像的观察会发现，像素点并不是独立的，如果对图像进行分块，自 然图像经常会出现图像块结构相似的情况，例如在图像中取一个小图像块出来，它经常会和 周围的块呈现相似的几何结构，通常相似块像素值也是相近的。目前，这种自相似性主要运 用于纹理合成、图像超分辨率研究和图像的重构中。非局部相似模型的其基本思想是对图像 进行分块，这些块可以之间可以重合，根据块与块之间的相似度进行聚类，因为这些块是相 似块的，由其像素值的向量表示形式形成的向量组是相关的，则相似块组形成的矩阵具有低 秩特性，可以利用低秩特性对图像进行重构。在提高图像表示稀疏度的同时进一步提高了压 缩感知图像恢复效率, 恢复图像对于自然图像多变的结构有着较强的适应性和保持性。