符號(hào)矩陣填充的修正增廣拉格朗日乘子算法

王俊霞, 申倩影, 王川龍

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

1 引言

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

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

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

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

針對(duì)符號(hào)矩陣的填充問(wèn)題，本文基于奇異值閾值算法和增廣Lagrange 乘子法提出了修正的增廣Lagrange 乘子法(MALM)和遺傳算法(GA).與傳統(tǒng)的ALM 算法相比，MALM 算法每步產(chǎn)生的閾值矩陣都為符號(hào)矩陣，并討論了算法的收斂性，同時(shí)通過(guò)數(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]對(duì)于任意參數(shù)τ ≥0，秩為r的矩陣X ∈Rn1×n2，存在奇異值分解X=UΣrV T，奇異值閾值算子Dτ定義為

其中

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

2 算法

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

2.1 矩陣填充的ALM 算法

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

其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 步 通過(guò)給定參數(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 符號(hào)矩陣填充的新算法

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

2.2.1 修正的ALM 算法

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

符號(hào)矩陣的填充問(wèn)題可以描述為以下凸優(yōu)化問(wèn)題

其中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)行奇異值分解之后，取其符號(hào)矩陣，然后進(jìn)行填充，這樣可以保證每次產(chǎn)生的迭代矩陣都保持符號(hào)矩陣的結(jié)構(gòu).

2.2.2 符號(hào)矩陣填充的遺傳算法

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

算法3 GA 算法

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

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

3 收斂性分析

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

證明

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

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

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

本文是針對(duì)符號(hào)矩陣(取自元素-1,1)填充問(wèn)題進(jìn)行研究，在此說(shuō)明一下實(shí)驗(yàn)過(guò)程中采樣矩陣的生成方式，所采用的矩陣秩的選取規(guī)則以及對(duì)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í)，矩陣的元素也會(huì)出現(xiàn)不同的結(jié)果，具體如下：

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

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

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

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

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

在本節(jié)中，通過(guò)數(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 算法作對(duì)比，無(wú)論是迭代步數(shù)還是收斂時(shí)間，MALM 算法都具有很強(qiáng)的優(yōu)勢(shì)；使用遺傳算法進(jìn)行填充，當(dāng)采樣矩陣規(guī)模過(guò)大，例如矩陣大小為1000，采樣率為0.2 時(shí)，染色體長(zhǎng)度為800000，選取個(gè)體數(shù)為20，生成的初始種群為800000×20 的矩陣，由于計(jì)算機(jī)硬件的限制，程序運(yùn)行不出來(lái).因此，表3 給出了小規(guī)模矩陣的運(yùn)行結(jié)果，但仍然不理想，達(dá)不到收斂效果.但和初始誤差相比，經(jīng)過(guò)有限步，誤差會(huì)相對(duì)減少.

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

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

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

5 總結(jié)

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

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