《稀疏随机矩阵有限等距性质分析》由会员分享，可在线阅读，更多相关《稀疏随机矩阵有限等距性质分析（6页珍藏版）》请在金锄头文库上搜索。
1、第36卷第1期 电 子 与 信 息 学 报 Vol.36 No.1 2014年1月 Journal of Electronics then it is proved that sparse random matrices satisfy RIP with high probability provided the numbers of measurements satisfy certain conditions. Simulation results show that sparse random matrices can guarantee accurate reconstruction
2、of original signal, while greatly reduce the time of measuring and reconstruction. Key words: Compressed Sensing (CS); Sparse random matrix; Restricted Isometry Property (RIP); Measurement matrix 1 引 言 压缩感知1 5(Compressed Sensing, CS)是一种 全新的数据获取和采样理论。该理论指出：如果信 号是稀疏的或者在某个变换域是稀疏的，则可用一 个测量矩阵将该信号投影到低维空间，
3、投影后的低 维信号包含了重构原始信号的全部信息，通过求解 一个优化问题就可以从这些少量的投影中精确重构 出原始信号。 测量矩阵设计是CS理论的一个重要研究方向。 为保证信号在投影过程中不丢失信息，测量矩阵应2013-01-8 收到，2013-10-21 改回 教育部新世纪优秀人才支持计划(NCET-10-0873)，重庆市自然科学基金重点项目(CSTC2011BA2016)，重庆高校创新团队建设计划(KJTD201343)和重庆市基础与前沿研究计划项目(cstc2013jcyjA 40045)资助课题 *通信作者：张波 满足一定性质。文献2证明了测量矩阵满足有限等 距性质(Restricte
4、d Isometry Property, RIP)是完全 重构稀疏信号的充分条件，并指出稠密高斯随机矩 阵可以作为普适的测量矩阵。后续研究以减少精确 重构原始信号所需的测量值个数为目标，构建了部 分傅里叶矩阵3，Toeplitz矩阵6等性能优异的稠密 测量矩阵。然而，文献7指出，采用传统的稠密测 量矩阵作为网络数据收集的测量矩阵会带来密集观 测问题，即每个测量值的获取均需要所有节点参与 运算8。 由于每个测量值均由密集观测得到， 因此测 量值的获取需要极大的通信开销，且进行重建时计 算量巨大。为避免密集观测问题，文献9提出用稀 疏随机矩阵作为测量矩阵对网络数据进行测量，该 方法计算测量值只需部
5、分节点参与，显著减少了获 取测量值的通信开销，极大地推动了CS在无线传感 器网络(Wireless Sensor Networks, WSNs)中的应 用。除此之外，稀疏随机矩阵在图像处理、遥感成170 电 子 与 信 息 学 报 第 36 卷 像、雷达探测、数据流计算等领域都具有巨大的应 用潜力，引起了广泛关注9 12。 现有文献缺乏对稀疏随机矩阵 RIP 的证明，本 文则给出了其严格证明。首先，证明了测量矩阵满 足 RIP 等价于其子矩阵的格拉姆矩阵特征值分布位 于1,1kk+范围内，将矩阵满足 RIP 的证明问 题转化为格拉姆矩阵特征值分布范围的讨论问题； 然后，证明当测量值个数满足特定
6、条件时，格拉姆 矩阵特征值以接近 1 的概率位于1,1kk+范围 内，从而证明稀疏随机矩阵满足 RIP。 2 基本理论 2.1 压缩感知 CS 的基本思想是利用稀疏信号的少量投影值 重构原始信号。考虑一个长度为n、稀疏度为 ()k kn+G A， 根 据 引 理 1 ， 当max()( ()TT=G A zG Az时，有 ()HHmaxH(1)TT Tk=+z A A zG Az z(9) 即存在一个kRz满足： ()()22222max2(1)TTk=+A zG Azz (10) 这与 RIP 的定义相矛盾，故假设不成立，即max( ()1TkG A 1k。即()TG A的所有特征值均位于1
7、,1kk+ 范围内。 证毕 第 1 期 张 波等： 稀疏随机矩阵有限等距性质分析 171 4 稀疏随机矩阵有限等距性质分析 根据定理 1 可知，要证明一个矩阵以参数k满 足k阶 RIP，只需证明该矩阵任意抽取k列构成子 矩 阵 的 格 拉 姆 矩 阵 的 所 有 特 征 值 均 位 于1,1kk+。在经典的特征分析中，圆盘定理对 矩阵的特征值范围作出了估计。 引理 2 (Gersgorin 圆盘定理) 矩阵u uM的 特 征 值 分 布 于u个 圆 盘(),iiiidd c r=的 并 集 ()1,uiii id c r=中，其中1,2,iu=?，圆盘的圆心ic = , i iM，半径,1u
8、ii jjjir=M，其中, i iM和, i jM分 别是矩阵M的对角线元素和非对角线元素。 矩阵A任意抽取k列构成的子矩阵TA共有k nC 个，要依次证明每个子矩阵格拉姆矩阵的特征值分 布位于1,1kk+是一个组合复杂度问题，因此， 本文将证明所有子矩阵格拉姆矩阵的特征值同时位 于1,1kk+范围。矩阵A的格拉姆矩阵( )G A包 含了所有子矩阵格拉姆矩阵的特征值分布信息，为 证明所有子矩阵的格拉姆矩阵的特征值分布均位于 1,1kk+范围，可适当选取,0do , do+ (0,1)k=，如果( )G A的各对角元素, i iG满足,|1|i idG，各非对角元素,()i jijG满足,|i
9、 jG 1|/ok， 即各 Gersgorin 圆盘的圆心与 1 之间的距 离不超过d，各圆盘的半径不超过o，根据引理 2 即可证明()TG A的所有特征值分布位于1,k 1k+范围。如果矩阵A的非零元素独立同分布于 高斯分布， 则( )G A的各对角元素为高斯变量的平方 和，各非对角元素为独立高斯变量的乘积之和，对 角元素和非对角元素的取值范围可由以下引理确 定。 引理 3 设序列1 niix=中仅有n个非零元素，并且非零元素服从均值为 0，方差为1/()n的高斯分布，那么 2 21Pr12exp16n d id inx=(11) Pr表示事件发生的概率。 证明 首先考虑序列1 niiz=，
10、其中各元素独立同分布于均值为 0，方差为2的高斯分布，对01t，由文献6可知 2221Pr42exp()ni iznntt=(12) 2 1n iix=为序列1 niix=各元素的平方和， 加法具 有交换性， 因此可通过交换元素顺序将n个非零元素交换到前n项，那么有 2211nnii iixx=(13) 将式(13)和非零元素方差1/()n代入式(12)可 得 214Pr12exp()ni ixn ttn =(14) 令4 dn tn=，代入式(14)可得 2 21Pr12exp16n d id inx=(15) 证毕 引理 4 设序列1 niix=和1 niiy=中仅有n个非 零元素， 并且
11、非零元素服从均值为 0， 方差为1/()n 的高斯分布，那么 21Pr2exp42nii in tx ytt=+(16) 证明 首先考虑1 niiz=和1 niir=， 其中各元素独 立同分布于均值为 0，方差为2的高斯分布，则由 文献6可知 222 1Pr2exp4(2)ni i itz rtnt=+(17) 设序列1 niix=和1 niiy=非零元素的混叠长度为 l(显然ln)，那么1n iiix y=只有l项非零，加法 具有交换性，将l个非零元素交换到前l项，那么有 11nliiii iix yx y=(18) 将式(18)和非零元素方差1/()n代入式(17)有1122 22PrPr
12、2exp2exp4242nliiii iix ytx ytntn t ln tt =+(19) 证毕 借助以上引理可证明稀疏随机矩阵满足有限等 距性质。 定理 2 设A为一个mn维， 稀疏率等于的 稀疏随机矩阵， 且非零元素独立同分布于均值为零， 方差为1/()m的高斯分布。那么对任意(0,1)k ， 存在常数1c和2c(由k决定)， 使得当2 2(log )mc kn /时，稀疏随机矩阵A以不小于11exp(c m 2/)k的概率满足k阶 RIP 性质。 证明 记,(1,2,1,2, )i jim jn=A?为A的 第( , )i j元素，那么( )G A的对角线元素可表示为 172 电 子
13、 与 信 息 学 报 第 36 卷 2 ,1m i ijij=GA，由引理 3 可知 ()2,Pr12exp16d i idmG (20) 则所有的, i iG满足 2, 1Pr12 exp16n d i id imn=G(21) ( )G A的非对角线元素可表示为,1=m i jrir=GA rjA，由引理 4 可知 ()2,Pr2exp42i jm ttt+G (22) 将t用ok替换可得 2,2Pr2exp42oo i j om kkk +G (23) ( )G A的非对角线元素具有对称性， 互不相同的非对角元素总共有(1)/2n n个，则所有,i jG联合概率分布满足 2 2 ,2 11Prexp42nn oo i j ijo jimnkkk = +G(24) 记P为稀疏随机矩阵满足 RIP 的概率，假设(2/3)dk=, (1/3)ok=及2n ，由式(21)和式(24)可知 , 11122 22 22=Pr1+Pr2exp2exp36642nnn o
