符号矩阵填充的修正增广拉格朗日乘子算法

申倩影 ，王川龙

(工程科学计算山西省高等学校重点实验室 太原师范学院，晋中 030619)

0 引言

矩阵填充问题是一个引人注目的新研究领域，它的一个著名应用是Netflix系统，在图像恢复[1]，控制[2]，计算机视觉[3]，机器学习[4,5]等问题中都有非常重要的应用.

矩阵填充主要研究如何在数据不完整的情况下将缺失矩阵进行填充.大部分低秩矩阵(其数据分布在一个低维的线性子空间上)填充问题一般可以通过求解如下凸优化问题来实现：

min ‖X‖*

(1)

s.t.PΩ(X)=D

符号模式矩阵是组合矩阵论的一个新型研究分支，是近年来在组合数学中较为活跃的一个研究方向.符号矩阵[19]是指元素取自集合{+,-,0}或{1,-1,0}的矩阵.本文主要是对取值于集合{1,0}的符号矩阵的填充问题进行研究.符号矩阵的填充问题主要应用于生物医学领域.基因变异是指基因在结构上发生碱基对组成或排列顺序的改变，基因变异在临床疾病诊断和治疗、细菌和疫苗中都有重要的研究意义，而这种变异可以用单倍体(染色体的单核苷酸多态性) 来识别，单倍体含有本物种配子染色体数及其全套染色体组，也就是有生活必需的全套基因，而每条单倍体可以看作是由{1,0}所组成的符号序列.然而，由于硬件的限制，单倍体不能被完全观测，只能得到一部分信息.如何从已知的部分信息来得到完整的单倍体信息就需要通过求解符号矩阵的填充问题来实现.

本文结构安排如下：第1节首先回顾已有的对一般矩阵填充的ALM算法，然后详细介绍针对符号矩阵填充的SM-ALM算法和GA算法；第2节给出了SM-ALM算法的收敛性分析；第3节通过数值实验给出了SM-ALM算法和GA算法对符号矩阵填充的结果；最后在第4节对全文进行总结.

1 算法

首先回顾已有的对一般矩阵填充的ALM算法：

1.1 矩阵填充的ALM算法

ALM算法[7]解决以下凸优化问题：

min ‖A‖*

(2)

s.t.A+E=D,PΩ(E)=0

其Lagrange函数为：

(3)

其中Y∈Rn1×n2.

算法1(ALM算法)

第0步：给定下标集合Ω，样本矩阵D，参数μ0>0，ρ>1,以及初始矩阵Y0=0,E0=0,k=0;

第2步：令

第3步：通过给定参数，若‖D-Ak+1-Ek+1‖F/‖D‖F<ε1，并且μk‖Ek+1-Ek‖F/‖D‖F<ε2，停止；否则，转第4步；

第4步：令Yk+1=Yk+μk(D-Ak+1-Ek+1)，如果μk‖Ek+1-Ek‖F/‖D‖F<ε2，令μk+1=ρμk；否则，转第1步.

1.2 符号矩阵填充的算法

在总结现有算法的基础上，提出针对符号矩阵填充问题的算法.

1.2.1 修正的ALM算法(SM-ALM算法)

符号矩阵的填充问题可以描述为以下凸优化问题：

min ‖A‖*

(4)

s.t.A+E=D,PΩ(E)=0

其Lagrange函数为：

(5)

其中A,D,E都是符号矩阵，Y∈Rn1×n2.

算法2(SM-ALM算法)

第0步：给定下标集合Ω，样本矩阵D，参数μ0>0，ρ>1,以及初始矩阵Y0=0,E0=0,k=0；

第2步：令

第3步：令

第4步：通过给定参数，若‖D-Ak+1-Ek+1‖F/‖D‖F<ε1，并且μk‖Ek+1-Ek‖F/‖D‖F<ε2，停止；否则，转第5步；

第5步：令Yk+1=Yk+μk(D-Ak+1-Ek+1)，如果μk‖Ek+1-Ek‖F/‖D‖F<ε2，令μk+1=ρμk；否则，转第1步.

算法2在进行奇异值分解之后，根据矩阵的均值进行投影，然后进行填充，这样可以保证每次产生的迭代矩阵都保持符号矩阵的结构.

1.2.2 遗传算法

遗传算法(GA)[20]是计算机科学人工智能领域中用于解决最优化的一种搜索启发式算法，是进化算法的一种.它是美国的J.Holland教授1975年提出的，这种启发式通常用来生成有用的解决方案来优化和搜索问题.进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等.遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优.

下面我们提出针对符号矩阵填充的遗传算法.

算法3(GA算法)

第0步：给定下标集合Ω，样本矩阵D，参数ε,交叉概率，变异概率；

第1步：给定种群大小，根据采样率计算染色体长度，生成种群pop(其中元素为1，0)；

第3步：对pop中每一个个体进行选择，得到新种群newpop；

第4步：对新种群newpop进行交叉，变异得到newpop1；

第7步：比较newpop1中每一个个体适应度的大小，选出最优个体.

2 收敛性分析

本节讨论算法2的收敛性.

引理1[21]奇异值分解(SVD)秩为r的矩阵X∈Rn1×n2，则必存在正交矩阵U∈Rn1×r和V∈Rn2×r，使得X=UΣrVT，Σr=diag(σ1，…，σr)，其中σ1≥σ2≥…≥σr>0.

引理 2[22](奇异值阈值算子) 对于任意参数τ≥0，秩为r的矩阵X∈Rn1×n2，存在奇异值分解X=UΣrVT，奇异值阈值算子Dτ定义为：

Dτ(X)=UDτ(Σ)VT,Dτ(Σ)=diag({σi-τ}+)

其中：

证明

Yk=Yk-1+μk-1(D-Ak-Ek)=

证明

Yk=Yk-1+μk-1(D-Ak-Ek)

由引理4知，当k充分大时，有D-Ak-Ek=0.由定理1知，Ak是问题(5)的解.

3 数值实验

在本节中，通过数值实验比较SM-ALM算法与GA算法.

表1 小矩阵的计算结果(使用MALM算法)

表2 大矩阵的计算结果(使用MALM算法)

表3 使用GA算法对符号矩阵进行填充

4 总结

在本文中，使用SM-ALM算法和GA算法来填充符号矩阵，结果表明SM-ALM算法是可行的，并能在很短的时间和很少的迭代步数内找到精确的解.而使用 GA 算法只能经过有限步迭代输出结果，降低误差，不能达到收敛的效果，更找不到精确的解.