您的位置： &
矩阵补全算法研究进展
优质期刊推荐经典算法_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
上传于|0|0|暂无简介
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩10页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢工具类服务
编辑部专用服务
作者专用服务
矩阵补全的模型、算法和应用研究
当矩阵的元素有未知或缺失的情况下，矩阵补全(Matrix Completion，简记为:MC)就是根据已知元素估计未知元素，从而把矩阵恢复完整的过程.目前矩阵补全已广泛应用于机器学习，工程控制，图像和视频处理.一般情况下，如果不对矩阵的特性做任何假设，则矩阵缺失的元素可以取任何值，矩阵补全在理论上是不可能唯一实现的.但是如果对矩阵的特性做一些假设，例如低秩，则矩阵补全的解就是唯一的.　　本文主要研究矩阵补全的一些模型，算法和应用.全文共分六章.首先在第一章，我们简要介绍矩阵补全的模型，一些经典算法，研究背景，意义和现状，并概述了本文的主要工作.　　第二章，在线性规划的系数矩阵存在信息缺失且已知元素不精确的情况下，我们给出了一个新的基于矩阵补全的鲁棒线性优化模型和算法.线性规划目前已广泛应用于投入产出分析中，用于分析经济和环境科学中行业之间的相互依存关系.在这些应用中，系数矩阵的一些元素无法测量到，即使能测量到也会存在取样误差.因为系数矩阵在一般情况下是低秩的，所以我们可以用核范数来描述不确定性集合，得到线性规划问题的鲁棒模型.基于交替乘子法，我们设计了一种快速求解算法.在一些随机例子和合成例子上的数值实验结果表明我们的模型和算法是很有效的.　　第三章，我们给出了矩阵补全的三种新的非凸模型和相应的算法，它们是为信息缺失条件下的高维协方差矩阵估计设计的.协方差矩阵在风险管理，资产定价，资本配置等应用领域发挥着重要的作用.在高维条件下，即在矩阵的维数趋近于或大于样本的数目时，协方差矩阵估计就变得非常困难了.一种广泛使用的降维方法是多因子模型.基于多因子模型的高维协方差矩阵估计方法具有很快的收敛速度，在一些应用中输出的协方差矩阵具有很高的精度.但是由于技术和花费方面的原因，因子矩阵中有大量的信息无法通过调查得到.在因子矩阵存在信息缺失条件下，基于多因子模型的高维协方差矩阵估计的协方差矩阵的质量就会衰退.因为因子矩阵往往是满秩的，目前已有的矩阵补全的方法不能直接应用到高维协方差矩阵估计中.本章我们给出了新的矩阵补全的非凸模型，并应用交替方向乘子法进行求解.数值实验表明，已有的基于核范数的凸的矩阵补全方法不能直接用来估计信息缺失条件下的高维协方差矩阵，而我们提出的非凸模型和算法可以给出非常令人满意的结果.　　第四章，我们给出了非负矩阵补全的两个模型和相应的算法.生命周期评价(LCA)和投入产出分析(IOA)是两种数据密集型(data-intensive)方法，这两种方法的可靠性和应用性非常依赖于数据的质量.但是由于技术和花费方面的原因，并不是所有的数据可以通过调查得到.但是，在生命周期评价中生产相似商品的过程往往具有相似的数据结构.而在投入产出分析中，历史调查年份的部门和目标年份的部门具有相似的投入结构.这些结论表明了生命周期评价和投入产出分析中的技术矩阵往往具有低秩或近似低秩的结构，这种结构促使我们应用低秩矩阵补全的技术来补全缺失的信息.如果我们忽略生命周期评价和投入产出分析中少量的副产品，技术矩阵应该是非负的.本章我们分别针对已知数据有噪声和无噪声的情况提出了一种非负矩阵补全的模型，它们都可以用交替方向乘子法进行求解.“Ecoinvent”数据库中存在大量的数据缺失，因此我们把提出的模型和算法应用到生命周期评价广泛使用的“Ecoinvent”数据库.数值结果显示新算法是非常有效的.　　第五章，我们针对第四章提出的带非负约束的核范数正则化最小二乘模型设计了另外三种快速算法.非负矩阵补全根据矩阵的一些已知元素寻找一个非负且低秩矩阵的过程.非负矩阵补全可以通过求解带非负约束的核范数正则化最小二乘模型进行.我们可以应用交替方向乘子法求解此模型.引入分离变量的方式不同，我们可以得到完全不同的算法.其中两种算法是基于交替方向乘子法的精确算法，每个子问题都可以精确求解.第三种算法也是基于交替方向乘子法，但其中一个子问题通过Forward-backward分裂方法近似求解，得到了一种非精确算法.我们在两类问题上测试新提出的三种算法，分别是随机矩阵补全例子和随机近似低秩例子.数值结果表明我们的算法都是非常有效的.　　第六章，总结了本文的主要工作，并提出了一些有待进一步研究的课题.
学科专业：
授予学位：
学位授予单位：
导师姓名：
学位年度：
在线出版日期：
本文读者也读过
相关检索词
万方数据知识服务平台--国家科技支撑计划资助项目（编号：2006BAH03B01）(C)北京万方数据股份有限公司
万方数据电子出版社 上传我的文档
 下载
 收藏
网络营销助理，网店执行经理，生产加工运输技术工程师
 下载此文档
正在努力加载中...
矩阵补全模型及其算法研究综述 优先出版
下载积分：1500
内容提示：矩阵补全模型及其算法研究综述 优先出版
文档格式：PDF|
浏览次数：11|
上传日期： 18:24:15|
文档星级：
全文阅读已结束，如果下载本文需要使用
 1500 积分
下载此文档
阅读此文档的用户还读了
矩阵补全模型及其算法研究综述 优先出版
官方公共微信矩阵乘法及经典算法
　　乘法是一种高效的算法可以把一些一维递推优化到log（ n
)，还可以求路径方案等，所以更是是一种应用性极强的算法。
　　矩阵，是线性代数中的基本概念之一。一个m&n的矩阵就是m&n个数排成m行n列的一个数阵。由于它把许多数据紧凑的集中到了一起，所以有时候可以简便地表示一些复杂的模型。矩阵乘法看起来很奇怪，但实际上非常有用。它是这样定义的，只有当矩阵A的列数与矩阵B的行数相等时A&B才有意义。一个m&n的矩阵a（m,n)左乘一个n&p的矩阵b（n,p)，会得到一个m&p的矩阵c（m,p)，满足
　　矩阵乘法满足结合率，但不满足交换率
　　一般的矩乘要结合快速幂才有效果``
　　一般矩乘的代码：function mul( a , b : Tmatrix ) : T
　　i,j,k :
　　fillchar( c , ( c ) , 0 );
　　for k:=0 to m do
　　for i:=0 to m do
　　for j:=0 to m do
　　inc( c[ i , j ] , a[ i , k ]*b[ k , j ] );
　　if c[ i , j ] & ra then c[ i , j ]:=c[ i , j ] mod
　　mul:=c;
　　-------------------------------------------------------------------------------------------------------------
　　矩阵乘法在编程语言中的运用例题(十个利用矩阵乘法解决的经典题目 )
　　-------------------------------------------------------------------------------------------------------------
　　好像目前还没有这方面题目的总结。这几天连续看到四个问这类题目的人，今天在这里简单写一下。这里我们不介绍其它有关矩阵的知识，只介绍矩阵乘法和相关性质。
　　不要以为数学中的矩阵也是黑色屏幕上不断变化的绿色字符。在数学中，一个矩阵说穿了就是一个。一个n行m列的矩阵可以乘以一个m行p列的矩阵，得到的结果是一个n行p列的矩阵，其中的第i行第j列位置上的数等于前一个矩阵第i行上的m个数与后一个矩阵第j列上的m个数对应相乘后所有m个乘积的和。比如，下面的算式表示一个2行2列的矩阵乘以2行3列的矩阵，其结果是一个2行3列的矩阵。其中，结果的那个4等于2*2+0*1：
　　下面的算式则是一个1 x 3的矩阵乘以3 x 2的矩阵，得到一个1 x 2的矩阵：
　　矩阵乘法的两个重要性质：一，矩阵乘法不满足交换律；二，矩阵乘法满足。为什么矩阵乘法不满足呢？废话，交换过来后两个矩阵有可能根本不能相乘。为什么它又满足结合律呢？仔细想想你会发现这也是废话。假设你有三个矩阵A、B、C，那么(AB)C和A(BC)的结果的第i行第j列上的数都等于所有A(ik)*B(kl)*C(lj)的和（所有的k和l）。
　　经典题目1
给定n个点，m个操作，构造O(m+n)的算法输出m个操作后各点的位置。操作有平移、缩放、翻转和旋转
　　这里的操作是对所有点同时进行的。其中翻转是以坐标轴为对称轴进行翻转（两种情况），旋转则以原点为中心。如果对每个点分别进行模拟，那么m个操作总共耗时O(mn)。利用矩阵乘法可以在O(m)的时间里把所有操作合并为一个矩阵，然后每个点与该矩阵相乘即可直接得出最终该点的位置，总共耗时O(m+n)。假设初始时某个点的坐标为x和y，下面5个矩阵可以分别对其进行平移、旋转、翻转和旋转操作。预先把所有m个操作所对应的矩阵全部乘起来，再乘以(x,y,1)，即可一步得出最终点的位置。
　　经典题目2 给定矩阵A，请快速计算出A^n（n个A相乘）的结果，输出的每个数都mod p。
　　由于矩阵乘法具有结合律，因此A^4 = A * A * A * A = (A*A) * (A*A) = A^2 *
A^2。我们可以得到这样的结论：当n为偶数时，A^n = A^(n/2) * A^(n/2)；当n为奇数时，A^n = A^(n/2)
* A^(n/2) * A
（其中n/2取整）。这就告诉我们，计算A^n也可以使用二分快速求幂的方法。例如，为了算出A^25的值，我们只需要地计算出A^12、A^6、A^3的值即可。根据的一些结果，我们可以在计算过程中不断取模，避免高精度运算。
　　经典题目3 POJ3233 (感谢)
　　题目大意：给定矩阵A，求A + A^2 + A^3 + ... +
A^k的结果（两个矩阵相加就是对应位置分别相加）。输出的数据mod m。k&=10^9。
　　这道题两次二分，相当经典。首先我们知道，A^i可以二分求出。然后我们需要对整个题目的数据规模k进行二分。比如，当k=6时，有：
　　A + A^2 + A^3 + A^4 + A^5 + A^6 =(A + A^2 + A^3) + A^3*(A + A^2 +
　　应用这个式子后，规模k减小了一半。我们二分求出A^3后再递归地计算A + A^2 + A^3，即可得到原问题的答案。
　　经典题目4 VOJ1049
　　题目大意：顺次给出m个置换，反复使用这m个置换对初始序列进行操作，问k次置换后的序列。m&=10,
　　首先将这m个置换“合并”起来（算出这m个置换的乘积），然后接下来我们需要执行这个置换k/m次（取整，若有余数则剩下几步模拟即可）。注意任意一个置换都可以表示成矩阵的形式。例如，将1
2 3 4置换为3 1 2 4，相当于下面的矩阵乘法：
　　置换k/m次就相当于在前面乘以k/m个这样的矩阵。我们可以二分计算出该矩阵的k/m次方，再乘以初始序列即可。做出来了别忙着高兴，得意之时就是你灭亡之日，别忘了最后可能还有几个置换需要模拟。
　　经典题目5 《》207页（2.1代数方法和模型，[例题5]细菌，版次不同可能页码有偏差）
　　大家自己去看看吧，书上讲得很详细。解题方法和上一题类似，都是用矩阵来表示操作，然后二分求最终状态。
　　经典题目6 给定n和p，求第n个Fibonacci数mod p的值，n不超过2^31
　　根据前面的一些思路，现在我们需要构造一个2 x
2的矩阵，使得它乘以(a,b)得到的结果是(b,a+b)。每多乘一次这个矩阵，这两个数就会多一次。那么，我们把这个2 x
2的矩阵自乘n次，再乘以(0,1)就可以得到第n个Fibonacci数了。不用多想，这个2 x 2的矩阵很容易构造出来：
　　经典题目7 VOJ1067
　　我们可以用上面的方法二分求出任何一个线性递推式的第n项，其对应矩阵的为：在右上角的(n-1)*(n-1)的小矩阵中的主对角线上填1，矩阵第n行填对应的系数，其它地方都填0。例如，我们可以用下面的矩阵乘法来二分计算f(n)
= 4f(n-1) - 3f(n-2) + 2f(n-4)的第k项：
　　利用矩阵乘法求解线性递推关系的题目我能编出一卡车来。这里给出的例题是系数全为1的情况。
　　经典题目8 给定一个，问从恰好走k步（允许重复经过边）到达B点的方案数mod p的值
　　把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i-&j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的路径数，我们只需要二分求出A^k即可。
　　经典题目9 用1 x 2的填满M x
N的矩形有多少种方案，M&=5，N&2^31，输出答案mod
　　我们以M=3为例进行讲解。假设我们把这个矩形横着放在电脑屏幕上，从右往左一列一列地进行填充。其中前n-2列已经填满了，第n-1列参差不齐。现在我们要做的事情是把第n-1列也填满，将状态转移到第n列上去。由于第n-1列的状态不一样（有8种不同的状态），因此我们需要分情况进行讨论。在图中，我把转移前8种不同的状态放在左边，转移后8种不同的状态放在右边，左边的某种状态可以转移到右边的某种状态就在它们之间连一根线。注意为了保证方案不重复，状态转移时我们不允许在第n-1列竖着放一个多米诺骨牌（例如左边第2种状态不能转移到右边第4种状态），否则这将与另一种转移前的状态重复。把这8种状态的转移关系画成一个有向图，那么问题就变成了这样：从状态111出发，恰好经过n步回到这个状态有多少种方案。比如，n=2时有3种方案，111-&011-&111、111-&110-&111和111-&000-&111，这与用多米诺骨牌覆盖3x2矩形的方案一一对应。这样这个题目就转化为了我们前面的例题8。
　　后面我写了一份此题的源代码。你可以再次看到位运算的相关应用。
　　经典题目10 POJ2778
　　题目大意是，检测所有可能的n位串有多少个DNA串中不含有指定的病毒片段。合法的DNA只能由ACTG四个字符构成。题目将给出10个以内的病毒片段，每个片段长度不超过10。数据规模n&=2
000 000 000。
　　下面的讲解中我们以,AAA,GGC,CT这四个病毒片段为例，说明怎样像上面的题一样通过构图将问题转化为例题8。我们找出所有病毒片段的前缀，把n位DNA分为以下7类：以AT结尾、以AA结尾、以GG结尾、以?A结尾、以?G结尾、以?C结尾和以??结尾。其中问号表示“其它情况”，它可以是任一字母，只要这个字母不会让它所在的串成为某个病毒的前缀。显然，这些分类是全集的一个划分（交集为空，并集为全集）。现在，假如我们已经知道了长度为n-1的各类DNA中符合要求的DNA个数，我们需要求出长度为n时各类DNA的个数。我们可以根据各类型间的转移构造一个边上带权的有向图。例如，从AT不能转移到AA，从AT转移到??有4种方法（后面加任一字母），从?A转移到AA有1种方案（后面加个A），从?A转移到??有2种方案（后面加G或C），从GG到??有2种方案（后面加C将构成病毒片段，不合法，只能加A和T）等等。这个图的构造过程类似于用有限状态做串匹配。然后，我们就把这个图转化成矩阵，让这个矩阵自乘n次即可。最后输出的是从??状态到所有其它状态的路径数总和。
　　题目中的数据规模保证前缀数不超过100，一次矩阵乘法是三方的，一共要乘log(n)次。因此这题总的复杂度是100^3 *
log(n)，AC了。
　　最后给出第9题的代码供大家参考（今天写的，熟悉了一下C++的类和运算符重载）。为了避免大家看代码看着看着就忘了，我把这句话放在前面来说：
　　Matrix67原创，转贴请注明出处。
　　#include &cstdio&
　　#define SIZE (1&&m)
　　#define MAX_SIZE 32
　　class CMatrix
　　public:
　　long element[MAX_SIZE][MAX_SIZE];
　　void setSize(int);
　　void setModulo(int);
　　CMatrix * (CMatrix);
　　CMatrix power(int);
　　private:
　　void CMatrix::setSize(int a)
　　for (int i=0; i&a; i++)
　　for (int j=0; j&a; j++)
　　element[i][j]=0;
　　size =
　　void CMatrix::setModulo(int a)
　　modulo =
　　CMatrix CMatrix::operator* (CMatrix param)
　　product.setSize(size);
　　product.setModulo(modulo);
　　for (int i=0; i& i++)
　　for (int j=0; j& j++)
　　for (int k=0; k& k++)
　　product.element[i][j]+=element[i][k]*param.element[k][j];
　　product.element[i][j]%=
　　CMatrix CMatrix::power(int exp)
　　CMatrix tmp = (*this) * (*this);
　　if (exp==1) return *
　　else if (exp & 1) return tmp.power(exp/2) *
　　else return tmp.power(exp/2);
　　int main()
　　 int validSet[]={0,3,6,12,15,24,27,30};
　　long n, m,
　　scanf("%d%d%d", &n, &m,
　　unit.setSize(SIZE);
　　for(int i=0; i&SIZE; i++)
　　for(int j=0; j&SIZE; j++)
　　if( ((~i)&j) == ((~i)&(SIZE-1))
　　 isValid=
　　for (int k=0; k&8; k++)=isValid||(i&j)==validSet[k];
　　unit.element[i][j]=isV
　　unit.setModulo(p);
　　printf("%d", unit.power(n).element[SIZE-1][SIZE-1] );
　　return 0;
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。