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

太原 师范学 院学报(自然科学版)

JOURNAL OF TAIYUAN NORMAL UNIVERSITY (Natural Science Edition)

Vol. 18 No. 4Dec. 2019符号矩阵填充的修正增广拉格朗日乘子算法申倩影，王川龙(工程科学计算山西省高等学校重点实验室太原师范学院，晋中030619)〔摘要〕 以增广Lagrange乘子算法为基础，通过对阈值矩阵进行投影，提出修正的增广La­

grange 乘子算法.新方法保证每次迭代产生的矩阵是可行的符号矩阵.同时给出新算法的收敛性

分析.最后通过数值实验说明了新的算法在时间和误差上比传统的遗传算法更有效，误差能够达Y

零，达到精确恢复的效果.〔关键词〕矩阵填充；符号矩阵；增广Lagrange乘子算法；遗传算法〔文章编号〕1672-2027(2019)04-0006-06

〔中图分类号〕O151. 21 〔文献标识码〕A0引言矩阵填充问题是一个引人注目的新研究领域,它的一个著名应用是Netflix系统,在图像恢复［1］,控

制⑵,计算机视觉,机器学习［，5］等问题中都有非常重要的应用.矩阵填充主要研究如何在数据不完整的情况下将缺失矩阵进行填充.大部分低秩矩阵(其数据分布在一

个低维的线性子空间上)填充问题一般可以通过求解如下凸优化问题来实现：min

|| X ||*

(1)st Fn(X) — 犇其中，核范数|| X ||*二 匕k(X炖k(X)是矩阵XGRn\"的第犽大的奇异值,DGRn1Xn2 ,Q是已知元素

k-1的下标集合.针对矩阵填充问题的算法研究已有较为丰富的成果,Toh和Yun提出了复杂度为1的加速临

槡近梯度法(accelerated proximal gradient , APG)［］ , Cai 等人提出了奇异值阈值算法(singular value threshol­

ding ,SVT)［7］ , Lin等人提出了增广拉格朗日乘子算法(augmented Lagrange multiplier , ALM)［］等，更多算

法可见文献［15］,并通过数值实验证明了 ALM算法在收敛速度和精确度方面比APG算法和SVT算法有

更好的结果.除了以上提到的这些算法,一些学者还研究了噪声下的矩阵填充问题［16］,加速的奇异值阈值 法［17］,无奇异值分解的快速奇异值阈值法［18］等多种算法.符号模式矩阵是组合矩阵论的一个新型研究分支，是近年来在组合数学中较为活跃的一个研究方向.符

号矩阵［19］是指元素取自集合｛ + , —,0｝或｛1,—1,0｝的矩阵.本文主要是对取值于集合｛1,0｝的符号矩阵的

填充问题进行研究.符号矩阵的填充问题主要应用于生物医学领域.基因变异是指基因在结构上发生碱基对

组成或排列顺序的改变，基因变异在临床疾病诊断和治疗、细菌和疫苗中都有重要的研究意义，而这种变异 可以用单倍体(染色体的单核昔酸多态性)来识别，单倍体含有本物种配子染色体数及其全套染色体组，也

就是有生活必需的全套基因，而每条单倍体可以看作是由｛,0｝所组成的符号序列.然而，由于硬件的, 单倍体不能被完全观测，只能得到一部分信息.如何从已知的部分信息来得到完整的单倍体信息就需要通过 求解 矩阵的 问题来 ．本文结构安排如下:第1节首先回顾已有的对一般矩阵填充的ALM算法,然后详细介绍针对符号矩阵 填充的SM-ALM算法和GA算法;第2节给出了 SM-ALM算法的收敛性分析;第3节通过数值实验给出了

SM-ALM算法和GA算法对符号矩阵填充的结果；最后在第4节对全文进行总结.收稿日期:2019-09-19作者简介：申倩影(1996-),女，山西晋城人，太原师范学院数学系在读硕士研究生，主要从事矩阵数据分析与科学计算研究.第4期申倩影，等：符号矩阵填充的修正增广拉格朗日乘子算法7为方便起见，R”1x”2表示n X\"2的实矩阵全体，广(X)表示矩阵X的秩，X犻表示矩阵X位于(犼)的元 素，|| X || f, || X ||*分别表示矩阵X0F范数和核范数，通常用〈X,Y〉=\"ace(XTY)表示矩阵X和矩阵Y的内积(即有|| X ||犉=〈X,X〉)，集合Q表示采样矩阵X的已知元素下标集合，满足:Pq(X)—X,(i,j) G Q0,(,) & Q1算法首先回顾已有的对一般矩阵填充的ALM算法：1.1矩阵填充的ALM算法ALM算法⑺解决以下凸优化问题：min || A ||*

s. t. A + E = D, Pq (,E) = 0(2)其 Lagrange函数为：L(A,E,Y,) = ||A||* +〈Y,D —A —E〉+ 2 || D —A —E | F

其中 YGR\"1Xn2.算法1(ALM算法)(3)第0步：给定下标集合Q,样本矩阵D,参数眇〉0,p〉1,以及初始矩阵Y°-0,E°-0,-0；第1步:计算矩阵(D —Ek+“—Yk)比Q 大的奇异值，[Uk,6,Vk] — svd(D —Ek+“—Yk)第2步:令Ak+1 — UkDk (6)VT ,Ek+1 — P^CD — Ak+1 +“—Yk)第3步：通过给定参数，若|| D-Ak+1—Ek+1 ||犉/ || D || fVs并且冷|| Ek+1—Ek ||犉/ || D ||犉＜◎,停 止;否则，转第4步；第 4 步：令 Yk+1 — Yk + p.k (D—Ak+1 — Ek+1),如果 “k || Ek+1 — E» || 犉/ || D || 犉＜$2,令 p-k+1 — pp-k;否则，转

第1步•1.2符号矩阵填充的算法在总结现有算法的基础上，提出针对符号矩阵填充问题的算法.1.2.1 修正的ALM算法(SM-ALM算法)符号矩阵的填充问题可以描述为以下凸优化问题：min || A ||*

s.t. A + E = D ,Pq (E) = 0(4)其 Lagrange 为：L(A,E,Y 屮)—||A||* +〈Y,D —A —E〉+ 2 || D —A —E | F

(5)其中A，犇 ,E都是符号矩阵,YGR”1x”2.算法2(SM-ALM算法)第0步：给定下标集合Q,样本矩阵D,参数“〉0,p〉1 ,以及初始矩阵Y°-0, Ee-0k-0； 第1步:计算矩阵(D — Ek+P—1Yk)比大的奇异值，[Uk ,Sk 犞k] — svd(D —Ek+p—Yk)第2 步： 令Ak+1 — UD-1 (tk)Vl8 太原师范学院学报（自然科学版） 第18卷第3步:令a = mean （mean（A'k+1））犃*+1 = if a > 0{J01 ,, if a0

犼1犼 < Ek+1 = P^n （.D — At_+1 +“k1Vk）第 4 步：通过给定参数，若 I D — Ak+1—Ek+1 I f/ I D I f<6 ,并且冷 I Ek+1—Ek I f/ I D I f<6,停 止;否则，转第5步；第 5 步：令 Yk+1 ~Yk + /j.k （D—At_+1 一Ek+1）如果侔 I Ek+1 一Ek I f I D I 犉<6,令 “k+1 =p“k;否则，转

/第1 步．算法2在进行奇异值分解之后，根据矩阵的均值进行投影，然后进行填充，这样可以保证每次产生的迭 代矩阵都保持符号矩阵的结构.1. 2. 2遗传算法遗传算法（GA）20]是计算机科学人工智能领域中用于解决最优化的一种搜索启发式算法，是进化算法 的一种.它是美国的J. Holland教授1975年提出的，这种启发式通常用来生成有用的解决方案来优化和搜 索问题.进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择

以及杂交等.遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优.下面我们提出针对符号矩阵填充的遗传算法.算法3（GA算法）第0步:给定下标集合O,样本矩阵D,参数6交叉概率，变异概率；第1步：给定种群大小，根据采样率计算染色体长度，生成种群pop（其中元素为1,0）；第2步:将pop中每一个个体代入d中（O的元素），计算” m犕;犉，得到适应度值；第3步:对pop中每一个个体进行选择，得到新种群newpop；第4步:对新种群newpop进行交叉，变异得到newpop1 ；第5步:将newpop1中每一个个体代入D中（O的元素），计算1 |犕犕|犉；第6步:若1 |犕犕|犉<6停止'否则'将newpop1赋给pop,重复以上步骤；第7步：比较newpop1中每一个个体适应度的大小，选出最优个体.I2收敛性分析本节讨论算法2的收敛性.

引理1[1]奇异值分解（SVD）秩为狉的矩阵XGR\"1x\"2，则必存在正交矩阵UGR\"1\"和VGR”2\使得

X = U2”VT ,^r = diag（1 ,…，,），其中,>,2>…>,狉〉0.引理2[2]（奇异值阈值算子）对于任意参数t>0,秩为狉的矩阵XGR\"1x\"2，存在奇异值分解X =

U2rVT ,奇异值阈值算子D定义为：tDX） = UDt（.2）Vt DO = dtag（{ffl—r} +）t其中：,—T}+ =一 T, if ,〉T {]0 ,.「” , f ,T W 为方便起见,将算法1中的犃k Ek 犢k分别记为犃瓦工.引理3序列{犢j是有界的，其中犢k二犢二1+jk—1（D—犃T—瓦二）.第4期申倩影,等：符号矩阵填充的修正增广拉格朗日乘子算法9引理 4 若 || Pq(D—Ak) || fW || Pq(D—Ak) || f ,则序D{Yk}是有界的.证明Yk — Yk—1 + “k—1(,D — Ak — E—) •由引理3知,Yk有界，“一 + *(— *),则对每个犻,存在MGR+ ,有|| D—A—E || VM,即|| Pq (D —A,) || 犽—1另“犻(D — A, — E,) — K“Pq(D —A»0 0

由于 || Pn(D—At) || fW || Pn(.D—A，) || f 及Y有界，推得 Yk 有界.

定理1若冷是不减的,§ P—1-+* ,则A收敛到问题(3)的最优解A •k=1k定理2若*,工;“一1 =+ * ,则当犽充分大时,Ak为问题(5)的解•,—1证Yk — Yk— + pk— CD — Ak — Ek)

\"(Yk—Yu) =D — Ak—Ek由引理4知，当犽充分大时,有D—Ak—E»-0.由定理1知,Ak是问题(5)的解•3数值实验在本节中，通过数值实验比较SM-ALM算法与GA算法.在实验中,犕表示采样矩阵,A表示输出的最优解，狆一^^ 表示采样率,其中m表示观察到符号矩阵

n x n的元素个数,n Xn表示采样矩阵的全部元素个数,设置参数(参考文献[8] £1-2犲一4,£2-1幺一5,t-

,5-1. 217 2 + 1. 858 8X^^.这里所有的数值实验均是在相同的工作环境下进行的,也就是在比

较实验中所取的矩阵犕和Pq(M)具有相同数据.表1小矩阵的计算结果(使用MALM算法)大小/n * n秩/狉采样率/狆迭代次数/ ^iter时间/s||A—犕||犉||犕||犉50070215193 31814 30060000000000000000 150 25800702418119 00765 06027 37300 150 25100028111131716 188211 470612 274930 32157020 150 25150070216 178623 153418 801157 85150 150 25971120007020 150 253417166 742785 066710太原师范学院学报（自然科学版）第18卷表2大矩阵的计算结果（使用MALM算法）大小/\"- ”秩/狉采样率/Q迭代次数/ ^iter时间/sIIa—mIIMIIff30007020．150．253500109181．4972171．6888139．1407286．1694275．1296293．1384442．8448471．129100000000000000071091071177020．150．2540007020．150．2580007027106327．582. 4 6e+033. 359 8e+030．150．25100002．1396e+035．2420e+035．3592e+037028860．150．254．1298e+03表3大小/\"- ”秩/狉采样率/Q使用GA算法对符号矩阵进行填充迭代次数/井犻rr起始误差时间/s0．99971．9762II 犃一MIIfIMIIf502005007777704040404043150．74270．71350．72370．7209 0．7223

0．74210．71280．72360．72080．722342316.543 5105．8402382．6559200030004总结在本文中，使用SM-ALM算法和GA算法来填充符号矩阵，结果表明SM-ALM算法是可行的，并能在 很短的时间和很少的迭代步数内找到精确的解.而使用GA算法只能经过有限步迭代输出结果，降低误差,

不能达到收敛的效果，更找不到精确的解.参考文献：[1]

BERTALMIO M,SAPIRO G,CASELLES V,et al. Image inpaiting. In：Proceedings of the 27th Annual Conference on Com­puter Graphics and Interactive Techniques]A]. New York.： ACM,2000,417-424MESBAHI M,PAPAVASSILOPOULOS G P. On the rank minimization problem over a positive semidefinite linear matrix

inequality[]. IEEE Trans Automat Control ,1997,42： 236-243[3]

TOMASI C, KANADE T. Shape and motion from image streams under orthography： A factorization method]〕]. Int J Com- put Math Vision, 1992,9： 137-154[4] AMIT Y, FINK M,SREBRO N,et al. Uncovering shared structures in multiclass classification [A]. In： Processings o! the 24thInternationalConferenceon Machine Learing．New York：ACM,2007,17-24[5] [6]

ARGYRIOU A,EVGENIOU T, Mul-task feature learning[J]. Adv Neural Inf Process Sy st ,007,19 ： 41-48TOH K C,YUN S. An accelerated proximal gradient algorthm for nuclear norm regularized least squares problems]〕]. Pa-

cificJ．Optimi,2010,6：615-0[7]

CAI J F, CANDES E J ,SHEN Z. A singular value thresholding algorithm for matrix completion]J]. SIAM J. Optim, 2010, 20：1956-1982[8] LINZ,etal Theaugmentedlagrangemultipliermethodforexactrecoveryofcorruptedlow-rankmatrices[J] UIUCTechni- cial Report UIUL-ENG-09-2214,2010[9] MA Y,ZHIL．Theminimum-rankgram matrixcompletionvia modifiedfixedpointcontinuation method[A] International SymposiumonSymbolicand AlgebraicComputation36th,2011,241-248[10] JAIN P,NETRAPALLI P,SANGHAVI S．Low-rank matrixcompletionusingalternating minimization[J] Statistics,2012,第4期665-674申倩影,等：符号矩阵填充的修正增广拉格朗日乘子算法11[11] YUAN M JOSEPH R ,ZOU II. Structured variavle selection and estimation[J]. Annals of Applied Atatistics,2009,3(4):

1738-1757[12] MA S , GOLDFARB D , CHEN L. Fixed point and Bregman iterative methods for matrix rank minimization [J ]. Math. Pro­

gram ,2011,128(1-2):321-353[13] DAI W , MILENKOVIC O. SET: an algorthm for consistent matrix completion】 A]. IEEE International Conference on A­

coustics Speech andSignalProcessing 2010 36-39[14] CHEN C , HE B , YUAN X. Matrix completion via an alternating direction method]〕]. Ima. J. Numer. Anal,2012,32(1) :227-

245[15]

LINZ GANESHA WRIGHTJetalFastconvexoptimizationalgorithmforexactrecoveryofacorruptedlow-rankmatrix [A]. IEEE International Workshop on Computational Advances in Multi-sensor Adaptive Processing , Aruba , Dutch Antilles , 2009,56(3):707-722[16] CANDES E J,PLAN Y. Matrix completion with noise[J]. Proc IEEE ,2009,98 : 925-936[17] HU Y ,ZHANG D B ,LIU J,et al. Accelerated singular value thresholding for matrix completion]A] In： Proceedings of the18th ACM SIGKDD international conference on Knowledge discovery and data mining. New York： ACM ,2012,298-306[18] CAIJF OSHERS Fast singular value thresholding without singular value decomposition[J] MethodsApplAnal2013 20：335-352[19] MARINA ARAV ,FRANK HALL ,et al. Sign patterns that require almost unoque rank[J]. Linear Algebra and ts Applica-

tions2009 430：7-16[20] MARCO MARTORELLA FABRIZIO BERIZZI SILVIA BRUSCOLI UseofGeneticAlgorithmsforContrastandEntropy

Optimization in ISAR Autofocusing[J] EURASIP Journal on Applied Signal Processing 2009 1-11[21]

GOLUB G H VANLOAN C F MatrixComputations[M](3rdedn) Baltimore：TheJohnsHopkinsUniversityPress MD

1996[22] CHEN Y D. Robust matrix completion wth corrupted columns]〕]. Information Theory IEEE Transactions on,2012,62(1):

503-526The Augmented Lagrange Multiplier Method Algorithm for

Sign Matrix CompletionSHEN Qianying , WANG Chuanlong(Higher Education Key Laboratory of Engineering and Scientific Computing in Shanxi Province ,Taiyuan Normal University,Jinzhong 030619 ,China)〔Abstract〕 To propose a modified Augmented Lagrange Multiplier Method for sign matrix

completion by projecting the threshold matrix based on the Augmented Lagrange Multiplier

Method. The new method ensures that the matrix produced by each iteration is a feasible sign ma­

trix and the convergence analysis is given．Final y numerical experiments show that the new al- gorithmismoreefectivethanthetraditionalgeneticalgorithmintimeanderror andtheerror canreachzerotoachieveaccuraterecovery．〔Key words〕 matrix completion； sign matrix； the augmented Lagrange method； the geneticalgorithm