基于奇异值分解的压缩感知观测矩阵优化算法-李周.pdf
《基于奇异值分解的压缩感知观测矩阵优化算法-李周.pdf》由会员分享,可在线阅读,更多相关《基于奇异值分解的压缩感知观测矩阵优化算法-李周.pdf(5页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、Journal of Computer Applications计算机应用,2018,38(2):568572ISSN 10019081CODEN JYIIDU20180210http:wwwjocacn文章编号:10019081(2018)02056805 DOI:1011772jissn1001-90812017071854基于奇异值分解的压缩感知观测矩阵优化算法李周,崔琛(国防科技大学电子对抗学院,合肥230037)(通信作者电子邮箱17756587331163conl)摘要:针对压缩感知(CS)中从优化后的Gram矩阵求解观测矩阵时会出现较大相关系数的问题,在利用现有算法得到优化后的G
2、ram矩阵的基础上,通过求解等价变换后的目标函数对观测矩阵行向量的导数得到目标函数取极值时行向量的值,并通过对误差矩阵进行奇异值分解(SVD)在上述行向量的值中选出使得目标函数取最值时行向量的解析式,在此基础上给出了观测矩阵的优化算法:通过借鉴K-SVD算法中逐行优化目标矩阵的思想,对观测矩阵进行逐行迭代优化,并将相邻两轮迭代产生的观测矩阵所对应的相关性之差作为衡量迭代是否结束的条件。仿真结果表明:该算法在观测矩阵与稀疏基的相关性方面优于改进前的算法,从而提高了重构精度。关键词:压缩感知;观测矩阵;奇异值分解;行向量解析式;迭代优化中图分类号:TNgll7 文献标志码:AObservation
3、 matrix optimization algoritlun in compressivesensing based on singular value decompositionLI ZhouCUI Chen(Institute of E如ctronw Engineering,National University of Defense Technology,Hefei Anhui 230037,China)Abstract:In order to solve the problem of large correlation coefficients when obtaining the
4、observation matrix from theoptimized Gram matrix in Compressive Sensing(CS),based on the optimized Gram matrix obtained in the existing algorithm,the value of the roW vector in the observation matrix when the objective function takes the extreme value Was obtained based onthe extreme value of the eq
5、uivalent transformation of the objective function,the analytic formula of the rOW vector when theobjective function takes the extreme value Was elected from the values mentioned above by Singular Value Decomposition(SVD)of the error matrix,then a new observation matrix optimization algorithm Was put
6、 forward by using the idea ofoptimizing the target matrix roW by lOW in the K-SVD algorithm,the observation matrix Was optimized iteratively roW by row,and the difference between the correlations of the observation matrix generated by adjacent two iterations Was taken as ameasure of whether or not t
7、he iteration is completedSimulation results show that the relevance between the observation matrixand the sparse base in the improved algorithm is better than that in the original algorithm,thus reducing the reconstructionelTorKey words:Compressive Sensing(CS);observation matrix;Singular Value Decom
8、position(SVD);analytic formula oflOW vector;iterative optimization0 引言压缩感知(Compressive Sensing,cs)L1-3j在采样率远小于奈奎斯特采样率的条件下获取信号的离散样本,然后通过非线性优化算法重构出原始信号。重构信号所需的采样率并不取决于信号的带宽,而与信号的稀疏度密切相关,因此CS有效降低了信号获取、存储及传输的代价,引起了越来越多学者的关注。信号的稀疏表示、观测矩阵的构造、重构算法是cs理论中三个主要研究方向,其中观测矩阵是影响压缩感知性能的关键因素之一【4 J。观测矩阵构造的目的是如何采样得到观测
9、值,并能从观测值中重构出原始信号。文献57对精确重构所需观测矩阵的约束条件进行了研究:文献5提出了零空间性质(Null Space Property,NSP),但在存在噪声的情况下NSP并不能保证信号的精确重构;文献6提出了有限等距性质(Restricted Isometry Property,RIP),但判断观测矩阵是否符合瞰P需要计算观测矩阵t列中任意组合的K列,即需要计算观测矩阵各列的组合,实际用于观测矩阵的分析非常困难;文献7提出了相关性的概念,其含义是观测矩阵与稀疏基之间的相关程度,通过降低相关性可以减少cs的重构误差和精确重构原始信号所需的观测数。文献7通过线性收缩Gram矩阵中绝
10、对值大于限定阈值的非对角元来降低相关性,取得了较好的实验效果。但是,该算法在收缩Gram矩阵时会改变矩阵的秩哺。90;同时在求解观测矩阵时需要求解稀疏基的逆矩阵,但由于稀疏基可能奇异,此时需要利用稀疏基的MoorePenrose广义伪逆来求解新的观测矩阵,造成了算法中计算量大且精度受限的问题48。文献9延续了文献7之前的思路,不同之处在于增加了一收稿日期:2017-0731;修回日期:2017-09-12。作者简介:李周(1993一),男,河北邱县人,硕士研究生,主要研究方向:压缩感知、计算机软件;崔琛(1962一),男,河北易县人,教授,硕士,主要研究方向:无线传感网络、软件工程、可视计算。
11、万方数据第2期 李周等:基于奇异值分解的压缩感知观测矩阵优化算法个保留前一次矩阵优化信息的操作,其目的在于使每一次矩阵更新的变化量减少,该算法继承了文献7的缺点,同时需要根据经验手动设置一个权重系数,用来衡量本次矩阵优化结果与前一次矩阵优化结果之间的比重。文献10提出将Gram矩阵非对角元素的平方和作为整体互相关系数,用来表示观测矩阵的整体性能;在此基础上,文献11引入了d紧框架的概念,平均化Gram矩阵的非零特征值,减小了整体相关系数。但在由Gram矩阵求解观测矩阵时,文献1011仍采用了求稀疏基MoorePenrose广义伪逆矩阵的做法,同样造成了算法中计算量大且精度受限的问题。针对现有算
12、法从优化后的Gram矩阵求解观测矩阵时出现的相关系数较大与需要求广义伪逆矩阵的问题,本文借鉴了K-SVD(K-Singular Value Decomposition)算法中逐行更新优化目标矩阵的思想,在利用现有算法得到优化后的Gram矩阵的基础上,提出了一种基于奇异值分解(Singular ValueDecomposition,SVD)的观测矩阵优化算法:该算法通过求解等价变换后的目标函数对观测矩阵行向量的导数得到目标函数取极值时行向量的值,并通过对误差矩阵进行奇异值分解在上述行向量的值中选出使得目标函数取最值时行向量的解析式,之后在每轮迭代中对观测矩阵的每一行分别使用上述的行向量解析式进行
13、优化。1 观测矩阵相关性和相应算法11观测矩阵相关性假定离散信号,R“6,若,中最多含有K个非零值且Kh,那么,就称作群稀疏的。将忌稀疏的信号集合记为:A。=rl”Il。K (1)若,本身为非稀疏的,但可以经过一个稀疏基缈作如下变换:,=qts (2)如果变换后的S符合忪忆Kh,即,可以用已知的稀疏基中少量的元素线性表示,那么r也被称作忌稀疏的。CS理论的测量过程可以表示为:Y=咖,=痧妒s=Xs (3)其中:,为原始信号,妒R“为稀疏基,s为变换后的稀疏信号,西R“为观测矩阵,X垒咖妒称为感知矩阵。由于mn,所以无法根据y直接求解出,。但由于s是稀疏的,故可以利用一系列重构算法得到s的估计值
14、;,进而可得到原始信号的估计;。对于任意两个不同的稀疏信号,。,r2A。,必须满足Xr,Xr2,否则仅仅根据观测值无法区分r,2,因此感知矩阵需要满足一定的条件:对于任意船稀疏的信号,只要其稀疏度K满足下式,信号即可准确地恢复出来“。Kt,i (7)12观测矩阵优化的相关算法及问题分析为降低x任意两列的相关性,即减少Gram矩阵非对角元素的值,文献7采用如下阈值函数对Gram矩阵G中绝对值大于限定阈值的非对角元进行线性收缩: fTg口, l驯岛=ytsign(g#),tI gIyt (8)【g ytfgf其中:t为阈值,7为收缩因子。Gram矩阵G经过阈值函数后的矩阵e的秩不再是m,通过取矩阵
15、G的奇异值分解式中对角阵的m个元素将G的秩收缩为m,但改变矩阵秩的收缩操作可能会引入原有Gram矩阵中没有的较大非对角元哺9。之后对e使用如下式所示的相似对角化得到A,使得e=A1A。e=pTAP=P7(Af)AlP=A7A (9)其中:A=中蟹气在妒逆矩阵存在时,咖=A矿1;但在稀疏基妒可能奇异导致其逆矩阵不存在时,需要利用稀疏基的MoorePenrose广义伪逆来求解观测矩阵垂=Aqr,从而带来计算量与精度的问题H8 J。文献6的阈值函数只能使局部比较大的非对角元素减小。为整体减小Gram矩阵中的非对角元素,文献11通过平均化Gram矩阵的非零特征值,使得矩阵非零特征值的平方和减小,降低了
16、整体相关系数。但在由Gram矩阵求解观测矩阵时,仍然需要求解稀疏基的广义逆矩阵,故存在着与文献7相同的问题148 J。13问题的解决思路在现有算法优化Gram矩阵后,本文借鉴了文献13提出的K-SND算法中逐行优化目标矩阵的思想从优化后的Gram矩阵求解观测矩阵。K-SVD是一种通过逐行优化字典矩阵对信号进行稀疏表示的方法,具体目标为:m。in Il yDX II 2F (10)其中:y为要表示的信号,D为所求的字典,x为稀疏矩阵。x与y按列对应,表示|D中的元素以t为系数线性组合就可得到y,而K-SVD的目的是在x和y已知的情况下更新字典D满足上述条件。ll YDX雌2=II y一哆一睢2=
17、I|y一哆F一噍工跏2,=I|E;一dk工跏2,(11)式(11)可以看作把第k个分量剥离后表达式会产生空洞,目的是找到一个新向量以更好地填补这个洞:假设除第k项外其余项是固定的,之后对巨进行奇异值分解得到E。=万方数据570 计算机应用 第38卷UA矿,其中夥和y的列矢量均是正交基,A是对角矩阵。若A的对角元素从大到小排列,则表示臣的能量分量主轴在相应几个正交方向上由大到小分配。取,的第一个列向量来表示d;,取y的第一个列向量与以的第一个元素的乘积表示,至此完成了字典一个条目的更新。2观测矩阵的优化算法在利用现有算法得到优化后的Gram矩阵的基础上,借鉴K-SVD算法中逐行更新优化目标矩阵的
18、思想,本章利用稀疏基的奇异值分解对目标函数进行等价变换,通过求解等价变换后的目标函数对观测矩阵行向量的导数得到目标函数取极值时行向量的值,并通过对误差矩阵进行奇异值分解在上述行向量的值中选出使得目标函数取最值时行向量的解析式,最后利用所求出的行向量解析式逐行迭代优化观测矩阵。21观测矩阵行向量的优化在得到优化后的Gram矩阵舀后,观测矩阵优化的目标函数143如下:m巾in 0 8一矿矿痧驯2F (12)假设稀疏基缈的秩为N,其奇异值分解为:妒川(:)(13)将奇异值分解式代入目标函数中,可得:II吞一矿矿咖妒雌2=II 8一(:)c,1矿伽,(?:)K旺(14)根据F范数的酉不变性,在式(14
19、)中左乘k,右乘,同时设础,垒面=(11 12),其中Il为面的前N,列。设召。=y,召y,=(三;三茎),其中召:1为E的前,行与前0列,将面和8。代入式(14)可得:If舀一矿矿西妒雌2=11慨一(三)c面魂,(:)11:=瞄12(晒抓 ,由式(15)易得:吧n怕一矿矿圣妒虬2甘呼lIG:11型譬=一4(弓一呜畔7)畔 (19)导数置0便可得到一系列极值点:型苌烈竖=o铮弓哆=o哆ii 2q (20)由式(20)可得畔为目的特征向量,Il q峨为弓的特征值,又因弓为对称阵,故弓奇异值分解为:弓=吼q“=A每弘每p每7,其中A=diag(AIj,A,A融)且A如A可,所以呜=A#p茸(后=l
20、,2,J、r)。易得:唧。弓一哆呼7雌2甘-t毕哆叼7 (21)当吩哆=A每p目取最大值时,lI弓一叶叶7雌2取最小值,此时相应的J所对应的畔=A茸p茸即为所求。在得到n后,利用式(22)可得观测矩阵西,其中12与目标函数的取值没有任何关系,故或取初始值即可。咖=(仍,-1 磊),-1 (22)22观测矩阵的迭代优化算法在现有算法得到优化后的Gram矩阵的基础上,本小节利用21节求出的观测矩阵行向量的解析式,采用逐行更新的方法优化观测矩阵。输入初始观测矩阵咖R”8,离散傅里叶变换基妒ER“,迭代次数her,退出阈值Po;输出观测矩阵。fork=1:her1)将初始的Gram矩阵G=蟹尹4T咖妒
21、经文献11中的方法优化后得到Gmm矩阵石2)fj吖=1:m计算弓=G:1一蛾t151I,求取弓的奇异值分解,得到弓=q=A#弘与弘目计算A茸弘茸7p|;最大时的取值,得到q=石pHendfor3)咖=(aS,_1 12)U,-14)计算,若p。与上一轮迭代的以。之差小于则退出循环,否则转至1)继续循环endfors,西11西lS,ll;,3 实验结果及其分析(16) 。一设=s西7=(。,她,),则:0 G;1一s面。面。S,0;=II G:l-n7以惦2=|G:l一善州i忙2 (17)在XtO;gO。7中剥离n矩阵的第-行哆,此时脚iOJi7中会产生一个“空洞”,优化目的是寻找新的鳞来填补这
22、个“空洞”使得式(17)取最小值:一一X川O)itOi7沪懈一;暑蛾一哆呜1卜lI弓一哆q1噼=11 w孵 (18)式(18)对岫求导可得:本文在Madab平台上对算法进行仿真实验,仿真选择高斯随机矩阵作为初始观测矩阵,离散傅里叶变换基作为稀疏基,比较文献7所提的算法cs。小文献11所提的算法CS和经文献11中的方法优化Gram矩阵后使用本文所提的算法CSh,扪、ilig。;在相关性、重构误差和运行时间三方面的性能。仿真中相关参数如下:m=30,n=z=100,稀疏度K=10,迭代次数her=100。Gram矩阵收缩变换时非对角线的限定阈值t=30,收缩因子y=05,CS蛳。im嘶“的退出阈值
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 奇异 分解 压缩 感知 观测 矩阵 优化 算法 李周
限制150内