符號矩陣填充的修正增廣拉格朗日乘子算法

王俊霞, 申倩影, 王川龍

(太原師范學(xué)院數(shù)學(xué)系，晉中 030619)

1 引言

矩陣填充主要研究如何通過已知的部分矩陣元素來恢復(fù)一個(gè)低秩矩陣.矩陣填充在圖像恢復(fù)[1]、控制[2]、計(jì)算機(jī)視覺[3]、機(jī)器學(xué)習(xí)[4,5]等領(lǐng)域中都有非常重要的應(yīng)用.由于秩的不連續(xù)性，低秩矩陣填充問題通常被松弛為一個(gè)凸優(yōu)化問題

符號矩陣[16]是指元素取自集合{1,-1}或{1,-1,0}的矩陣.本文主要是對取值于集合{1,-1}的符號矩陣進(jìn)行研究.一個(gè)n×n的符號矩陣T有如下形式

顯然，T是一個(gè)由1,-1 元素組成的符號矩陣.這類矩陣的填充問題在生物醫(yī)學(xué)等領(lǐng)域有著很好的應(yīng)用前景.基因變異的研究是疾病識別和藥物開發(fā)的關(guān)鍵，這種變異可以用單倍體(染色體的單核苷酸多態(tài)性)來識別.每條單倍體可以看作由{1,-1}所組成的符號序列.然而，由于硬件的限制，單倍體不能被完全觀測，只能得到一部分信息.如何從有限的信息恢復(fù)出完整的單倍體就需要用符號矩陣的填充來解決.

遺傳算法(GA)[17]是一類借鑒生物界的進(jìn)化規(guī)律(適者生存，優(yōu)勝劣汰的遺傳機(jī)制)演化而來的隨機(jī)化搜索方法.它是美國的Holland 教授于1975 年提出的，其主要特點(diǎn)是直接對結(jié)構(gòu)對象進(jìn)行操作，不存在求導(dǎo)和函數(shù)連續(xù)性的界定；具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力；采用概率化的尋優(yōu)方法，能自動獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則.遺傳算法在適應(yīng)度函數(shù)選擇不當(dāng)?shù)那闆r下有可能收斂于局部最優(yōu)，而不能達(dá)到全局最優(yōu).

針對符號矩陣的填充問題，本文基于奇異值閾值算法和增廣Lagrange 乘子法提出了修正的增廣Lagrange 乘子法(MALM)和遺傳算法(GA).與傳統(tǒng)的ALM 算法相比，MALM 算法每步產(chǎn)生的閾值矩陣都為符號矩陣，并討論了算法的收斂性，同時(shí)通過數(shù)值試驗(yàn)與ALM 算法和GA 算法進(jìn)行比較，驗(yàn)證MALM 算法的有效性.

首先給出一些定義和引理：

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

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

定義1(奇異值閾值算子)[7]對于任意參數(shù)τ ≥0，秩為r的矩陣X ∈Rn1×n2，存在奇異值分解X=UΣrV T，奇異值閾值算子Dτ定義為

其中

本文結(jié)構(gòu)安排如下：第2 節(jié)首先回顧已有算法，然后介紹符號矩陣的MALM 算法和遺傳算法；第3 節(jié)給出了MALM 算法的收斂性分析；第4 節(jié)通過數(shù)值實(shí)驗(yàn)來比較MALM 算法和ALM 算法、遺傳算法對符號矩陣填充的結(jié)果；最后在第5 節(jié)對全文進(jìn)行總結(jié).

2 算法

為保證文章的完整性及收斂性證明的需要，我們首先對已有算法進(jìn)行簡單回顧.

2.1 矩陣填充的ALM 算法

ALM 算法[8]解決以下凸優(yōu)化問題

其Lagrange 函數(shù)為

其中Y ∈Rn1×n2.

算法1 ALM 算法

第0 步 給定下標(biāo)集合Ω，樣本矩陣D ∈Rn1×n2，參數(shù)μ0＞0, ρ ＞1, ?1,?2＞0 以及初始矩陣Y0=O, E0=O, k:=0；

第3 步 通過給定參數(shù)，若

停止；否則，轉(zhuǎn)第4 步；

第4 步 令Yk+1=Yk+μk(D-Ak+1-Ek+1).如果μk‖Ek+1-Ek‖F(xiàn)/‖D‖F(xiàn) ＜?2，令μk+1=ρμk, k:=k+1，轉(zhuǎn)第1 步.

2.2 符號矩陣填充的新算法

在總結(jié)現(xiàn)有研究基礎(chǔ)上，我們提出符號矩陣填充問題的新算法.

2.2.1 修正的ALM 算法

由于我們是對符號矩陣進(jìn)行填充，算法1 在填充結(jié)束之后所形成的矩陣是Rn1×n2中的矩陣，雖然能達(dá)到誤差要求，但不一定能落入中.因此，我們給出了修正后的ALM 算法(MALM 算法).

符號矩陣的填充問題可以描述為以下凸優(yōu)化問題

其中A,D,E ∈.

其Lagrange 函數(shù)為

其中Y ∈Rn1×n2.

算法2 MALM 算法

停止；否則，轉(zhuǎn)第5 步；

第5 步 給定參數(shù)，令Yk+1=Yk+μk(D-Ak+1-Ek+1).如果μk‖Ek+1-Ek‖F(xiàn)/‖D‖F(xiàn) X ＜?2，令μk+1=ρμk, k:=k+1，轉(zhuǎn)第1 步.

算法2 在進(jìn)行奇異值分解之后，取其符號矩陣，然后進(jìn)行填充，這樣可以保證每次產(chǎn)生的迭代矩陣都保持符號矩陣的結(jié)構(gòu).

2.2.2 符號矩陣填充的遺傳算法

下面我們提出符號矩陣填充的遺傳算法(GA 算法).

算法3 GA 算法

第0 步 給定下標(biāo)集合Ω，樣本矩陣D ∈，參數(shù)?，交叉概率，變異概率；

第1 步 給定種群大小，根據(jù)采樣率計(jì)算染色體長度，生成種群pop(其中元素為1,-1)；

3 收斂性分析

本節(jié)討論算法2 的收斂性.

證明

由引理3 知，當(dāng)k充分大時(shí)，有D-Ak-Ek=O.由定理1 知Ak是問題(4)的解.

4 數(shù)值實(shí)驗(yàn)

4.1 實(shí)驗(yàn)細(xì)則

本文是針對符號矩陣(取自元素-1,1)填充問題進(jìn)行研究，在此說明一下實(shí)驗(yàn)過程中采樣矩陣的生成方式，所采用的矩陣秩的選取規(guī)則以及對ALM 算法的補(bǔ)充.

1) 采樣矩陣的生成方式

2) 矩陣秩的選取規(guī)則

在生成矩陣M的實(shí)驗(yàn)中，我們發(fā)現(xiàn)：當(dāng)矩陣P和Q的秩為r時(shí)，矩陣M的秩為2r-1，當(dāng)r取奇偶數(shù)時(shí)，矩陣的元素也會出現(xiàn)不同的結(jié)果，具體如下：

① 當(dāng)r取奇數(shù)時(shí)，填充矩陣A只包含元素1,-1，與本文研究內(nèi)容相符；

② 當(dāng)r取偶數(shù)時(shí)，填充矩陣A包含元素1,0,-1，與本文研究內(nèi)容不符.

3) ALM 算法的補(bǔ)充

由于用ALM 算法填充出來的是Rn1×n2中的矩陣，雖然滿足誤差要求，但不一定是符號矩陣，因此，在ALM 算法的最后一步，我們將迭代完畢后的矩陣投影到中，然后和MALM 算法進(jìn)行比較.

4.2 實(shí)驗(yàn)結(jié)果

在本節(jié)中，通過數(shù)值實(shí)驗(yàn)將MALM 算法與ALM 算法和GA 算法進(jìn)行比較.

表1 和表2 是MALM 算法和ALM 算法的比較，從實(shí)驗(yàn)數(shù)據(jù)可以看出，當(dāng)矩陣達(dá)到一定規(guī)模時(shí)，ALM 算法是收斂的，并且誤差能達(dá)到0，但和MALM 算法作對比，無論是迭代步數(shù)還是收斂時(shí)間，MALM 算法都具有很強(qiáng)的優(yōu)勢；使用遺傳算法進(jìn)行填充，當(dāng)采樣矩陣規(guī)模過大，例如矩陣大小為1000，采樣率為0.2 時(shí)，染色體長度為800000，選取個(gè)體數(shù)為20，生成的初始種群為800000×20 的矩陣，由于計(jì)算機(jī)硬件的限制，程序運(yùn)行不出來.因此，表3 給出了小規(guī)模矩陣的運(yùn)行結(jié)果，但仍然不理想，達(dá)不到收斂效果.但和初始誤差相比，經(jīng)過有限步，誤差會相對減少.

表3 使用GA 算法的實(shí)驗(yàn)結(jié)果

表2 MALM 算法與ALM 算法比較(秩為64)

表1 MALM 算法與ALM 算法比較(秩為16)

5 總結(jié)

在本文中，我們給出了符號矩陣填充的MALM 算法和GA 算法.MALM 算法以奇異值閾值算法為基礎(chǔ)，對ALM 算法進(jìn)行修正，保證迭代矩陣始終在解空間上.與ALM 算法相比，MALM 算法從迭代步數(shù)和收斂時(shí)間上都有著很強(qiáng)的優(yōu)勢.而GA 算法只能相對減少誤差，還不能達(dá)到收斂，更找不到確切的解.對含有0 的符號矩陣的填充問題將是我們下一步工作的重點(diǎn).

續(xù)表2 MALM 算法與ALM 算法比較(秩為64)