荣耀彩票代理

  • 热门专题

研究领域总结(二):稀疏矩阵补全

作者:aezero  发布日期:2015-10-08 21:12:48
  • I.定义

      JUZHENBUQUAN(Matrix Completion)SHIZHIRUXIAYIGEWENTI: YOUYIGEJUDADEJUZHEN$X\in\mathbb{R}^{m\times n}$,RANERRENMENZHINENGGUANCEDAOQIZHONGDEBUFENYUANSU。JIGUANCEDAODEJUZHENWEIJUZHEN$M\in\mathbb{R}^{m\times n}$(MEIGUANCEDAODEYUANSUWEIZHIYI$0$TIANCHONG),ZE$P_\Omega(X)=P_\Omega(M)$,QIZHONGGUANCEDAODEYUANSUXIABIAOJIHEJIWEI$\Omega$,$P_\Omega$BIAOSHITOUYINGDAO$\Omega$。

      WEILESHUOMINGTADEYIYI,ZHEILIJUYIGEZUICHANGJIANDEQINGXING,JIPINGFENYUCE/TUIJIANXITONG——XIETONGGUOLV,RUDOUBANZHILEIDEWANGZHAN,HUIYOUHENDUOYONGHU(KANZUOXING)DUIHENDUODIANYING(KANZUOLIE)JINXINGDAFEN(JUZHENYUANSUDEZHI),MEIGEYONGHUZHIHUIDUIHENSHAODEDIANYINGDAFEN,ZHEIJIUDAOZHIWOMENDEDAFENJUZHENSHIYIGEBUFENGUANCEDAODEJUZHEN,ERWANGWANGWOMENXIANGYUCECHULAIYONGHUDUIMEIYOUDAFENDEDIANYINGDEPINGFEN,YICILAITUIJIANHUOWAJUEDENGDENG。TONGSHIZHUYIDAOXINGSHUHELIESHUWANGWANGFEICHANGFEICHANGDA(>BAIWANJIBIE),BINGQIEJUZHENDEXISHUDUKENENGHENGAOHENGAO(<0.x%)。

    荣耀彩票代理  XIANRANZHEIGEWENTISHIGEBUSHIDINGWENTI,XIANGYAOBUQUANZHENGGEJUZHEN,WOMENXUYAOYIXIEEWAIDEYUESHU,ZUICHANGJIANDEJIUSHIJIASHEZHEIGEJUZHENSHIDIZHIDE,YIFANGMIANZHEIFUHEWOMENDUIZIRANJIEDEGUANCE,LINGYIFANGMIANKEYIYONG“WUYILEIJU,RENYIQUNFEN”DEYIZHIXINGLAIZUOZHIJUEJIESHI。KAOLVGUANCEYOUZAOSHENGDEQINGKUANG,ZEZHENGGEWENTIKEYIXINGSHIHUAWEI:

    \[ \min_{X}\|P_\Omega(X-M)\|_F^2 \quad s.t. rank(X)\leq k. \]

    II.求解:化归到稀疏问题 

    荣耀彩票代理  rankSHIGEHENNANGAODEDONGXI,ERQIEBAZHENGGEWENTIBIANCHENGFEITUDELE。BA$X$DEQIYIZHIBIAOSHICHENGXIANGLIANGXINGSHI$\sigma$,NEIMEGENJUSVDFENJIEDEXINGZHI,$rank(X)\leq k$DENGJIAYU $\|\sigma\|_0\leq k$。ZHEIYANG,JIUHUAGUIDAOLEXISHUWENTISHANGLAI,KEYIYONGYASUOGANZHI、XISHUBIANMADESILULAISIKAO,ZHIBUGUOMUBIAOCONGXIANGLIANGTUOZHANDAOLEJUZHEN。

       1.松弛到凸问题。

    荣耀彩票代理  LEISIYASUOGANZHI,WOMENYEKEYIBA$\|\sigma\|_0$SONGCHIDAO$\|\sigma\|_1$,ZHEIYANGJIUBIANCHENGLETUWENTI。TONGSHI,SONGCHIDAO$\|\sigma\|_1$JIJUZHENDENuclear norm  \|X\|_*,WENTIHUAWEI:

    \[ \min_{X}\|P_\Omega(X-M)\|_F^2 +\lambda \|X\|_* \]

    荣耀彩票代理  GUANYUZHEIGEWENTI,YOUHENDUOJIEFA,DABUFENDOUSHICONGXISHULIBIANHUANGUOLAIDE,RUSHOUSUOSUANZI、ADMMDENGDENG。

      Candes证明了矩阵补全和压缩感知一样,在满足矩阵size和采样率(观测稀疏度)要求下,有exact recovery的bound(事实上,矩阵补全的坑就是Candes挖的)。有兴趣的可以读一下他的paper:  E. J. Candès and B. Recht. Exact matrix completion via convex optimization. Found. of Comput. Math.9 717-772

      2.非凸解法。

      TONGYANGDE,SUIRANSONGCHIDAOTUWENTIYOUZUIYOUJIE,YOUbound guarantee,DANSHILUNQISHIJIXIAOGUOWANGWANGFEITUDEYIXIEJIEFAGENGZHUNQUEGENGKUAISU。ZHEIBUFENWOZUODEBIJIAODUO。ZHUYAOLIANGLEI:

  • 类似OMP,可以用贪心方法选基,每次选一个rank one的矩阵,然后更新系数,选k个即能保证矩阵秩小于等于k。注意到一个重要的区别是稀疏里有个字典,也即从一组冗余基里选,而矩阵补全没有这样一个字典,可以从无限个数的基里选,可以用top SVD 或者其它子目标问题求解得到。 非凸惩罚项,比如MCP。

    III.协同过滤、去噪      

      GONGYEJIEDETUIJIANXITONGZUIZHUYAODELIANGGESILUJIUSHIJIYUNEIRONGHEXIETONGGUOLVLIANGZHONG。XIETONGGUOLVGENGstandardDESHIYONGJUZHENFENJIELAIZUO(GERENRENWEIZHUYAOHAISHIJUZHENFENJIEBIBUQUANCHULAIDEZAO,QIANGZHANLESHICHANG),JUZHENFENJIEGENJUYIPIANpaperDEDINGLI(YISHIWANGJICHUCHULE),QISHISHIHENuclear normYUESHUDENGJIADE。QIDAIJUZHENBUQUANZAISHIJIZHONGDEGENGDUOYINGYONG。CIWAI,JUZHENBUQUANYEKEYIYONGLAIZUOTUXIANGQUZAO。

延伸阅读:

About IT165 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规