矩阵补全（matrix completion）的经典算法有哪些？目前比较流行的算法是什么？ - 知乎517被浏览14351分享邀请回答stat.osu.edu/~dmsl/GrandPrize2009_BPC_BellKor.pdf我们先看看什么是matrix completion问题，就用Netflix的dataset来说明。简单来说就是在一个豆瓣电影评分系统做inference，要根据非常稀疏的现有数据集（一个用户可能就只rate了几十部电影）来推断整个用户群对不同电影的评分。见下图，480000 x 18000规模的matrix completion（各位可以算算光存储这个矩阵就需要多少GB）。这个问题在推荐系统、图像处理等方面都有广泛的运用。接着，这类问题一般来说都有隐含的假设即最终的矩阵应该是低秩（low rank）的。这其实也很好理解，因为我们一般会觉得：1、不同用户对于电影的偏好可以分成聚落（cliques），即最多也就是这么几大类的用户，比如按照年龄：年轻人，中年人，老年人...，而电影因为也可以分成不同的题材（genres），战争片，魔幻片，言情片...所以会有low rank的特性。简单来说，就是这个矩阵的行和列会有“合作”的特性，这也是这个问题的别名collaborative filtering得名的原因。另外，low rank限制下的matrix completion也会比较实用，因为一般人都会喜欢稀疏（sparse）的解，这样利于存储且有更好的诠释性。最后则是理论上的意义，更利于reconstruction，这点先隐去不表（下图有几篇paper可以refer）。当然我们注意到，data是会有noise的（有些用户可能会乱填rating...）。这段总结如下图。好了，那么这个问题的数学形式其实非常简洁。Z是我们要complete的矩阵，X则是现有的data（大部分缺失）。我们希望找到一个和X不缺失部分差距尽量小的rank最小的矩阵。好了，那么这个问题的数学形式其实非常简洁。Z是我们要complete的矩阵，X则是现有的data（大部分缺失）。我们希望找到一个和X不缺失部分差距尽量小的rank最小的矩阵。然而问题来了：1、这个问题是非凸的，所以可能有一大堆local minimum因此没有什么现成的efficient的办法（NP-hard, of course）。2、这种问题一般的应用规模都非常大（比如上述的netflix问题规模是10^5 x 10^4），需要考虑很多数值方面的trick才能让算法比较实际。然而问题来了：1、这个问题是非凸的，所以可能有一大堆local minimum因此没有什么现成的efficient的办法（NP-hard, of course）。2、这种问题一般的应用规模都非常大（比如上述的netflix问题规模是10^5 x 10^4），需要考虑很多数值方面的trick才能让算法比较实际。最早人们用一些启发式算法如下图。即局部让user对item做迭代（vote）最后算法收敛到一个局部最优解。矩阵P就是最后的ouput。至于里面那个weight就是见仁见智了，如下图可以取各种，反正是启发式算法...矩阵P就是最后的ouput。至于里面那个weight就是见仁见智了，如下图可以取各种，反正是启发式算法...显然，这些算法虽然很容易实现，但没有理论上的收敛性保证，也没有对rank的考虑，也绝无可能满足像Netflix这种公司对解的精度的需求（对那种规模的问题这些算法的表现可能会惊人的差）。所以，我们需要一些更好的方法。这里我不详述BellKor的解法，因为他的解法实质上是一堆解法的组合。只是指出，他们的方法主要是基于matrix factorization，如下图。显然，这些算法虽然很容易实现，但没有理论上的收敛性保证，也没有对rank的考虑，也绝无可能满足像Netflix这种公司对解的精度的需求（对那种规模的问题这些算法的表现可能会惊人的差）。所以，我们需要一些更好的方法。这里我不详述BellKor的解法，因为他的解法实质上是一堆解法的组合。只是指出，他们的方法主要是基于matrix factorization，如下图。核心想法是把Z作low rank factorization（有一些比较有效的算法，比如regularized SVD，但具体implementation detail水其实很深）然后解这个reformulate之后的优化问题。另外一种方法是对原问题作convex relaxation，即把原问题的目标函数rank(Z)换成Z的nuclear norm（定义不清楚的可查），这个在里有介绍。见下图：()不过我们发现这两种reformulation仍然有太过于rigid或者无法控制noise的缺陷，所以最后简单介绍一下这篇工作： 思路是把那个constraint dualize来做。为了快速解这个问题我们也需要考虑合理利用每步的SVD做很多fast subroutine，具体也不展开。为了快速解这个问题我们也需要考虑合理利用每步的SVD做很多fast subroutine，具体也不展开。哦对了，以上这些图大多是我research advisor课件里的，最后一篇是他当phd时候的一篇很不错的paper...14337 条评论分享收藏感谢收起156 条评论分享收藏感谢收起查看更多回答矩阵补全问题的研究与应用--《中国石油大学(华东)》2014年硕士论文
矩阵补全问题的研究与应用
【摘要】：矩阵补全问题是指通过利用低秩或近似低秩的未知矩阵的部分已知元素恢复出其它未知元素,由于该问题在控制,计算机视觉,网络调查等广泛的应用领域具有重要的价值。近年来,关于该问题的算法和理论均得到了快速的发展,尤其在控制论、人脸识别等视觉应用领域有显著的应用价值,近一段时间有关该问题的求解和理论都得以迅速的开展。在互联网推荐系统上也有很多的应用,比如协同过滤等,其中包括著名的网飞问题(Netflix problem)。这篇硕士论文讨论了其在稀疏问题中应用,我们通过系统的学习和研究,发现了新的解决方法,进一步提高现有的理论,使其应用在压缩感知等稀疏问题。本文的创新点有以下几点:第一:提出了改进的线性Bregman迭代算法以及A-、A+线性残差迭代算法。第二:推导了临近点算子和软阈值算子之间的关系,并将莫洛包络思想应用于求解基追踪问题。第三:运用加速超松弛技术,使矩阵补全的低秩矩阵拟合算法得以实现。第四:用新的方法推导交替迭代算法,并将其用于分解非负矩阵。
【关键词】：
【学位授予单位】：中国石油大学(华东)【学位级别】：硕士【学位授予年份】：2014【分类号】：TP391.41;O151.21【目录】：
摘要4-5Abstract5-8第一章 绪论8-10 1.1 研究的背景及其意义8-9 1.2 矩阵补全问题的论述9-10第二章 预备知识10-19 2.1 凸优化10-11 2.2 正则化方法11-19
2.2.1 适定性正则化方法11-12
2.2.2 迭代正则化方法12-13
2.2.3 信赖域方法13-14
2.2.4 Lanczos方法14
2.2.5 Lavrentiev正则化方法14-15
2.2.6 奇异值分解算法15-17
2.2.7 Landweber-Fridman迭代算法17-19第三章 基追踪问题19-41 3.1 BREGMAN距离的定义与性质19 3.2 基追踪公式推导及相关证明19-31
3.2.1 问题陈述19-20
3.2.2 线性Bregman迭代算法20-27
3.2.3 线性残差迭代算法27-31 3.3 莫洛包络算法31-36 3.4 数值模拟36-41第四章 软阈值算法41-43 4.1 基追踪问题的软阈值迭代41-42 4.2 矩阵补全问题的软阈值42-43第五章 低秩分解模型算法43-49 5.1 交替极小化格式45-49
5.1.1 非线性Gauss-Seidal方法45
5.1.2 非线性类SOR格式45-49第六章 交替迭代算法求解非负因子的矩阵补全49-61 6.1 非负矩阵分解的定义49-50 6.2 相关的算法50-51 6.3 主要算法51-54 6.4 收敛性分析54-57 6.5 非线性SOR算法57-58 6.6 数值实验58-61结论与展望61-62 本文的主要创新点61 后续研究工作展望61-62参考文献62-67攻读硕士学位期间成果67-68致谢68
欢迎：、、)
支持CAJ、PDF文件格式
【相似文献】
中国期刊全文数据库
鄂国康;;[J];西南民族学院学报(自然科学版);1991年04期
田钟颖,严克明;[J];甘肃工业大学学报;1989年04期
王群英;;[J];长春工业大学学报(自然科学版);2011年01期
张海建;;[J];科技通报;2013年12期
李华云;;[J];现代情报;2008年10期
汤彬;段波;;[J];物探化探计算技术;1989年04期
陈伯伦;陈崚;邹盛荣;徐秀莲;;[J];计算机科学;2014年02期
范云鹏;周水生;;[J];数学学习与研究;2012年03期
贺超波;汤庸;沈玉利;石玉强;;[J];小型微型计算机系统;2014年06期
胡家赣;[J];计算数学;1983年01期
中国重要会议论文全文数据库
王春江;钱若军;王人鹏;杨联萍;;[A];第九届全国结构工程学术会议论文集第Ⅰ卷[C];2000年
王春江;王人鹏;钱若军;王颖;;[A];“力学2000”学术大会论文集[C];2000年
中国博士学位论文全文数据库
李英明;[D];浙江大学;2014年
赵科科;[D];浙江大学;2012年
郭亦鸿;[D];清华大学;2014年
胡惠轶;[D];江南大学;2014年
陈根浪;[D];浙江大学;2012年
中国硕士学位论文全文数据库
秦晓晖;[D];华南理工大学;2015年
刘凤林;[D];南京理工大学;2015年
李源鑫;[D];福建师范大学;2015年
陈洪涛;[D];福建师范大学;2015年
张济龙;[D];燕山大学;2015年
邓志豪;[D];浙江大学;2015年
余露;[D];杭州师范大学;2015年
倪泽明;[D];浙江大学;2015年
丁浩;[D];复旦大学;2014年
吴世伟;[D];复旦大学;2014年
&快捷付款方式
&订购知网充值卡
400-819-9993
《中国学术期刊（光盘版）》电子杂志社有限公司
同方知网数字出版技术股份有限公司
地址：北京清华大学 84-48信箱 大众知识服务
出版物经营许可证 新出发京批字第直0595号
订购热线：400-819-82499
服务热线：010--
在线咨询：
传真：010-
京公网安备75号工具类服务
编辑部专用服务
作者专用服务
矩阵补全的模型、算法和应用研究
当矩阵的元素有未知或缺失的情况下，矩阵补全(Matrix Completion，简记为:MC)就是根据已知元素估计未知元素，从而把矩阵恢复完整的过程.目前矩阵补全已广泛应用于机器学习，工程控制，图像和视频处理.一般情况下，如果不对矩阵的特性做任何假设，则矩阵缺失的元素可以取任何值，矩阵补全在理论上是不可能唯一实现的.但是如果对矩阵的特性做一些假设，例如低秩，则矩阵补全的解就是唯一的.　　本文主要研究矩阵补全的一些模型，算法和应用.全文共分六章.首先在第一章，我们简要介绍矩阵补全的模型，一些经典算法，研究背景，意义和现状，并概述了本文的主要工作.　　第二章，在线性规划的系数矩阵存在信息缺失且已知元素不精确的情况下，我们给出了一个新的基于矩阵补全的鲁棒线性优化模型和算法.线性规划目前已广泛应用于投入产出分析中，用于分析经济和环境科学中行业之间的相互依存关系.在这些应用中，系数矩阵的一些元素无法测量到，即使能测量到也会存在取样误差.因为系数矩阵在一般情况下是低秩的，所以我们可以用核范数来描述不确定性集合，得到线性规划问题的鲁棒模型.基于交替乘子法，我们设计了一种快速求解算法.在一些随机例子和合成例子上的数值实验结果表明我们的模型和算法是很有效的.　　第三章，我们给出了矩阵补全的三种新的非凸模型和相应的算法，它们是为信息缺失条件下的高维协方差矩阵估计设计的.协方差矩阵在风险管理，资产定价，资本配置等应用领域发挥着重要的作用.在高维条件下，即在矩阵的维数趋近于或大于样本的数目时，协方差矩阵估计就变得非常困难了.一种广泛使用的降维方法是多因子模型.基于多因子模型的高维协方差矩阵估计方法具有很快的收敛速度，在一些应用中输出的协方差矩阵具有很高的精度.但是由于技术和花费方面的原因，因子矩阵中有大量的信息无法通过调查得到.在因子矩阵存在信息缺失条件下，基于多因子模型的高维协方差矩阵估计的协方差矩阵的质量就会衰退.因为因子矩阵往往是满秩的，目前已有的矩阵补全的方法不能直接应用到高维协方差矩阵估计中.本章我们给出了新的矩阵补全的非凸模型，并应用交替方向乘子法进行求解.数值实验表明，已有的基于核范数的凸的矩阵补全方法不能直接用来估计信息缺失条件下的高维协方差矩阵，而我们提出的非凸模型和算法可以给出非常令人满意的结果.　　第四章，我们给出了非负矩阵补全的两个模型和相应的算法.生命周期评价(LCA)和投入产出分析(IOA)是两种数据密集型(data-intensive)方法，这两种方法的可靠性和应用性非常依赖于数据的质量.但是由于技术和花费方面的原因，并不是所有的数据可以通过调查得到.但是，在生命周期评价中生产相似商品的过程往往具有相似的数据结构.而在投入产出分析中，历史调查年份的部门和目标年份的部门具有相似的投入结构.这些结论表明了生命周期评价和投入产出分析中的技术矩阵往往具有低秩或近似低秩的结构，这种结构促使我们应用低秩矩阵补全的技术来补全缺失的信息.如果我们忽略生命周期评价和投入产出分析中少量的副产品，技术矩阵应该是非负的.本章我们分别针对已知数据有噪声和无噪声的情况提出了一种非负矩阵补全的模型，它们都可以用交替方向乘子法进行求解.“Ecoinvent”数据库中存在大量的数据缺失，因此我们把提出的模型和算法应用到生命周期评价广泛使用的“Ecoinvent”数据库.数值结果显示新算法是非常有效的.　　第五章，我们针对第四章提出的带非负约束的核范数正则化最小二乘模型设计了另外三种快速算法.非负矩阵补全根据矩阵的一些已知元素寻找一个非负且低秩矩阵的过程.非负矩阵补全可以通过求解带非负约束的核范数正则化最小二乘模型进行.我们可以应用交替方向乘子法求解此模型.引入分离变量的方式不同，我们可以得到完全不同的算法.其中两种算法是基于交替方向乘子法的精确算法，每个子问题都可以精确求解.第三种算法也是基于交替方向乘子法，但其中一个子问题通过Forward-backward分裂方法近似求解，得到了一种非精确算法.我们在两类问题上测试新提出的三种算法，分别是随机矩阵补全例子和随机近似低秩例子.数值结果表明我们的算法都是非常有效的.　　第六章，总结了本文的主要工作，并提出了一些有待进一步研究的课题.
学科专业：
授予学位：
学位授予单位：
导师姓名：
学位年度：
在线出版日期：
本文读者也读过
相关检索词
万方数据知识服务平台--国家科技支撑计划资助项目（编号：2006BAH03B01）(C)北京万方数据股份有限公司
万方数据电子出版社 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
基于范数正则化矩阵补全的无线传感网定位算法
下载积分：1000
内容提示：基于范数正则化矩阵补全的无线传感网定位算法
文档格式：PDF|
浏览次数：9|
上传日期： 14:27:08|
文档星级：
全文阅读已结束，如果下载本文需要使用
 1000 积分
下载此文档
该用户还上传了这些文档
基于范数正则化矩阵补全的无线传感网定位算法
关注微信公众号基于社交网络与矩阵补全的协同过滤推荐算法研究―李坷璐(0111)_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
基于社交网络与矩阵补全的协同过滤推荐算法研究―李坷璐(0111)
阅读已结束，下载文档到电脑
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，方便使用
还剩15页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢}