半正定矩阵完备的一种新算法

摘要

半正定矩阵完备（PSDMC）目的是从矩阵的一个子集中恢复半正定和低秩矩阵。它广泛应用于许多领域，如统计分析和系统控制。这项任务可以通过求解具有半正定约束的核范数正则化线性最小二乘模型来完成。我们应用了广泛使用的alte采用方向乘子法求解模型，得到了一种新的算法，数值实验证明了新算法的适用性和有效性，恢复结果表明我们的算法是有帮助的。

1.导言

矩阵补全（MC）是恢复矩阵中未知或缺失元素的过程。在矩阵的某些假设下，例如低秩或近似低秩，可以很好地重构不完备矩阵[1.,2.].矩阵补全广泛应用于机器学习、统计分析、系统控制、图像和视频处理等领域[3.]，其中低秩或近似低秩的矩阵广泛用于模型构造。

最近，人们对低秩矩阵完备（LRMC）问题进行了广泛的研究。仿射秩最小化问题包括寻找满足给定线性约束系统的最小秩矩阵。然而，它是NP难问题（不确定多项式时间难问题）由于秩函数的组合性质。参考文献[1.,2.]结果表明，在合理的条件下，通过求解核范数极小化问题，可以找到LRMC的解。奇异值阈值法[4.]采用近似奇异值分解（FPCA）的不动点延拓法[5.]SVT采用线性化Bregman迭代来解决无约束核范数正则化线性最小二乘问题。FPCA采用基于迭代收缩阈值算法的迭代，并将延拓技术与一个近似奇异值分解程序，加速算法。参考[6.]提出了一种加速的近梯度奇异值阈值分割算法，并在LMaFit中建立了一个完全不同的模型[7.]，这是一种非线性逐次超松弛算法，每次迭代只需要解一个线性最小二乘问题。有关LRMC的更多详细信息，请参阅[1.,8.–10及其参考文献。

在实际应用中，通常要求完成的矩阵是半正定的。例如，协方差矩阵及其逆：统计分析的精度矩阵，都是半正定的。最近，人们对高维协方差矩阵估计进行了广泛的研究。它们都推动了半正定矩阵的发展初始矩阵完成（PSDMC）。参考[11]在某些特殊条件下完成矩阵完成任务，并使用交替方向乘数法（ADMM）[12–15来解这个模型。参考文献(16,17]提出了非负矩阵补全的新模型，并利用ADMM求解。

我们在这项工作中的主要贡献是开发了一种有效的PSDMC算法。首先，我们提出了具有半正定约束的核范数正则化线性最小二乘模型。由于其鲁棒性，我们选择它作为PSDMC的模型。该模型的结构建议一种交替极小化ion格式，它非常适合于解决大规模问题。我们给出了一个精确的基于ADMM的算法，它的子问题得到了精确的解决。我们在两类问题上测试了新的基于ADMM的算法：随机矩阵完成问题和随机低秩近似问题。数值实验表明，我们提出的算法都是有效的本论文的组织结构如下2.介绍了PSDMC的模型和算法。第节给出了一些数值结果3.．

本文将使用以下符号。大写（小写）字母用于矩阵（列向量）。所有向量都是列向量；下标表示矩阵和向量的转置。表示对角矩阵在主对角线上。是一个适当维数的全零矩阵；代表了单位矩阵。的痕迹，即，表示为.弗罗贝尼乌斯规范被定义为.两个矩阵之间的欧氏内积和被定义为.不平等意味着是半正定的。等式意味着所有参赛作品．

2.基于admm的PSDMC方法

2.1.PSDMC模型

研究了从一个子集上恢复半正定低秩矩阵的矩阵完备问题 在哪里决策变量是什么的索引集是已知的元素．

允许是非零限制在索引集上的稀疏矩阵在子空间上的投影；即，

从定义，则可以将模型中的等式约束(1.就…而言.由于目标函数的组合性质，模型(1.)一般来说是NP难的。灵感来自于在核规范下矩阵完成的成功[1.,2.,10]，我们使用核范数作为估计最优解模型的(1.)根据以下模型： 核规范在哪里属于的奇异值的和；即， 在哪里是第一大奇异值。对于正半定矩阵，．

如果矩阵的已知元素没有噪音，也就是说，是可靠的，我们将直接解决模型(3.)进行SDPMC。相反，如果已知元素的向量是被噪音污染了吗必须放松，造成以下问题: 或具有半正定约束的核范数正则化线性最小二乘模型： 在这里,和是给定的参数，其值应根据噪声级设置和设置得当,(5.)及(6.)它们是等价的(6.)通常优于(5.)对于有噪声的观测，我们的算法可以扩展到(5.)稍加修改。

实际上，模特儿(6.)在实践中尤其有用。这是因为已知的信息往往来自于大规模的调查，不可避免地会受到抽样误差的污染。本文中，我们选择模型(6.)作为进行NMC的模式。

2．2．基于admm的模型建模方法(6.)

在本节中，我们提出了一个为模型(6.)。为了便于有效使用ADMM，我们引入了一个新的矩阵（拆分）变量并考虑模型的等价形式(6.): 在哪里,. 模型的增广拉格朗日函数(7.)是 在哪里是拉格朗日乘数。是一个惩罚参数。

模型乘子的交替方向法(7.)通过连续最小化得到关于和以交替的方式；即， 在哪里．

通过重新安排(9)，相当于 在哪里.设其特征值分解（EVD）为,在那里和.定义收缩运算符像 然后 是问题的最优解(9).

通过重新安排(9 b)，相当于 模型(13)可分为两个子问题： 在哪里是．最后，我们可以得到(13)通过求解上述两个子问题。 在哪里．

简而言之，ADMM应用于模型(7.)产生迭代:

基于以上考虑，我们得出了算法1.．

对凸问题中ADMM及其变体的收敛性进行了广泛的研究。有兴趣的读者可参考[12–15,18–20.]，以及其中的参考资料。自(6.)是凸的，是算法的收敛性1.得到全局最优解。

3.数值结果

在这一节中，我们报告了我们提出的基于admm的算法在一系列矩阵问题中的应用，以证明它的能力。为了说明结合不同程序的算法方法的性能，我们测试以下两个求解器。(1)算法在[11］．(2)算法1.，模型(6.).

我们在MATLAB中实现了我们的算法，所有的实验都在2.20上进行 GHz英特尔奔腾PC带6.0 GHz的内存和MATLAB 2012b。

３．１．两个求解器的实现和参数

我们在随机正半定矩阵问题上检验了上述两种求解方法。我们按以下步骤进行数值实验。首先，我们构造了一个低秩正半定矩阵. 其次，我们选择一个子集元素均匀随机地从元素并表示它们的索引集为．未知元素的索引集记为.比率矩阵中的测量数量和条目数量之间的关系表示为“SR”（采样率）完成；结果表示为.最后，我们将检查和它的实际值．

算法中最重要的算法参数1.是,,,，以及最大迭代次数.在我们的实施中，我们设置,,和.然而很难设置，因为它既不能太大也不能太小。通常选择为中等值。当等于三个不同的值。如表所示1.．

我们可以使用连续化技术[5.,6.加快ADMM-SDP的融合。如果模型(6.)用目标参数值求解，我们建议求解一系列的模型(6.)按递减顺序排列.当出现新问题时，与，是待解的，求出当前问题的近似解与作为起点。在本节的数值实验中3.2，我们设定了初始值更新在迭代.算法的停止准则1.只要满足以下三个条件，则满足：

3.2.关于随机矩阵完成问题的实验

矩阵有地位在本小节中，是由以下程序随机创建的(参见[5.,7.:两个随机矩阵和i。id标准高斯条目首先生成，是噪声矩阵，并且．然后是组装的。从创建过程中，其排名不超过．

表中给出了半正定矩阵完备的计算结果2.．我们可以观察到，我们提出的求解器的性能与ADMM-VI一样好。两者都能产生令人满意的结果。

竞争利益

两位作者宣称他们没有相互竞争的利益。

致谢

作者要感谢文在文教授对矩阵补全的讨论。他们感谢袁晓明教授提供的ADMM-VI的原始代码。基金资助:国家自然科学基金资助项目(no. 5130459);2015 rcjj056)。

工具书类

1. E. J. Candés和B. Recht，“基于凸优化的精确矩阵补全”，计算数学基础，第9卷，第5期。6，第717-772页，2009。浏览：出版商的网站|谷歌学术搜索|MathSciNet
2. B.Recht，M.Fazel和P.A.Parrilo，“通过核范数最小化保证线性矩阵方程的最小秩解，”暹罗评论，第52卷，第3期，第471-501页，2010年。浏览：出版商的网站|谷歌学术搜索|天顶卫星数学|MathSciNet
3. Ji H.C.Liu，Z.Shen和Y.Xu，“使用低秩矩阵完成的鲁棒视频去噪”，年IEEE计算机视觉与模式识别会议论文集(CVPR’10)，页1791-1798,IEEE，旧金山，加利福尼亚，美国，2010年6月。浏览：出版商的网站|谷歌学术搜索
4. 蔡志辉、坎迪斯和沈志强，“矩阵完备的奇异值阈值算法，”暹罗优化杂志，第20卷，第4期，1956-1982页，2010年。浏览：出版商的网站|谷歌学术搜索|MathSciNet
5. Ma S.， D. Goldfarb, L. Chen，“矩阵秩最小化的不动点和Bregman迭代方法”，数学规划，第128卷，第1-2期，第321-353页，2011年。浏览：出版商的网站|谷歌学术搜索|MathSciNet
6. K.-C。Toh和S. Yun，“核范数正则化线性最小二乘问题的加速近端梯度算法”，太平洋优化杂志，第6卷，第3期，第615-640页，2010年。浏览：谷歌学术搜索|MathSciNet
7. 尹伟，“求解矩阵补全的低秩因子分解模型的非线性逐次超松弛算法”，数学规划计算，第4卷，第4期。4, pp. 333-361, 2012。浏览：出版商的网站|谷歌学术搜索|天顶卫星数学|MathSciNet
8. 法泽尔先生，矩阵秩最小化及其应用[博士论文]，斯坦福大学，斯坦福，加利福尼亚，美国，2002年。
9. D.Goldfarb，S.Ma和Z.Wen，“有效解决低秩矩阵完成问题”，在第47届Allerton通信、控制和计算年度会议记录（Allerton'09），第1013-1020页，美国伊利诺伊州蒙蒂塞洛，2009年9月。浏览：出版商的网站|谷歌学术搜索
10. E.J.Candés和T.Tao，“凸松弛的力量：接近最优矩阵完成，”IEEE信息论学报第56期5, pp. 2053-2080, 2010。浏览：出版商的网站|谷歌学术搜索|MathSciNet
11. 陈，何，袁，“通过交替方向法完成矩阵，”数值分析杂志，第32卷，第1期，第227-245页，2012年。浏览：出版商的网站|谷歌学术搜索|MathSciNet
12. M. Fortin和R. Glowinski，《增广拉格朗日方法》，刊于边界值问题数值解的应用，数学及其应用研究，北荷兰，阿姆斯特丹，荷兰，1983年，由B.Hunt和D.C.Spicer译成法语。浏览：谷歌学术搜索
13. 何伯斯，杨汉林，王世林，“单调变分不等式的带自适应惩罚参数的交替方向法，”最优化理论与应用杂志，第106卷，第2期，第337-356页，2000年。浏览：出版商的网站|谷歌学术搜索|天顶卫星数学|MathSciNet
14. Z.Wen，D.Goldfarb和W.Yin，“半定规划的交替方向增广拉格朗日方法，”数学规划计算，第二卷，第3-4号，第203-230页，2010年。浏览：出版商的网站|谷歌学术搜索|天顶卫星数学|MathSciNet
15. 邓文伟和尹文伟，“关于广义交替方向乘子法的全局收敛性和线性收敛性”，技术代表，莱斯大学CAAM，2012年。浏览：谷歌学术搜索
16. 徐耀华，尹文华，张耀华，“一种非负因子矩阵补全的交替方向算法，”中国数学前沿，第7卷，第2期，第365-3842012页。浏览：出版商的网站|谷歌学术搜索|天顶卫星数学|MathSciNet
17. Xu F.和G. He，“非负矩阵补全的新算法”，太平洋优化杂志，第11卷，第3期，第459-469页，2015年。浏览：谷歌学术搜索|MathSciNet
18. L.M.Briceño-Arias和P.L.Combettes，“对偶中复合单调包含的单调+斜分裂模型，”暹罗优化杂志第21卷第2期4, pp. 1230 - 1250,2011。浏览：出版商的网站|谷歌学术搜索|MathSciNet
19. R.Glowinski和P.Le Tallec，非线性力学中的增广拉格朗日和算子分裂方法第9卷暹罗应用数学研究，工业和应用数学学会，费城，美国宾夕法尼亚州，1989。浏览：出版商的网站|MathSciNet
20. B.He和X.Yuan，“可分离凸规划的带高斯反代换的乘法器线性化交替方向法，”数值代数、控制与优化，第3卷，第2期，第247-260页，2013年。浏览：出版商的网站|谷歌学术搜索

版权

版权所有©2016徐芳芳和潘鹏。这是一篇在知识共享署名许可协议，允许在任何媒介中不受限制地使用、分发和复制，前提是原作被正确引用。