王俊霞, 申倩影, 王川龍

(太原師范學院數學系，晉中 030619)

1 引言

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

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

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

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

針對符號矩陣的填充問題，本文基于奇異值閾值算法和增廣Lagrange 乘子法提出了修正的增廣Lagrange 乘子法(MALM)和遺傳算法(GA).與傳統(tǒng)的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 節(jié)首先回顧已有算法，然后介紹符號矩陣的MALM 算法和遺傳算法；第3 節(jié)給出了MALM 算法的收斂性分析；第4 節(jié)通過數值實驗來比較MALM 算法和ALM 算法、遺傳算法對符號矩陣填充的結果；最后在第5 節(jié)對全文進行總結.

2 算法

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

2.1 矩陣填充的ALM 算法

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

其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 算法).

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

其中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 收斂性分析

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

證明

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

4 數值實驗

4.1 實驗細則

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

1) 采樣矩陣的生成方式

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

在生成矩陣M的實驗中，我們發(fā)現：當矩陣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 實驗結果

在本節(jié)中，通過數值實驗將MALM 算法與ALM 算法和GA 算法進行比較.

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

表3 使用GA 算法的實驗結果

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

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

5 總結

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

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