压缩感知中RIP界的研究新进展

蔡云　石莹　杨文国

摘  要：该文对压缩感知（稀疏恢复）问题的研究背景以及研究模型进行了详细阐述，并对基于最小化的恢复模型准确恢复未知稀疏信号的恢复条件进行系统介绍，最后对基于约束等距条件（RIP）条件的恢复结果进行归纳总结。

关键词：压缩感知  稀疏  RIP条件

中图分类号：O29    文献标识码：A 文章编号：1672-3791（2019）09（c）-0237-02

现今社会处于大数据研究时代，海量数据带来更多信息，但也带来了数据信号存储、传输和分析的困难。近年来，由菲尔兹奖获得者T.Tao、美国科学院院士D.Donoho和美国科学院院士E.Candes等学者提出的压缩感知理论为该问题的解决提供了全新的方法：当未知的高维信号是稀疏信号时，可以通过求解优化问题从较少的非自适应线性投影数据中以高概率精确重构原始未知信号。压缩感知理论突破了传统香农采样定理中对信号采样频率的限制，给信号采样理论带来了新的变革，在核磁共振成像、雷达、图像处理、地震勘探、传感器网络设计和计算生物学等领域都有着广阔的应用前景[1]。压缩感知已经成为国内外应用数学及其交叉学科极为热门的研究前沿，激发了包括应用数学、统计、电气工程、计算机科学和医学等方面的研究人员极大的研究兴趣和热情。

1  压缩感知理论

压缩感知的主要任务可归结为求解如下线性方程组：

其中y∈Rm是观测向量，A∈Rm×n（m≤n）是线性测量矩阵，压缩感知的主要任务是从已知的观测向量y和线性测量矩阵A中准确恢复未知信号。显然，方程组是不确定性的，即它有无穷多解。但当假设未知信号具有某种特殊结构即稀疏性时，且测量矩阵A满足良好的性质时，该方程有唯一的稀疏解。当向量中非零未知分量的个数最多为k个时，称信号为k-稀疏信号。

求解该线性方程组最自然的方法是求解如下的l0最小化问题：

其中是向量的l0范数即向量的非零元素的个数。但由于求解上述l0最小化方法是NP难问题且计算不可行，因此研究者们寻找许多快速有效地求解最稀疏解的算法来替代l0最小化方法。其中，l1最小化方法是l0最小化方法的凸松弛方法，它在于求解如下的优化问题：

其中是向量的l1范数。上述l1最小化问题是凸优化问题，并能用线性规划的许多方法求解如半正定法。

2  约束等距条件（RIP条件）

l1最小化方法的解和l0最小化方法的解在什么情况下一致是数学家们极为关心的问题。探讨这两个问题等价的常用条件通常有3个：零空间条件（NSP）、非相干性条件（MIP）和约束等距条件（RIP条件）。在这3个条件之中最常用的条件为RIP条件，下面介绍RIP条件的具体定义[1]。

定义1：对于线性测量矩阵A∈Rm×n和正整数k≤n，对于所有的k-稀疏向量∈Rn，矩阵A的k阶约束等距常数（RIC）δk定义为满足下面不等式的最小常数：

如果有上述不等式成立，则称测量矩阵A满足k阶RIP条件。

注意到，一个矩阵具有较小的RIP条件意味着矩阵A的每k个或者更少的列构成的子矩阵近似于一个正交矩阵。验证某个确定性矩阵是否满足RIP条件是较为困难的。因此，学者们通常构造满足良好RIP条件的随机性矩阵。并且有研究表明，当测量次数m满足m≥Cδ-2klog（n/k）时，则高斯随机矩阵以及次高斯随机矩阵以高概率满足RIP条件且δk﹤δ。另外，也有学者表明根据l1球宽度理论，测量次数m对于k和n的阶数达到了最佳阶数。RIP条件对于一大类结构随机矩阵也满足例如Gabor随机矩阵和 Topellitz随机矩阵[1]。当测量次数满足m≥Cδ-2klog4n时，部分随机傅立叶测量矩阵也以大概率满足RIP条件且δk﹤δ。另外，有研究表明，如果随机测量矩阵A满足如下的集中不等式：对于任意给定的∈Rn和0﹤δ﹤1固定和常数，c，t﹥0。

那么当测量次数m≥cδ2nk，测量矩阵A以极大概率满足RIP条件且RIC常数满足δk≤δ。

3  其他恢复方法

对于压缩感知问题，除了可以使用l1最小化方法替代l0最小化方法之外，研究者们也常用一种非凸优化的方法来恢复未知稀疏信号，即lp（0﹤p﹤1）最小化方法，即考虑用非凸范数来逼近零范数：

测量矩阵A以极大概率满足p-RIP条件时，lp（0﹤p﹤1）最小化方法能准确恢复未知稀疏信号。p-RIP条件定义如下[1]。

定义2：对于线性测量矩阵A∈Rm×n和正整数k≤n，对于所有的k-稀疏向量∈Rn，矩阵A的k阶p-约束等距常数（p-RIC）δk定义为满足下面不等式的最小常数：

如果有上述不等式成立，则称测量矩阵A满足k阶p-RIP条件。

并且研究者表明高斯随机测量矩阵以高概率满足p-RIP条件，另外数值实验也表明lp（0﹤p﹤1）最小化方法具有较好的可实现性和算法快速计算的优势[2]。

除了用上述的凸优化和非凸优化方法直接求解未知稀疏向量，在数值算法方面，学者们主要用贪婪算法来求解稀疏界，例如匹配追踪算法（MP）、正交匹配追踪算法（OMP）、逐步回归匹配追踪算法（StOMP）、压缩采样匹配追踪算法（CoSsMP）、硬阈值迭代算法（IHT）、迭代加权最小二乘算法（IRLS）、投影梯度下降算法（PGT）、软阈值迭代算法（SHT）。各种算法在收敛性和收敛速度以及计算时间上各有优势，具体可见参考文献[1-2]。

4  最新RIP研究进展

在实际应用中，观测向量通常含有噪声，也即有下面的观测模型y=Ax+z，其中y∈Rm是观测向量，A∈Rm×n（m≤n）是线性测量矩阵，z∈Rm是噪声向量，常用的方法是考虑如下的l1约束优化问题：

其中ε是噪声界估计。

有许多学者对问题（7）进行了研究，特别地针对基于RIP条件的恢复，Candes首先指出当测量矩阵A满足RIP条件且时，l1最小化和恢复模型（1）能分别准确地和稳定地恢复未知稀疏信号。之后又有许多学者对这个界进行了改进，例如，Foucart 和Lai给出了δ2k﹤0.4531，Mo和Li将这个界改进至δ2k﹤0.4931，Cai和Zhang给出δ2k﹤0.5，之后他们又给出是最优界[3-4]。对于高阶RIP恢复条件的研究，最近Zhang和Li给出了一个公认的最优结果，为了完整起见，我们简要列出定理内容，具体可参见文献[3]。

定理1：考虑恢复模型（1），当时，当测量矩阵满足且时，对于k稀疏信号那么（1）的最优解*满足：

5  结语

该文具体介绍了压缩感知的應用和理论背景，并介绍了压缩感知的几种恢复方法以及恢复条件，并系统介绍了基于RIP条件的一些研究进展及相应结果，最后介绍了压缩感知RIP界的最新定理。

参考文献

[1] S.Foucart， H.Rauhut.A Mathematical Introduction to Compressed Sensing[M].Birkhauser，2013.

[2] 蔡云.稀疏逼近中几个经典算法的理论分析[D].浙江大学，2015.

[3] 章瑞.压缩感知中最优限制等距常数界[D].浙江大学，2017.

[4] T.Cai， A.Zhang， Sparse representation of a polytope and recovery of sparse signals and low rank matrices[J].IEEE Transactions on information theory，2014，60（1）：122-132.