压缩感知中测量矩阵的优化研究

文献阅读报告课程名称矩阵分析与线性空间任课老师王霞邓科题目压缩感知中测量矩阵的优化研究研究生姓名高蕊董晨霓尚青学号311509101431153130143115091034目录一、压缩感知理论.................................................................................3二、常用测量矩阵.................................................................................42.1随机高斯测量矩阵.....................................................................42.2随机贝努利测量矩阵.................................................................42.3部分哈达玛测量矩阵.................................................................52.4部分正交测量矩阵.....................................................................52.5稀疏随机测量矩阵.....................................................................6三、测量矩阵的设计与优化..................................................................63.1基于近似QR分解的测量矩阵优化方法...................................63.2基于奇异值分解(SVD)的测量矩阵优化方法.............................73.3基于特征值分解的测量矩阵优化方法......................................83.4基于相关性梯度迭代的测量矩阵优化方法............................10四、总结...............................................................................................13参考文献...............................................................................................14一、压缩感知理论由采样定理可知，如果想要从离散的数字信号中无失真地恢复出原始连续信号，则采样频率必须大于或等于原始信号频率的两倍。但是，随着人们对信息需求量的不断增加，奈奎斯特采样率过高，导致采样信息太大，而且先采样后压缩又导致了存储空间的浪费。2006年,Donoho和Candes等人提出了一种全新的信号处理理论——压缩感知理论。压缩感知理论是利用信号的稀疏性或可压缩性，通过低维空间采样数据的非相关性测量来实现高维信号的近似或精确重构。在压缩感知的理论下，信号处理可以以远远低于奈奎斯特采样率的频率进行采样，同时又能保留信号的有用信息，继而可以完全恢复信息。压缩感知的核心思想是在已知信号本身是稀疏的或可以系数表示的前提下，通过设计一种测量矩阵将原始的高维信号投影到一个低维的空间上，然后求解一个非线性优化问题就可以从少量的测量值中较高概率地恢复出原始信号。因此，压缩感知理论包含了三个主要方面：稀疏表示、非相关测量、非线性优化重建。设长度为N的离散实值信号x，在某种变换域下，可以用一组基12,,...,TN的线性组合表示成：1Niiixs或者xs其中，s是x在域中的变换向量，是NN的变换矩阵。当信号x在基上只有个KN个非零系数，则称是x的K稀疏基。信号x经过一个大小为MN的测量矩阵线性投影，得到长度为(MN)M的测量值y：yx（1.1）其中为测量矩阵，大小为MN。若x是可压缩的，则上式可表示为：yxss其中，大小为MN，是稀疏基。由于式（1.1）中，MN，方程个数远比未知数的个数少，所以求解这个方程是十分困难的。要想使式（1.1）有确定的解，则必须满足等距约束性条件（RestrictedIsometryProperty，RIP）：对于任意具有严格K稀疏的向量s，矩阵满足如下不等式222222(1)(1)KKsss其中，K为等距约束常数，且01K。然而，实际中要直接验证矩阵是否满足RIP条件是十分困难的，于是我们可以用RIP的等价情况，即非相干性来引导矩阵的设计。矩阵和矩阵的相干性定义为：1,(,)max,kjkjNN可知，相干系数(,)1,N。相干系数越小，则矩阵和的非相干性越大，就越能精确地重建原始信号。信号重建就是求解式（1.1）的逆问题。可以通过求解0l范数最小问题得到稀疏系数s的近似，也就是含有最少非零元素的解。然后通过xs就可以将x求解出来。由于0l范数难以求解，可以通过求解它的等价问题1l范数最小问题来解得x。二、常用测量矩阵2.1随机高斯测量矩阵构造一个大小为MN的矩阵，使中的每一个元素独立的服从均值为0，方差为1/M的高斯分布，即：,1~(0,)ijNM文献[1]中证明，当随机高斯测量矩阵的测量数McKlog(N/K)时，便会以极大的概率满足RIP条件。随机高斯测量矩阵与大多数的正交基不相关，而且精确重构所需的测量数比较少。2.2随机贝努利测量矩阵构造一个大小为MN的矩阵，使中的每一个元素独立服从贝努利分布，即：,111,1,212111,1,22ijPPMMPPM或,311,1,662320,0,331311,,66ijPPMPPMPPM同随机高斯测量矩阵一样，当随机贝努利测量矩阵的测量数McKlog(N/K)时，便会以极大的概率满足RIP条件(其中c是一个很小的常数)。相对于随机高斯测量矩阵，由于随机贝努利测量矩阵的元素为±1,所以在实际应用中更容易实现和存储。2.3部分哈达玛测量矩阵首先生成一个NN大小的哈达玛矩阵，然后随机的从该哈达玛矩阵中选取M行向量，构成一个大小为MN的测量矩阵。由于哈达玛矩阵是正交矩阵，故部分哈达玛矩阵仍旧具有较强的非相关性，但其维数的大小必须满足2的整数倍，限制了该矩阵的应用范围。2.4部分正交测量矩阵首先生成大小为NN的正交矩阵U，然后在矩阵U中随机的选取M行向量，最后对MN大小的矩阵进行列向量归一化，即得到测量矩阵。在矩阵大小固定的情况下，要是信号能够精确重建，其稀疏度要满足：261(log(N))MKc。当1时，部分正交矩阵就变为部分傅里叶矩阵。2.5稀疏随机测量矩阵首先生成一个大小为MN的全零矩阵，且MN。然后对于矩阵的每一列，随机的选取d个位置并置1。稀疏随机矩阵结构简单,在实际应用中易于构造和保存。三、测量矩阵的设计与优化压缩感知理论的关键就是测量矩阵的设计。一个好的测量矩阵可以使稀疏信号有效的投影到一个低维的空间上而且在压缩的过程中不会丢失携带的有用信息，在重建的过程中使用重构算法能够确保信号被恢复出来。在文献[1]中，我们得知设计的测量矩阵必须要满足几个性质：（1）测量矩阵的列向量必须满足一定的独立性；（2）测量矩阵的列向量要具有跟噪声类似的独立随机性；（3)满足稀疏度的解是满足范数最小的向量。这给矩阵的优化提供了思路。以下是从文献中总结的四个优化方法。3.1基于近似QR分解的测量矩阵优化方法文献[1]中说，测量矩阵Ф的最小奇异值必须要大于某一正常数η0。在书MatrixComputation中说，矩阵的奇异值与其线性相关性密切相关。最小奇异值越大，矩阵的非相关性越强。最大奇异值越小，矩阵的非相关性越强。所以在不改变矩阵的性质的条件下，作者想要尽可能的缩小奇异值的值区间。文献[4]、[5]、[6]中所用到的优化方法是采用近似QR分解。步骤如下：（1）首先将测量矩阵Ф进行标准的QR分解。Q是N×N的方阵，R是N×M的上三角矩阵；（2）由于R的对角线元素远大于非对角线上的元素，所以将R的非对角线上的元素置零，只保留对角线上的元素，生成新的上三角阵R’。（3）用R’替换R，得到了新的测量矩阵Ф’。图1近似QR分解的流程图新的测量矩阵仍满足测量矩阵应有的三个性质。且Ф’的最小奇异值大于Ф，且最大奇异值小于Ф。证明如下：TQRTTRQ''TTRQR的非对角元素全部置零~~~~~minminminminmin~~()()minmin()()()TTTTTTTTTTTTvvvvvRRvvRRvRRvvvvvv^^~~~maxmaxmaxmaxmax^^()()maxmax()()()TTTTTTTTTTTTvvvvvRRvvRRvRRvvvvvv其中~v，^v是列向量，它们的分量对应于矩阵R的对角线中最小元素和最大元素的位置分别取1，其他位置的元素全部为0。近似QR分解缩小了测量矩阵奇异值的取值区间，使新的测量矩阵具有更好的理论最优性。3.2基于奇异值分解(SVD)的测量矩阵优化方法奇异值分解的公式为，若12,...mnrrAC是A的r个正奇异值，则存在m阶正交矩阵U和n阶正交矩阵V，满足10[],(,...)00TTrAUDVUVdiag。奇异值具有很多特性，例如稳定性比例不变性、旋转不变性和降维压缩的特性，所以对测量矩阵进行奇异值分解能够很好的观察它的特性。稀疏信号的非零系数大多集中在低频段，而零系数与近似为零的系数大多集中在高频段，所以可以采用提高前半段测量系数的方法，可在采样次数相同的情况下获得更多信号的信息，从而准确重构原始信号。但是这样会降低矩阵的非相干性。由奇异值分解可得知，最大奇异值越小，矩阵的非相干性越好。所以可以在不改变矩阵的性质的条件下进行奇异值的修正，这样可以使得测量矩阵具有更好的RIP性质。文献[7]具体实现步骤如下：图2基于SVD分解的优化方法流程图3.3基于特征值分解的测量矩阵优化方法研究表明，通过减小测量矩阵与稀疏变换矩阵的互相干系数可以提高其重建性能。互相干系数影响着重建效果和测量值的数目，互相干系数越小，重建信号需要的测量值的数目越少，信号适应的稀疏度范围越大。文献[8]提出了一种基于矩阵特征值分解的测量矩阵优化方法。通过测量矩阵和稀疏变换矩阵构造得到Gram矩阵，并定义了一种基于Gram矩阵非对角线元素的整体互相干系数。在研究Gram矩阵的特征值与互相干系数的关系的基础上，用平均化Gram矩阵大于零的特征值的方法来逐步优化测量矩阵。其中的思想如下：设稀疏变换矩阵为nnR，测量矩阵为mnmR，要使二者的非相干性大，则应使得矩阵D有小的列相干系数。~D为D列单位化后的矩阵。令~~TGDD，称G为Gram矩阵（内积的对称矩阵）。一般情况下互相干系数可定义为可定义为矩阵~D中任意两列的内积的最大值，~~()max{}max{}maxTTijjiijijijijijddDddgdd。但这种定义只能反映局部的相干性，对测量矩阵的性能判断不是太准确。文献[]提出了一种基于整体的互相干系数2()allijijg，它能刻画全局的相干性。这个系数与Gram矩阵的特征值有着密切的联系。所以通过特征值分解调整Gram阵的特征值大小来减小整体互相干系数，从而达到优化测量矩阵的效果。Gram矩