论文部分内容阅读
本文主要研究的是如下的低秩矩阵完整化问题,或称之为秩最小化问题：min rank(X)(1) s.t. Xij=Mij,(?)(i,j)∈Ω,及其较一般的情形：min rank(X)(2) s.t. A(X)=b.这个问题在统计,图像处理,计算几何,机器学习,信号处理,模型控制等方面有广泛应用,比如著名的Netfilx大奖赛问题.而它的一个特殊情形,即当变量是向量时,问题就转化为求解稀疏向量的问题,与近年来大家感兴趣的压缩感知问题有很大关系.因此,研究这个问题有很重要的实际意义.本篇文章对这个问题做了系统的综述讨论,主要工作如下：(1).由于该问题是一个N-P难题,我们总结了该问题在什么样的情况下是可以解决的.要将一个矩阵恢复完整,我们说明了当矩阵M满足一定条件,且已知的元素个数不能太少时,此时在较大概率下矩阵M是可以恢复出来的.然后由于直接求解难度很大,往往用核范数最小化问题去逼近秩最小化问题.文章里给出了用核范数去逼近该问题的理论依据,现有的大多数算法都是基于近似求解如下的核范数最小化问题：min||X||*(3) s.t.Xij=Mij,V(i,j)∈Ω.(2).总结了现阶段已有的几种算法,主要强调的是这些方法产生的理论基础,奇异值阈值法和不动点连续性算法,都是通过核范数最小化问题来近似给出秩最小化问题的解,不动点连续性算法是直接求解核范数最小化问题,而奇异值阈值法是求解问题：min τ||X||*+1/2||X||F2(4) s.t. pΩ(X)=pΩ(M),来逼近核范数最小化问题的解.逐行法是有效利用了半定规划的一些好的性质,对偶规划问题则是基于交替方向增广拉格朗日乘子法.(3).本文从另一个角度给出了秩最小化问题的一种方法,我们不用核范数去逼近秩最小化问题,而是考虑问题：min Tr(XTX)(5) s.t. Xij=Mij,(?)f(i,j)∈Ω.对于这个问题,它也可以比较有效地去逼近秩最小化问题,我们基于替方向增广拉格朗日乘子法,也给出了相应的算法.