矩阵填充的可行方向逼近法.pdf
《矩阵填充的可行方向逼近法.pdf》由会员分享,可在线阅读,更多相关《矩阵填充的可行方向逼近法.pdf(5页珍藏版)》请在咨信网上搜索。
1、第 卷第期 年月太 原 师 范 学 院 学 报(自然科学版)J OUR NA LO FT A I YUANNO RMA LUN I V E R S I T Y(N a t u r a lS c i e n c eE d i t i o n)V o l N o M a r 收稿日期:基金项目:陆军工程大学基础部励志基金(J B L Z J J )作者简介:李晓丽(),女,山西大同人,硕士,陆军工程大学基础部基础数学教研室助教,主要从事数值代数和数值优化的研究通信作者:王川龙,教授,E m a i l:c l w a n g c o m矩阵填充的可行方向逼近法李晓丽,周华任,王川龙(陆军工程大学
2、基础部基础数学教研室,江苏 南京 ;太原师范学院 数学与统计学院,山西 晋中 )摘要以矩阵填充的子空间逼近法为基础,提出了一种矩阵填充的可行方向逼近法,该算法运用二次规划技术产生最接近可行的矩阵,且迭代矩阵逐步向低秩可行矩阵逼近,满足收敛条件产生低秩的最优填充矩阵通过数值实验验证了新的算法比传统算法更有效 关键词矩阵填充;可行方向逼近;子空间逼近;二次规划;可行矩阵 文章编号 ()中图分类号O 文献标识码A 引言矩阵填充问题是近几年的研究热点之一,首先是由C a n d s和R e c h t提出的,主要讨论的是如何在已知采样矩阵部分元素的前提下,合理精确地填充一个低秩矩阵著名的N e t f
3、 l i x推荐系统就是矩阵填充的一个典型例子同样在机器学习、控制、图像恢复、计算机视觉等信息科学领域矩阵填充都发挥着重要作用在数学上,可以用如下的优化问题来求解矩阵填充问题:m i nr(A)s t Xi jMi j,(i,j)()上述问题为非凸规划,C a n d s和R e c h t在 中提出大部分的秩为r的低秩矩阵是可以通过求解下面的凸优化问题来实现矩阵填充:m i nXs t Xi jMi j,(i,j)()其中核范数Xrkk(X),k(X)是矩阵XRnn的第k大的奇异值,MRnn,并且Mi j:(i,j)已知,是已知元素的下标集合目前为解决核范数极小化问题,已经拥有大量的快速算法
4、 F a z e l,首先提出了半正定规划算法,通过半正定规划程序求解优化问题 T o h等人提出了加速近似梯度法(简称A P G),接着M a和G o l d f a r d将近似奇异值分解技术应用在不动点延续算法(简称F P C),提出了F P C A算法与此同时,还有奇异值阈值算法(简称S VT)、增广拉格朗日算法(简称A LM)、不经过奇异值分解的快速奇异值阈值法(简称F a s t S VT)以及加速奇异值阈值法(简称A S VT)等本文是针对()问题进行求解对于()的求解,W a n g等人提出秩正交匹配法,但该方法每步仅修正秩,且运用了可行逼近求参数的二次规划法,因此该方法较为耗
5、时本文提出的可行方向逼近法是通过可行解中子空间维数的下降来达到最优解该算法与传统算法相比一定是低秩的通过与A LM算法比较发现,新算法的迭代次数少,收敛速度快 结构和记号本文的结构:第节简单的介绍矩阵填充的可行方向逼近法;第节通过数值实验验证算法的有效性,并通过与A LM算法比较验证某些特殊情况下算法的精确性;第节概括性的总结全文相关符号:Rmn表示mn实矩阵全体X(i,j)表示矩阵X的第i行第j列的元素 X表示矩阵X的核范数,XF表示矩阵X的F r o b e n i u s范数X表示矩阵X的转置 v e c(X)表示矩阵X的向量表示形式,集合,n,n 表示采样矩阵已知元素的下标集合,集合是
6、集合的补集 是集合上的正交投影,满足:(X)X,(i,j),(i,j)()为了方便,用Uk,k,Vkl a n s v d(Yk)表示矩阵基于L a n c z o s方法的奇异值分解,其中kd i a g(k,krk),kkkrkUk,Vk为矩阵Yk的前rk个奇异向量构成的矩阵 算法在本节,主要研究矩阵填充问题的可行方向逼近法本文解决的矩阵填充问题描述为如下的优化问题:m i nr(X)s t (X)(M)()其中X、MRnn,n,n算法:矩阵填充的可行方向逼近法(简称F D AM)第一步:给定下标集合,令,n,n,样本矩阵D(M),且向量v e c(D)D(i,j),其中(i,j),参数(
7、N),c(c)误差,给定初始矩阵YD且k:;第二步:计算矩阵Yk的S V D:Uk,k,Vkl a n s v d(Yk);第三步:解如下的两个优化问题,通过比较得到最优的Yk,m i nv e c(D)v e c(UkXk)Fm i nv e c(D)v e c(XkVk)F若v e c(D)v e c(UkXk)Fv e c(D)v e c(XkVk)F,则YkUkXk;否则,YkXkVk;第四步:若YkYkFDF,则终止迭代;否则转第五步;第五步:当k时,若v e c(D)v e c(Yk)(i,j)Fv e c(D)v e c(Yk)(i,j)F,则不变;转第六步;否则,c;转第二步;
8、第六步:k:k;转第二步 数值试验通过数值实验,对F D AM算法和A LM算法进行比较,算法结果见表 所有的数值实验均是在相同的工作环境下进行的其中本文中的算法的参数,终止条件,常数c 对于A LM算法中参数的选取均采用文献 中的建议表 中,m表示观察到的元素个数表算法F D AM与A LM比较s i z e(n)r a n k(r)a l g o r i t h m i t e rt i m e s(s)t(S V D)(s)YMF/MFm/(nn)F D AM e A LM e F D AM e A LM e F D AM e A LM e 太 原 师 范 学 院 学 报(自然科学版)第
9、 卷续表s i z e(n)r a n k(r)a l g o r i t h m i t e rt i m e s(s)t(S V D)(s)YMF/MFm/(nn)F D AM e A LM e F D AM e A LM e F D AM e A LM e 注:算法F D AM和A LM对相同的均值为、方差为的数据矩阵进行填充表算法F D AM与A LM比较s i z e(n)r a n k(r)a l g o r i t h m i t e rt i m e s(s)t(S V D)(s)YMF/MFm/(nn)F D AM E A LM E F D AM E A LM E F D A
10、M E A LM E F D AM E A LM E F D AM E A LM E F D AM E A LM E 注:算法F D AM和A LM对相同的均值为、方差为 的数据矩阵进行填充表算法F D AM与A LM比较s i z e(n)r a n k(r)a l g o r i t h m i t e rt i m e s(s)t(S V D)(s)YMF/MFm/(nn)F D AM e A LM e F D AM e A LM e F D AM e A LM e F D AM e A LM e F D AM e A LM e F D AM e A LM e 注:算法F D AM和A
11、LM对相同的均值为、方差为 的数据矩阵进行填充第期李晓丽,等:矩阵填充的可行方向逼近法表算法F D AM与A LM比较s i z e(n)r a n k(r)a l g o r i t h m i t e rt i m e s(s)t(S V D)(s)YMF/MFm/(nn)F D AM e A LM e F D AM e A LM e F D AM e A LM e F D AM e A LM e F D AM e A LM e F D AM e A LM e 注:算法F D AM和A LM对相同的均值为、方差为的数据矩阵进行填充表 对不同正态分布和均匀分布产生的不同抽样率样本矩阵填充问题
12、,展示了F D AM算法和A LM算法的迭代次数、计算时间和精度,通过对比,显示出了F D AM算法的有效性 总结本文提出了一种新的矩阵填充的可行方向逼近法,简称F D AM该算法以子空间逼近法为基础,采用二次规划技术获得最优的可行矩阵与A LM算法相比,F D AM算法有更好的收敛性以及更高的精确度由表 中数据可以看出F D AM算法的迭代次数少,收敛速度快同时,由表中的数据还可以看出,F D AM算法采用的二次规划技术在迭代过程中占用大部分时间,因此希望能够采用其他技术对此进行改进,来降低算法的复杂度,从而减少C P U时间,获得更快更精确更有效的算法,这将是未来研究的重点参考文献:C A
13、N D SEJ,R E C HTB E x a c tm a t r i xc o m p l e t i o nv i ac o n v e xo p t i m i z a t i o nJ F o u n d a t i o n so fC o m p u t a t i o n a lM a t h e m a t i c s,():B E N N E T TJ,L A N N I N GS T h eN e t f l i xp r i z eCP r o c e e d i n g so fK D DC u pa n dW o r k s h o p S a nJ o s e:A
14、CM,:A R G Y R I OU A,E V G E N I OUT,P ON T I LM M u l t i t a s k f e a t u r e l e a r n i n gCP r o c e e d i n g so f t h e t h I n t e r n a t i o n a lC o n f e r e n c eo nN e u r a l I n f o r m a t i o nP r o c e s s i n gS y s t e m s C a m b r i d g e:M I TP r e s s,:ME S B AH IM,P A P AV
15、A S S I L O P OU L O SGP O nt h er a n km i n i m i z a t i o np r o b l e mo v e rap o s i t i v es e m i d e f i n i t e l i n e a rm a t r i xi n e q u a l i t yJ I E E ET r a n s a c t i o n so nA u t o m a t i cC o n t r o l,():B E R T A LM I O M,S A P I R OG,C A S E L L E SV,e ta l I m a g e i
16、 n p a i n t i n gCP r o c e e d i n g so f t h e t hA n n u a lC o n f e r e n c eo nC o m p u t e rG r a p h i c sa n dI n t e r a c t i v eT e c h n i q u e s N e wY o r k:A CMP r e s s,:T OMA S IC,KANA D ET S h a p e a n dm o t i o n f r o mi m a g e s t r e a m su n d e r o r t h o g r a p h y:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 矩阵 填充 可行 方向 逼近
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。