仿射秩最小化问题的一种解法❋

王展梁，刘新国

(中国海洋大学数学科学学院，山东 青岛 266100)

近年来，基于仿射变换下的低秩矩阵恢复问题在协同过滤[1]、图像处理[2]、量子成像[3]等多个领域有重要应用，发展求解此问题的高效数值解法是当前数值最优化领域的研究热点之一。仿射秩最小化问题是指下述矩阵最优化问题

(1)

或者其拉格朗日形式

(2)

式中：X∈Rm×n为要恢复的目标矩阵;b∈Rp为观测数据;A：Rm×n→Rp为仿射变换;参数ε≤0反映噪声水平；λ>0为正则化参数。当仿射变换A为矩阵的取样算子时，仿射秩最小化问题就转化为矩阵填充问题[4]。

Wen等[7-9]提出了一种基于矩阵分解的建模方法，避免了对矩阵进行奇异值分解，但事先需要对矩阵的秩进行合理的预测。Mohan等[10]利用矩阵的Schatten-p范数来代替秩函数，提高了模型的恢复能力。本文用下述新的松弛模型来求解秩最小化问题

(3)

其中γ≤1，并且发展了模型(3)的数值解法，证明了数值算法的收敛性，数值实验表明了模型(3)相较于核范数模型的优越性。

1 算法

下述引理用于得到模型(3)的等价形式。

引理1设X∈Rm×n，γ≤1，则

(4)

证明 由矩阵行列式的性质可知

由引理1，可得到模型(3)的如下等价形式

(5)

定义1对于下半连续的正常函数g(x)：R→R及α>0，其邻近算子Proxαg：R→R定义如下：

(6)

在本文中，我们讨论y为矩阵奇异值的情况，因此只需要对y≤0进行考虑。下面的三个定理给出了模型(5)中罚函数的邻近算子的相关性质及其显式表达式。

定理1设g(x)=log(x+γ)，γ≤1，α>0，g(x)的邻近算子满足如下性质：

①∃c>0，∀y∈[0,c]，Proxαg(y)=0。

②当y→+时，对∀z∈Proxαg(y)，有z→+且

③当y1

②当y→+时，对∀z∈Proxαg(y)，z必为f(x)的一个驻点，即由于则，并且

③当y1

(z2-y2)(y2-y1)

对上述不等式化简可得z1

(7)

(8)

图1 log(x+γ)的邻近算子在γ=1，α=0.8时的图像

图2 log(x+γ)的邻近算子在γ=1，α=2时的图像

设UDiag(σ)VT为X的奇异值分解，由邻近算法[11]中的结论可知有ProxαG(X)的一个显式解为

ProxαG(X)=UDiag(Proxαg(σ1),…,Proxαg(σd))VT。

(9)

(10)

式中A*是A的共轭算子，μ>λmax(A*A)/2，λmax(A*A)/2为A*A的最大特征值。

由(9)式我们得到迭代算法

(11)

令

下面的定理给出了上述算法的收敛性。

定理4设μ>λmax(A*A)/2，则由PGA算法得到的序列{Xk}具有如下性质：

①{F(Xk)}单调递减并收敛。

证明 ①由(10)式可得

(12)

将Xk+1带入上式，则

(13)

由式(12)和(13)可得

则

因为μ>λmax(A*A)/2，结论①得证。

2 数值实验

在本节中，我们通过矩阵填充问题来验证模型(3)的有效性和算法的可行性。算法中涉及到的奇异值分解利用PROPACK[12]计算。

在无噪声的情况下，我们模拟模型和算法的恢复能力。假定采样率为50%，X=X1X2为目标矩阵，其中X1∈R200×r，X2∈Rr×200为元素服从均值为0，方差为1的正态分布的随机矩阵，整数r为矩阵的秩，其变化范围为25～50。设X*为算法得到的解，当相对误差满足

则视为恢复成功。对每个r重复100次实验，设恢复成功的次数为Sr，则定义恢复概率为Sr/100。我们将PGA算法与采用核范数的IADM[13]算法进行比较。由于侧重比较模型的恢复能力，我们希望算法能够得到充分迭代，因此设置停机准则为

由图3可以看出，当r≤29时，PGA和IADM算法都能够恢复成功；当r>32时，IADM算法恢复失败；而当r≤42时，PGA算法仍可恢复成功。

图3 无噪声情形下的矩阵填充结果

PGA算法亦适用于含噪声情况。假定采样率和目标矩阵X的构造与上述实验相同，令Xnoise=X+0.1×E，其中E为元素服从均值为0，方差为1的正态分布的随机矩阵。然后对Xnoise进行采样，矩阵的秩r变化范围为25～50。我们对每个r做20次实验得到其平均误差，并同IADM算法进行了对比。由图4可以看出当r≤30时，IADM算法相对误差高于0.05，且相对误差逐渐增大，而PGA算法在r≤43时，相对误差仍在0.05以下。

图4 有噪声情形下的矩阵填充结果

3 结语

本文提出了一种矩阵秩最小化问题的松弛模型，并给出了邻近梯度下降算法，证明了算法的收敛性。通过实验表明，模型的恢复能力要高于核范数松弛，是求解原问题的一种好的模型，且在有噪声污染的情况下，算法的表现也优于核范数松弛，本研究为解决实际问题提供了一种新的途径。