框架表示下的压缩感知问题研究
来源:用户上传
作者:蔡云 石莹
摘 要：压缩感知问题考虑通过较少的测量值来精确恢复未知高维稀疏信号，而实际问题中许多信号在标准正交基上不稀疏，但在一组框架表示下是稀疏的。该文首先对框架表示下的稀疏恢复问题进行阐述，然后系统介绍3个恢复模型即分析基追踪模型、分析LASSO模型和分析Danzig模型，并介绍基于D-RIP条件的最新恢复结果。
关键词：稀疏恢复 框架 恢复模型 D-RIP条件
中图分类号：O29 文献标识码：A 文章编号：1672-3791（2019）10（a）-0173-02
近年来稀疏信号恢复问题引起了国内外研究者的极大关注，稀疏恢复也称压缩感知问题，即考虑从较少的观测数据中以高概率精确恢复未知稀疏信号。现实中绝大多数信号都具有一些特殊的规律如稀疏性，因此稀疏恢复问题已经在许多方面有了广泛的应用，如核磁共振成像（MRI）、雷达、图像处理、地震勘探、传感器网络设计和计算生物学等。稀疏恢复突破了传统的香农采样定理，即不直接对信号值进行采样，而是通过信号与测量函数的内积获得测量值。而且采样时多使用随机测量矩阵，然后通过各种优化方法来恢复未知的稀疏信号[1]。因此，稀疏恢复问题一经提出就引起了国内外许多研究者们的高度关注，如菲尔兹奖获得者T.Tao、美国科学院院士D.Donoho、小波分析理论专家Daubechies和美国科学院院士E.Candes等。同时国内许多研究者也高度关注稀疏恢复问题，包括应用数学、统计、计算机科学、图像处理等领域的研究者，发表了许多重要的研究成果。
1 经典的压缩感知问题
经典的压缩感知（稀疏恢复）问题主要考虑下列的恢复模型：
其中y∈Rm是测量向量，A∈Rm×n（m≤n）是线性测量矩阵，稀疏恢复的主要任务是通过观测数据y和A来恢复未知x。显然该方程组具有不确定性，也即有許多解。通常假设x是稀疏的，并假设测量矩阵具有一些良好的性质，这时该线性方程组具有唯一解。当向量x中非零未知分量的个数最多为k个时，称信号为k-稀疏信号。
最直接的求解上述线性方程组的方法是求解如下的l0最小化问题，也即l0最小化方法：
其中l0范数定义为向x量的非零元素的个数。但是直接求解上述l0最小化问题是NP-难的，并且在计算上是不可行的。因此研究者们寻找了很多替代l0最小化方法的求解方法，最直接且简单的方法是l0最小化方法的凸松弛方法即最l1小化方法，即为求解如下的凸优化问题：
其中是向量x的l1范数。l1最小化问题是凸优化问题，并且能用线性规划的很多方法求解如半正定法。
研究者们关注在什么情况下上述两个问题等价即求得的解相同，文献中对测量矩阵提出了许多条件，最常用的条件主要有3个：列相干性条件（MIP）、零空间条件（NSP）和约束等距条件（RIP）[1]。其中最简单常用的条件是RIP条件，定义如下。
定义1[1]：A∈Rm×n对于测量矩阵和正整数（k≤n），对所有的k-稀疏向量x∈Rn，矩阵A的k阶约束等距常数（RIC）δk定义为满足如下不等式的最小常数：
若有上述不等式成立，则称测量矩阵A满足k阶RIP条件。
注意到RIP条件具有类似于正交矩阵的性质，并且对于确定性的矩阵不好判断是否满足RIP条件，因此通常采用随机测量矩阵。文献表明高斯随机测量矩阵、次高斯随机测量矩阵以及部分随机Fourier测量矩阵等都以大概率满足RIP条件。有许多研究者们都对RIP条件做了大量的研究。其中，Candes首先指出当测量矩A阵满足时，l1最小化能准确地恢复未知k-稀疏信号x。最新的研究结果是Cai和Zhang给出是最优界。具体详细内容可以参见参考文献[2-5]。
2 框架表示下的压缩感知问题
对于在一组标准正交基下稀疏的信号，上述的恢复方法和恢复条件是适用的。但是现实中也存在许多信号在标准正交基下不稀疏，但却在一组框架表示下是稀疏的，也即未知信号f可以表示为f=Dx，其中D∈Rn×d（n≤d）是冗余的框架，x是稀疏或者逼近稀疏的d维向量。这样的例子有很多，例如阵列信号处理中的信号模型、声纳信号和反射雷达以及图像曲线等，具体可见文献[3-4]。
这时线性测量模型y=Af可写为y=ADx，显然最直接的方法是可以利用经典压缩感知理论中的恢复模型先得到最优的x*，然后再利用合成算子即f*=Dx*得到未知信号。这种方法称为l1合成法。显然该方法直接易懂，但该方法要求满足经典压缩感知理论中的测量矩阵所满足的条件如RIP条件，注意到当冗余框架D之间的列相干性较大时，AD一般不满足经典的RIP条件。于是研究者们又开始寻求其他的恢复模型，比较常用的是l1分析法，该种方法通过求解某个l1最小化问题来直接求解f。
3 恢复模型
现实中测量模型通常含有噪声，如l2范数有界噪声、脉冲噪声，以及Danzig Selector噪声等。因此测量模型可写为：
其中是观测噪声。最常用的恢复模型有3个：分析基追踪（ABP）[4]、分析LASSO模型（ALASSO）和分析Danzig模型（ADS）[3]，分别表示如下：
其中ε、λ是噪音界，μ是调节参数。类似于经典的压缩感知问题，Candes等提出了基于框架下的约束等距条件（D-RIP）来研究框架表示下的压缩感知问题。具体定义如下，也可见文献[4]。
定义2（D-RIP）：对于测量矩阵D∈Rn×d和正整数k≤d，对所有的k-稀疏向量v∈Rd，矩阵的阶D-约束等距常数（D-RIC）δk定义为满足如下不等式的最小常数：
若有上述不等式成立，则称测量A矩阵满足k阶D-RIP条件。 并且Candes等指出高斯以及次高斯随机测量矩阵以高概率满足D-RIP条件，而且运用Johnson-Lindenstrauss引理可知，随机测量矩阵如果满足经典的RIP条件时，该矩阵也以高概率满足D-RIP条件，因此部分随机傅立叶测量矩阵以大概率满足D-RIP条件[4]。利用D-RIP条件，文献[3]和[4]给出了模型（1）（2）（3）的恢复结果，为完整起见，下面以定理形式给出3个模型的恢复结果，具体证明可参见文献[3-4]。
定理1[4]：对恢复模型（1），当测量矩阵满足δ2k﹤00.8且时，对于在紧框架D表示下的k稀疏信号f，C1为仅依赖于δ2k的常数，那么（1）的最优解f*满足。
定理2[3]：对恢复模型（2），当测量矩陣满足，取参数μ使得时，对于在紧框架D表示下的k稀疏信号f，C1为依赖于δ3k的常数，那么（2）的最优解fAL满足：
定理3[3]：对恢复模型（3），当测量矩阵满足，噪声满足时，对于在紧框架D表示下的k稀疏信号f，C3为依赖于δ3k的常数，那么（3）的最优解fADS满足：
参考文献
[1] S.Foucart，H.Rauhut，A Mathematical Introduction to Compressed Sensing[M].Birkhauser，2013.
[2] 蔡云.稀疏逼近中几个经典算法的理论分析[D].浙江大学，2015.
[3] 林俊宏.框架表示下的稀疏恢复[D].浙江大学，2013.
[4] E.Candes，Y.Eldar，D.Needell，P.Randall，Compressed sensing with coherent and redundant dictionaries[J].Appl.Comput. Harmon.Anal，2011（31）：59-73.
[5] T.Cai，A.Zhang，Sparse representation of a polytope and recovery of sparse signals and low rank matrices[J].IEEE.Trans. Inf. Theory，2014，60（1）：122-132.
转载注明来源:https://www.xzbu.com/8/view-15065360.htm
