论文部分内容阅读
当矩阵的元素有未知或缺失的情况下,矩阵补全(Matrix Completion,简记为: MC)就是根据己知元素估计未知元素,从而把矩阵恢复完整的过程.目前矩阵补全己广泛应用于机器学习,工程控制,图像和视频处理.一般情况下,如果不对矩阵的特性做任何假设,则矩阵缺失的元素可以取任何值,矩阵补全在理论上是不可能唯一实现的.但是如果对矩阵的特性做一些假设,例如低秩,则矩阵补全的解就是唯一的.本文主要研究矩阵补全的一些模型,算法和应用.全文共分六章.首先在第一章,我们简要介绍矩阵补全的模型,一些经典算法,研究背景,意义和现状,并概述了本文的主要工作.第二章,在线性规划的系数矩阵存在信息缺失且己知元素不精确的情况下,我们给出了一个新的基于矩阵补全的鲁棒线性优化模型和算法.线性规划目前己广泛应用于投入产出分析中,用于分析经济和环境科学中行业之间的相互依存关系.在这些应用中,系数矩阵的一些元素无法测量到,即使能测量到也会存在取样误差.因为系数矩阵在一般情况下是低秩的,所以我们可以用核范数来描述不确定性集合,得到线性规划问题的鲁棒模型.基于交替乘子法,我们设计了一种快速求解算法.在一些随机例子和合成例子上的数值实验结果表明我们的模型和算法是很有效的.第三章,我们给出了矩阵补全的三种新的非凸模型和相应的算法,它们是为信息缺失条件下的高维协方差矩阵估计设计的.协方差矩阵在风险管理,资产定价,资本配置等应用领域发挥着重要的作用.在高维条件下,即在矩阵的维数趋近于或大于样本的数目时,协方差矩阵估计就变得非常困难了.一种广泛使用的降维方法是多因子模型.基于多因子模型的高维协方差矩阵估计方法具有很快的收敛速度,在一些应用中输出的协方差矩阵具有很高的精度.但是由于技术和花费方面的原因,因子矩阵中有大量的信息无法通过调查得到.在因子矩阵存在信息缺失条件下,基于多因子模型的高维协方差矩阵估计的协方差矩阵的质量就会衰退.因为因子矩阵往往是满秩的,目前己有的矩阵补全的方法不能直接应用到高维协方差矩阵估计中.本章我们给出了新的矩阵补全的非凸模型,并应用交替方向乘子法进行求解.数值实验表明,己有的基于核范数的凸的矩阵补全方法不能直接用来估计信息缺失条件下的高维协方差矩阵,而我们提出的非凸模型和算法可以给出非常令人满意的结果.第四章,我们给出了非负矩阵补全的两个模型和相应的算法.生命周期评价(LCA)和投入产出分析(IOA)是两种数据密集型(data-intensive)方法,这两种方法的可靠性和应用性非常依赖于数据的质量.但是由于技术和花费方面的原因,并不是所有的数据可以通过调查得到.但是,在生命周期评价中生产相似商品的过程往往具有相似的数据结构.而在投入产出分析中,历史调查年份的部门和目标年份的部门具有相似的投入结构.这些结论表明了生命周期评价和投入产出分析中的技术矩阵往往具有低秩或近似低秩的结构,这种结构促使我们应用低秩矩阵补全的技术来补全缺失的信息.如果我们忽略生命周期评价和投入产出分析中少量的副产品,技术矩阵应该是非负的.本章我们分别针对己知数据有噪声和无噪声的情况提出了一种非负矩阵补全的模型,它们都可以用交替方向乘子法进行求解.“Ecoinvent”数据库中存在大量的数据缺失,因此我们把提出的模型和算法应用到生命周期评价广泛使用的“Ecoinvent”数据库.数值结果显示新算法是非常有效的.第五章,我们针对第四章提出的带非负约束的核范数正则化最小二乘模型设计了另外三种快速算法.非负矩阵补全根据矩阵的一些己知元素寻找一个非负且低秩矩阵的过程.非负矩阵补全可以通过求解带非负约束的核范数正则化最小二乘模型进行.我们可以应用交替方向乘子法求解此模型.引入分离变量的方式不同,我们可以得到完全不同的算法.其中两种算法是基于交替方向乘子法的精确算法,每个子问题都可以精确求解.第三种算法也是基于交替方向乘子法,但其中一个子问题通过Forward-backward分裂方法近似求解,得到了一种非精确算法.我们在两类问题上测试新提出的三种算法,分别是随机矩阵补全例子和随机近似低秩例子.数值结果表明我们的算法都是非常有效的.第六章,总结了本文的主要工作,并提出了一些有待进一步研究的课题.