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

文献阅读报告

课程名称 矩阵分析与线性空间

任课老师 王霞 邓科

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

研究生姓名 高蕊 董晨霓 尚青

学 号 3115091014 3115313014 3115091034

目 录
一、压缩感知理论 2
二、常用测量矩阵 4
2.1 随机高斯测量矩阵 4
2.2 随机贝努利测量矩阵 4
2.3 部分哈达玛测量矩阵 5
2.4 部分正交测量矩阵 5
2.5 稀疏随机测量矩阵 5
三、测量矩阵的设计与优化 5
3.1 基于近似QR分解的测量矩阵优化方法 5
3.2 基于奇异值分解(SVD)的测量矩阵优化方法 6
3.3 基于特征值分解的测量矩阵优化方法 7
3.4 基于相关性梯度迭代的测量矩阵优化方法 9
四、总结 12
参考文献 13

一、 压缩感知理论
由采样定理可知，如果想要从离散的数字信号中无失真地恢复出原始连续信号，则采样频率必须大于或等于原始信号频率的两倍。但是，随着人们对信息需求量的不断增加，奈奎斯特采样率过高，导致采样信息太大，而且先采样后压缩又导致了存储空间的浪费。2006年,Donoho和Candes等人提出了一种全新的信号处理理论——压缩感知理论。压缩感知理论是利用信号的稀疏性或可压缩性，通过低维空间采样数据的非相关性测量来实现高维信号的近似或精确重构。在压缩感知的理论下，信号处理可以以远远低于奈奎斯特采样率的频率进行采样，同时又能保留信号的有用信息，继而可以完全恢复信息。
压缩感知的核心思想是在已知信号本身是稀疏的或可以系数表示的前提下，通过设计一种测量矩阵将原始的高维信号投影到一个低维的空间上，然后求解一个非线性优化问题就可以从少量的测量值中较高概率地恢复出原始信号。因此，压缩感知理论包含了三个主要方面：稀疏表示、非相关测量、非线性优化重建。
设长度为N的离散实值信号x，在某种变换域下，可以用一组基的线性组合表示成：
或者
其中，s是x在域中的变换向量，是的变换矩阵。当信号x在基上只有个K<<N个非零系数，则称是x的K稀疏基。
信号x经过一个大小为的测量矩阵线性投影，得到长度为的测量值y：
（1.1）
其中为测量矩阵，大小为。
若x是可压缩的，则上式可表示为：

其中，大小为，是稀疏基。
由于式（1.1）中，，方程个数远比未知数的个数少，所以求解这个方程是十分困难的。要想使式（1.1）有确定的解，则必须满足等距约束性条件（Restricted Isometry Property，RIP）：
对于任意具有严格K稀疏的向量s，矩阵满足如下不等式

其中，为等距约束常数，且。
然而，实际中要直接验证矩阵是否满足RIP条件是十分困难的，于是我们可以用RIP的等价情况，即非相干性来引导矩阵的设计。
矩阵和矩阵的相干性定义为：

可知，相干系数。相干系数越小，则矩阵和的非相干性越大，就越能精确地重建原始信号。
信号重建就是求解式（1.1）的逆问题。可以通过求解范数最小问题得到稀疏系数s的近似，也就是含有最少非零元素的解。然后通过就可以将x求解出来。由于范数难以求解，可以通过求解它的等价问题范数最小问题来解得x。

二、常用测量矩阵
2.1 随机高斯测量矩阵
构造一个大小为的矩阵，使中的每一个元素独立的服从均值为0，方差为1/M的高斯分布，即：

文献[1]中证明，当随机高斯测量矩阵的测量数时，便会以极大的概率满足RIP条件。随机高斯测量矩阵与大多数的正交基不相关，而且精确重构所需的测量数比较少。
2.2 随机贝努利测量矩阵
构造一个大小为的矩阵，使中的每一个元素独立服从贝努利分布，即：

或

同随机高斯测量矩阵一样，当随机贝努利测量矩阵的测量数时，便会以极大的概率满足RIP条件(其中c是一个很小的常数)。相对于随机高斯测量矩阵，由于随机贝努利测量矩阵的元素为±1,所以在实际应用中更容易实现和存储。
2.3 部分哈达玛测量矩阵
首先生成一个大小的哈达玛矩阵，然后随机的从该哈达玛矩阵中选取M行向量，构成一个大小为的测量矩阵。由于哈达玛矩阵是正交矩阵，故部分哈达玛矩阵仍旧具有较强的非相关性，但其维数的大小必须满足2的整数倍，限制了该矩阵的应用范围。
2.4 部分正交测量矩阵
首先生成大小为的正交矩阵U ，然后在矩阵U中随机的选取M行向量，最后对大小的矩阵进行列向量归一化，即得到测量矩阵。在矩阵大小固定的情况下，要是信号能够精确重建，其稀疏度要满足：。当时，部分正交矩阵就变为部分傅里叶矩阵。
2.5 稀疏随机测量矩阵
首先生成一个大小为的全零矩阵，且。然后对于矩阵的每一列，随机的选取d个位置并置1。稀疏随机矩阵结构简单,在实际应用中易于构造和保存。

三、测量矩阵的设计与优化
压缩感知理论的关键就是测量矩阵的设计。一个好的测量矩阵可以使稀疏信号有效的投影到一个低维的空间上而且在压缩的过程中不会丢失携带的有用信息，在重建的过程中使用重构算法能够确保信号被恢复出来。在文献[1]中，我们得知设计的测量矩阵必须要满足几个性质：（1）测量矩阵的列向量必须满足一定的独立性；（2）测量矩阵的列向量要具有跟噪声类似的独立随机性；（3)满足稀疏度的解是满足范数最小的向量。这给矩阵的优化提供了思路。以下是从文献中总结的四个优化方法。
3.1 基于近似QR分解的测量矩阵优化方法
文献[1]中说，测量矩阵Ф的最小奇异值必须要大于某一正常数η>0。在书Matrix Computation中说，矩阵的奇异值与其线性相关性密切相关。最小奇异值越大，矩阵的非相关性越强。最大奇异值越小，矩阵的非相关性越强。所以在不改变矩阵的性质的条件下，作者想要尽可能的缩小奇异值的值区间。文献[4]、[5]、[6]中所用到的优化方法是采用近似QR分解。步骤如下：
（1） 首先将测量矩阵Ф进行标准的QR分解。Q是N×N的方阵，R是N×M的上三角矩阵；
（2） 由于R的对角线元素远大于非对角线上的元素，所以将R的非对角线上的元素置零，只保留对角线上的元素，生成新的上三角阵R’。
（3） 用R’替换R，得到了新的测量矩阵Ф’。

R的非对角元素全部置零

图1 近似QR分解的流程图
新的测量矩阵仍满足测量矩阵应有的三个性质。且Ф’的最小奇异值大于Ф，且最大奇异值小于Ф。证明如下：
其中，是列向量，它们的分量对应于矩阵R的对角线中最小元素和最大元素的位置分别取1，其他位置的元素全部为0。
近似QR分解缩小了测量矩阵奇异值的取值区间，使新的测量矩阵具有更好的理论最优性。
3.2 基于奇异值分解(SVD)的测量矩阵优化方法
奇异值分解的公式为，若是A的r个正奇异值，则存在m阶正交矩阵U和n阶正交矩阵V，满足。奇异值具有很多特性，例如稳定性比例不变性、旋转不变性和降维压缩的特性，所以对测量矩阵进行奇异值分解能够很好的观察它的特性。
稀疏信号的非零系数大多集中在低频段，而零系数与近似为零的系数大多集中在高频段，所以可以采用提高前半段测量系数的方法，可在采样次数相同的情况下获得更多信号的信息，从而准确重构原始信号。但是这样会降低矩阵的非相干性。由奇异值分解可得知，最大奇异值越小，矩阵的非相干性越好。所以可以在不改变矩阵的性质的条件下进行奇异值的修正，这样可以使得测量矩阵具有更好的RIP性质。文献[7]具体实现步骤如下：
图2 基于SVD分解的优化方法流程图
3.3 基于特征值分解的测量矩阵优化方法
研究表明，通过减小测量矩阵与稀疏变换矩阵的互相干系数可以提高其重建性能。互相干系数影响着重建效果和测量值的数目，互相干系数越小，重建信号需要的测量值的数目越少，信号适应的稀疏度范围越大。文献[8]提出了一种基于矩阵特征值分解的测量矩阵优化方法。通过测量矩阵和稀疏变换矩阵构造得到Gram 矩阵，并定义了一种基于Gram 矩阵非对角线元素的整体互相干系数。在研究Gram 矩阵的特征值与互相干系数的关系的基础上，用平均化Gram 矩阵大于零的特征值的方法来逐步优化测量矩阵。其中的思想如下：
设稀疏变换矩阵为，测量矩阵为，要使二者的非相干性大，则应使得矩阵有小的列相干系数。为D列单位化后的矩阵。令，称G为Gram矩阵（内积的对称矩阵）。一般情况下互相干系数可定义为可定义为矩阵 中任意两列的内积的最大值，。但这种定义只能反映局部的相干性，对测量矩阵的性能判断不是太准确。文献[]提出了一种基于整体的互相干系数，它能刻画全局的相干性。这个系数与Gram矩阵的特征值有着密切的联系。所以通过特征值分解调整Gram阵的特征值大小来减小整体互相干系数，从而达到优化测量矩阵的效果。
Gram矩阵若有m个大于0的特征值，则以下两个等式成立：
（矩阵所有特征值的和等于矩阵对角线上的元素之和）

（的特征值为G的特征值的平方; 中对角线上元素的和为）
由上述等式可得，要使得Gram矩阵的非对角线的元素平方和最小，只需求解下列式子

又=1，所以要使互相干系数最小，就要使Gram矩阵的特征值之和不变的情况下，他们的平方和达到最小。当每个特征值都等于他们的平均值n/m时，它们的平方和最小。所以采用迭代的方法进行对特征值的修正，使特征值逐步逼近极限值n/m。达到最优时则。具体实现步骤为：

图3 基于特征值分解的优化方法流程图
3.4 基于相关性梯度迭代的测量矩阵优化方法
与上一种方法类似,文献[2]和[9]在其基础上提出了一种梯度迭代的优化方法。即利用恢复图像的均方误差E最小来求得最优解。首先定义了Gram矩阵, 为D列单位化后的矩阵,和测量矩阵和系数矩阵之间的互相干系数。
令表示中任意两列的内积最大值，即。且定义为Gram矩阵中非对角元素的相干系数均值。假设D的列向量之间完全不相关，则，即Gram矩阵的非对角元素均为0。这种情况实际中不可能实现。所以定义一个近似的公式。
将上式进行变换，得。
将对称矩阵进行特征值分解。
然后又得到公式
定义，则上式可变换成
定义均方误差E=MSE=，能够满足该式的即为所求。
由上式可知，如果，则E=0。 所以这个问题可以转化成最小化问题。
定义,所以只要研究令F最小的。
因为是对称矩阵，所以特征值分解对应的是一个对角阵，可以表示成 ，如果特征值里有零的话，可以用伪逆来代替。
最小化F得迭代过程如下。设的初始值为，整体的迭代算法可表示为，>0是步长，是F对的梯度。且由上面的式子可求得。所以迭代的数据更新公式为。 当达到局部最小值时，迭代就停止下来。然后得到优化后的测量矩阵。整体的步骤如下：

图4 基于梯度迭代的优化方法

四、总结
通过阅读文献，我了解了压缩感知的基本定义，理解了压缩感知的基本理论和数学模型。知道了压缩感知的实现过程主要分为三步：信号的稀疏性质是前提，测量矩阵的设计是关键，非线性优化重建是信号重构的途径。测量矩阵的设计与优化在压缩感知的整个过程中起到了非常关键的作用，因为它既涉及到了能够使信号投影到低维的空间且压缩不丢失有效的信息，也涉及到了能否将信号极大可能的重建恢复出来。在设计时，RIP理论是其理论依据，但由于现实中很难判别，所以用相关性检测理论可以直观的判别测量矩阵的性质。这也是测量矩阵优化的目标。更具体一点的就是让测量矩阵和稀疏矩阵的非相干性越大越好。为了实现这一目标，报告中介绍了四种方法。总体来说都是为了减小矩阵列向量的相关性。QR分解和奇异值分解的方法是直接对测量矩阵进行处理，QR分解是缩小值的取值区间从而增加了测量矩阵的列相关性。奇异值分解除了处理奇异值，还利用非零系数集中在低频段而增大了前半段的测量系数。基于特征值分解的方法和梯度迭代的方法是将测量矩阵和稀疏矩阵相乘，定义了互相关系数从而达到减小二者的相关性。基于特征值分解的方法是通过迭代使得Gram矩阵的非对角元素尽可能为0使互相关系数减少。梯度迭代的方法直接假设gram矩阵近似单位阵，然后推导出一系列的公式，寻找误差最小时的情况。
前两种方法与后两种方法相比较为直观，处理起来容易。后两种方法都用到了迭代逼近的思想，过程比较复杂。并且后两方法都将稀疏基涉及了进来，它的前提是稀疏基能够写成矩阵的形式。在实际中这个步骤很难实现，所以在实际操作中后两种的优化方法有一定的局限性。之后的研究除了探究更好的优化算法之外，会进一步探讨稀疏基的构造与矩阵表示。

参考文献
[1] D． Donoho，Compressed sensing［J］.IEEE Transactionson Information Theory，2006， 52( 4) : 1289- 1306．
[2] ABOLUHASEMI J D, SANEI S. A robust approach for optimization of the measurement matrix in compressed sensing [C].international Workshop on Cognitive information Processing, Italy, 2010:388一392
[3] Caiyun Wang, Jing Xu. An Improved Optimization Method of MeasurementMatrix for Compressed Sensing [C]. Antennas and Propagation Society International Symposium (APSURSI),America, 2014 :155-156
[4] 李小波，基于压缩感知的测量矩阵研究[D].北京：北京交通大学，2010:15-20
[5] 傅迎华，可压缩传感重构算法与近似QR分解[J].计算机应用,2008,28(9):2300-2302
[6] 吴赟，压缩感知测量矩阵的研究[D].西安：西安电子科技大学，2012:11-14
[7] 田香玲,席志红, 压缩感知观测矩阵的优化算法[J].电子科技,2015,28(8):102-105
[8] 赵瑞珍,秦周,胡绍海，一种基于特征值分解的测量矩阵优化方法[J].信号处理,2012,28(5):654-657
[9] 王红梅,严军,牛涛,张之江, 一种利用相关性优化压缩感知测量矩阵的方法[J].电子测量技术,2012,35(11):116-119
[10] 李浩，用于压缩感知的确定性测量矩阵研究[D].北京：北京交通大学，2011:7-16