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

王俊霞, 申倩影, 王川龙

(太原师范学院数学系，晋中 030619)

1 引言

矩阵填充主要研究如何通过已知的部分矩阵元素来恢复一个低秩矩阵.矩阵填充在图像恢复[1]、控制[2]、计算机视觉[3]、机器学习[4,5]等领域中都有非常重要的应用.由于秩的不连续性，低秩矩阵填充问题通常被松弛为一个凸优化问题

符号矩阵[16]是指元素取自集合{1,-1}或{1,-1,0}的矩阵.本文主要是对取值于集合{1,-1}的符号矩阵进行研究.一个n×n的符号矩阵T有如下形式

显然，T是一个由1,-1 元素组成的符号矩阵.这类矩阵的填充问题在生物医学等领域有着很好的应用前景.基因变异的研究是疾病识别和药物开发的关键，这种变异可以用单倍体(染色体的单核苷酸多态性)来识别.每条单倍体可以看作由{1,-1}所组成的符号序列.然而，由于硬件的限制，单倍体不能被完全观测，只能得到一部分信息.如何从有限的信息恢复出完整的单倍体就需要用符号矩阵的填充来解决.

遗传算法(GA)[17]是一类借鉴生物界的进化规律(适者生存，优胜劣汰的遗传机制)演化而来的随机化搜索方法.它是美国的Holland 教授于1975 年提出的，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的界定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则.遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优.

针对符号矩阵的填充问题，本文基于奇异值阈值算法和增广Lagrange 乘子法提出了修正的增广Lagrange 乘子法(MALM)和遗传算法(GA).与传统的ALM 算法相比，MALM 算法每步产生的阈值矩阵都为符号矩阵，并讨论了算法的收敛性，同时通过数值试验与ALM 算法和GA 算法进行比较，验证MALM 算法的有效性.

首先给出一些定义和引理：

引理1(奇异值分解SVD)[18]秩为r的矩阵X ∈Rn1×n2，则必存在正交矩阵U ∈Rn1×r和V ∈Rn2×r，使得

其中σ1≥σ2≥···≥σr ＞0.

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

其中

本文结构安排如下：第2 节首先回顾已有算法，然后介绍符号矩阵的MALM 算法和遗传算法；第3 节给出了MALM 算法的收敛性分析；第4 节通过数值实验来比较MALM 算法和ALM 算法、遗传算法对符号矩阵填充的结果；最后在第5 节对全文进行总结.

2 算法

为保证文章的完整性及收敛性证明的需要，我们首先对已有算法进行简单回顾.

2.1 矩阵填充的ALM 算法

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

其Lagrange 函数为

其中Y ∈Rn1×n2.

算法1 ALM 算法

第0 步 给定下标集合Ω，样本矩阵D ∈Rn1×n2，参数μ0＞0, ρ ＞1, ϵ1,ϵ2＞0 以及初始矩阵Y0=O, E0=O, k:=0；

第3 步 通过给定参数，若

停止；否则，转第4 步；

第4 步 令Yk+1=Yk+μk(D-Ak+1-Ek+1).如果μk‖Ek+1-Ek‖F/‖D‖F ＜ϵ2，令μk+1=ρμk, k:=k+1，转第1 步.

2.2 符号矩阵填充的新算法

在总结现有研究基础上，我们提出符号矩阵填充问题的新算法.

2.2.1 修正的ALM 算法

由于我们是对符号矩阵进行填充，算法1 在填充结束之后所形成的矩阵是Rn1×n2中的矩阵，虽然能达到误差要求，但不一定能落入中.因此，我们给出了修正后的ALM 算法(MALM 算法).

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

其中A,D,E ∈.

其Lagrange 函数为

其中Y ∈Rn1×n2.

算法2 MALM 算法

停止；否则，转第5 步；

第5 步 给定参数，令Yk+1=Yk+μk(D-Ak+1-Ek+1).如果μk‖Ek+1-Ek‖F/‖D‖F X ＜ϵ2，令μk+1=ρμk, k:=k+1，转第1 步.

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

2.2.2 符号矩阵填充的遗传算法

下面我们提出符号矩阵填充的遗传算法(GA 算法).

算法3 GA 算法

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

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

3 收敛性分析

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

证明

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

4 数值实验

4.1 实验细则

本文是针对符号矩阵(取自元素-1,1)填充问题进行研究，在此说明一下实验过程中采样矩阵的生成方式，所采用的矩阵秩的选取规则以及对ALM 算法的补充.

1) 采样矩阵的生成方式

2) 矩阵秩的选取规则

在生成矩阵M的实验中，我们发现：当矩阵P和Q的秩为r时，矩阵M的秩为2r-1，当r取奇偶数时，矩阵的元素也会出现不同的结果，具体如下：

① 当r取奇数时，填充矩阵A只包含元素1,-1，与本文研究内容相符；

② 当r取偶数时，填充矩阵A包含元素1,0,-1，与本文研究内容不符.

3) ALM 算法的补充

由于用ALM 算法填充出来的是Rn1×n2中的矩阵，虽然满足误差要求，但不一定是符号矩阵，因此，在ALM 算法的最后一步，我们将迭代完毕后的矩阵投影到中，然后和MALM 算法进行比较.

4.2 实验结果

在本节中，通过数值实验将MALM 算法与ALM 算法和GA 算法进行比较.

表1 和表2 是MALM 算法和ALM 算法的比较，从实验数据可以看出，当矩阵达到一定规模时，ALM 算法是收敛的，并且误差能达到0，但和MALM 算法作对比，无论是迭代步数还是收敛时间，MALM 算法都具有很强的优势；使用遗传算法进行填充，当采样矩阵规模过大，例如矩阵大小为1000，采样率为0.2 时，染色体长度为800000，选取个体数为20，生成的初始种群为800000×20 的矩阵，由于计算机硬件的限制，程序运行不出来.因此，表3 给出了小规模矩阵的运行结果，但仍然不理想，达不到收敛效果.但和初始误差相比，经过有限步，误差会相对减少.

表3 使用GA 算法的实验结果

表2 MALM 算法与ALM 算法比较(秩为64)

表1 MALM 算法与ALM 算法比较(秩为16)

5 总结

在本文中，我们给出了符号矩阵填充的MALM 算法和GA 算法.MALM 算法以奇异值阈值算法为基础，对ALM 算法进行修正，保证迭代矩阵始终在解空间上.与ALM 算法相比，MALM 算法从迭代步数和收敛时间上都有着很强的优势.而GA 算法只能相对减少误差，还不能达到收敛，更找不到确切的解.对含有0 的符号矩阵的填充问题将是我们下一步工作的重点.

续表2 MALM 算法与ALM 算法比较(秩为64)