汪丽琴，喻高航，张亮亮

(杭州电子科技大学理学院，浙江 杭州 310018)

0 引 言

1 低秩矩阵填充模型

(1)

式中，δ表示对Z的秩的假设置信度，通常取某个正整数。模型(1)综合考虑了无噪音和有噪音的情况。由于秩函数是非凸且非连续的，计算模型(1)十分困难。Fazel[5]证明核范数在单元球上是秩的最紧凸松弛替代，随后，Candès和Recht[6]提出使用矩阵核范数代替秩来解矩阵填充问题，得到模型：

(2)

2 Frank-Wolfe算法

(3)

给出Frank-Wolfe算法。

算法1 用于解决问题(3)的标准Frank-Wolfe算法输入:x0∈,最大迭代步数K 当k=1,2,…,K时,(1)计算sk-1=argmins∈(2)搜索方向dfw=sk-1-xk-1(3)更新xk=xk-1+γdfw,其中γ∈[0,1]输出:xK

针对步骤3中步长的选取，本文使用精确线搜索策略，即γ=argminγ∈[0,1]f(xk+γdfw)。

由于核范数的对偶范数是算子范数，即‖Y‖=max‖X‖*≤1〈X,Y〉，因此最优化问题

minX〈X,Y〉 s.t.‖X‖*≤1

2.1 CGS算法

Lan等[8]使用Nesterov加速方法，提出FW算法的改进算法CGS。

算法2 FW算法的变体CGS算法输入:x0∈,最大迭代步数K 取βk∈R++,γk∈[0,1],和ηk∈R+,k=1,2,…,令y0=x0 当k=1,2,…,K时,(1)计算zk=(1-γk)yk-1+γkxk-1(2)计算xk=CndG f'(zk),xk-1,βk,ηk (3)更新yk=(1-γk)yk-1+γkxk输出:yK 子程序xk=CndG f'(zk),xk-1,βk,ηk 的步骤如下:(1)初始化g=f'(zk),u=xk-1,β=βk,η=ηk(2)令u1=u和t=1(3)令vt为子问题Vg,u,β(ut)maxx∈的最优解(4)如果Vg,u,β(ut)≤η,则令xk=ut,并跳转到步骤7,否则,进入步骤5(5)令ut+1=(1-αt)ut+αtυt,其中αt=min1,<β(u-ut)-g,υt-ut>β‖υt-ut‖2 (6)令t=t+1,并跳转到步骤3(7)返回xk

2.2 In-Face步骤

对于矩阵填充问题，FW算法的一个不足之处在于其中间解决方案的秩通常稳定增长，并在终止时产生一个高秩的解决方案，这对于大规模问题[13]可能在时间和空间成本上非常昂贵。

随后，Freund等[9]提出加In-Face步骤的拓展FW算法IF-(0,∞)，In-Face步骤是远离步骤的推广，远离步骤的具体细节见文献[14-15]。In-Face步骤沿着包含当前迭代的最小面选择最佳下降方向，通过沿着最小面移动到可行域的边界以达到低维面。该算法保持了低秩结构，且不会影响收敛。对于问题(2)，如文献[9]所述，包含点Xk核范数球NN(0,δ)的最小面由下列集合给出：