成立,其中为中由索引T所指示的相关列构成的大小为的子矩阵,则称矩阵满足约束等距性。
这个充要条件和Candés、Tao等人提出的稀疏信号在观测矩阵作用下必须保持的几何性质相一致。即,要想使信号完全重构,必须保证观测矩阵不会把两个不同的K-项稀疏信号映射到同一个采样集合中,这就要求从观测矩阵中抽取的每M个列向量构成的矩阵是非奇异的。可以看出,问题的关键是如何确定非零系数的位置来构造一个可解的线性方程组。
然而判定给定的是否具有RIP性质是比较复杂的,为降低复杂度,能否找一种易于实现RIP条件的替代方法成为构造观测矩阵的关键。
如果保证观测矩阵和稀疏基不相干,则在很大概率上满足RIP性质。不相干是指向量不能用稀疏表示[15]。不相干性越强,互相表示时所需的系数越多;反之,相关性越强。
通过选择高斯随机矩阵作为即可高概率保证不相干性和RIP性。如,可以生成多个零均值、方差为的随机高斯函数,将它们作为观测矩阵的元素,使得以很高的概率具有RIP性质。随机高斯矩阵有个有用的性质:对于一个的随机高斯矩阵,可以证明当时在很大概率下具有RIP性质(c是一个很小的常数)。总之,随机高斯矩阵与大多数固定正交基构成的矩阵不相关。这一特性决定了选它作为观测矩阵,其它正交基作为稀疏变换基时,满足RIP性质。因此,可以从M个观测值中以很高的概率去恢复长度为N的K-项稀疏信号X。其他能使传感矩阵满足约束等距性的测量矩阵还有一致球矩阵、二值随机矩阵、局部傅立叶矩阵、局部哈达玛矩阵以及托普里兹矩阵等。
2.3、信号重构
信号重构是压缩感知理论的重要部分。为更清晰地描述压缩感知理论的信号重构问题,首先定义向量的p-范数为
当时得到0-范数,它实际上表示X中非零项的个数。于是,在信号系数或可压缩的前提下,求解欠定方程组的问题转化为最小0-范数问题。但是,它需要列出X中所有非零项位置的种可能的线性组合,才能得到最优解。因此,求解最小0-范数问题的数值计算极不稳定而且是NP难问题。鉴于此,研究人员提出了一系列求得次最优解的算法,主要包括最小范数法、匹配追踪(Matching Pursuit, MP)系列算法、迭代阈值法(Iterative Shrinkage/Threshold, IST)以及专门处理二维图像问题的最小全变分法(Total Variation, TV)等,其中最小范数法和迭代阈值法属于将非凸问题转化为凸问题的凸松弛法。
2.3.1 最小范数法
Chen,Donoho,Saunders指出,求解一个更加简单的优化问题会产生同等的解:
使得问题变成了一个凸优化问题,于是可以方便地化简为线性规划问题,典型算法代表:基追踪(Basis Pursuit, BP)算法,计算复杂度的量级为。若考虑重构误差,上述问题可以转换为如下最小范数问题,
或者经典形式:
最小范数问题也可以转化为求解Lagrangian函数形式:
或著名的LASSO(Least Absolute Shrinkage andSelection Operator)问题:
最优化理论证明,当参数满足一定的关系时,这三个问题的求解是等价的。
2.2.2 匹配追踪法
匹配追踪算法是一种贪婪迭代算法,其基本思想在每一次的迭代过程中,从过完备原子库中(测量矩阵)选择与信号最匹配的原子(列向量)来构建稀疏逼近,并求出与信号的残差,然后继续选择与信号残差最为匹配的列向量,经过一定次数的迭代,信号可以由一些原子线性表示。但是由于信号在已选定原子集合上的投影的非正交性使得每次迭代的结果可能是次最优的,因此为获得收敛可能需要经过较多次迭代。正交匹配追踪算法(Orthogonal Matching Pursuit, OMP)则有效克服了这个问题,该算法沿用了匹配追踪算法中的原子选择规则,只是通过递归地对已选择原子集合进行正交化以保证迭代的最优性,从而减少了迭代次数。实验表明[13]对固定K稀疏N维离散时间信号x,用一个的高斯矩阵测量时,只要,正交匹配追踪算法以极大概率准确重构信号,而且比最小范数法更快。但是,正交匹配追踪算法精确重构的理论保证比最小范数法弱,并非对所有信号都能准确重构,而且对于测量矩阵的要求比约束等距性更加严格。Needell等在OMP基础上提出了正则正交匹配追踪(Regularized Orthogonal Matching Pursuit, ROMP)算法,对所有满足约束等距性条件的矩阵和所有稀疏信号都可以准确重构。另外,压缩采样匹配追踪算法(Compressive Sampling Matching Pursuit, CoSaMP)也可以用于很好地重构信号,提供了比OMP、ROMP更全面的理论保证,并且能在采样过程中对噪声鲁棒。