余宏伟 蒋轶

摘 要： 多年来矩阵恢复一直是学术界的一个热门研究课题，它被广泛应用于多个技术领域，如计算机视觉、图像恢复以及推荐系统等。考虑其中一种特殊且十分重要的矩阵恢复，即半正定矩阵恢复。通过将此类矩阵恢复问题与基于测距的网络定位问题类比，构造了基于最小二乘的优化模型，运用顺序凸规划（sequential convex programming/SCP）算法，可以高效并精确地求解此问题，从而将缺失矩阵较为精准地还原为全矩阵。仿真结果证明相比于目前文献中已有矩阵恢复算法，提出的算法具有更好的恢复性能。

关键词： 低秩矩阵;半正定矩阵;核范数最小化;最小二乘法;顺序凸规划

中图分类号： TN92

文献标志码： A

文章编号：1007-757X（2019）06-0001-03

Abstract： Matrix completion has been an active topic for more than a decade in academic research due to its widely applications in many fields， such as computer vision， image recovery and recommendation system. In this paper， we study a special and important case， low-rank positive semi-definite （PSD） matrix completion. By linking the matrix completion problem to a network localization problem， we propose an optimization model based on the least square criterion. Using the sequential solution programming （SCP） algorithm， we can efficiently reconstruct the PSD matrix with high precision. Simulation results show that the proposed method has more superior performance than the state-of-art algorithms.

Key words： Low-rank matrix; PSD matrix; Nuclear norm minimization; Least square; Sequential solution programming

0 引言

矩阵恢复技术要求能够从部分甚至是受到噪声污染的矩阵元素观测中精确地还原整个矩阵。在具有里程碑意义的论文[1]中，Candes等人证明，如果某矩阵是一个低秩矩阵，且其中被观测到的元素集合满足一定的条件，那么通过一个简单的凸规划，就可以以较高的概率将其恢复。矩阵恢复的应用范围非常广泛，如计算机视觉、图像恢复、定位[2]、推荐系统（Netflix）等等。

Candes等人提出通过最小化核范数的方法来恢复整个矩阵[1、3]。特别地，在满足一定非相干条件的情况下，最小化核范数法可以逼近最优解[4]。[1]中应用半正定规划解算器SDPT3求解核范数最小化问题，该计算正如SeDuMi一样都是基于内点法，当矩阵规模很大时需要求解一个巨大的线性方程组计算牛顿方向，一般来说当矩阵维度大于100时，SDPT就无能为力了[5]。……