申倩影 ，王川龍

(工程科學(xué)計(jì)算山西省高等學(xué)校重點(diǎn)實(shí)驗(yàn)室 太原師范學(xué)院，晉中 030619)

0 引言

矩陣填充問(wèn)題是一個(gè)引人注目的新研究領(lǐng)域，它的一個(gè)著名應(yīng)用是Netflix系統(tǒng)，在圖像恢復(fù)[1]，控制[2]，計(jì)算機(jī)視覺[3]，機(jī)器學(xué)習(xí)[4,5]等問(wèn)題中都有非常重要的應(yīng)用.

矩陣填充主要研究如何在數(shù)據(jù)不完整的情況下將缺失矩陣進(jìn)行填充.大部分低秩矩陣(其數(shù)據(jù)分布在一個(gè)低維的線性子空間上)填充問(wèn)題一般可以通過(guò)求解如下凸優(yōu)化問(wèn)題來(lái)實(shí)現(xiàn)：

min ‖X‖*

(1)

s.t.PΩ(X)=D

符號(hào)模式矩陣是組合矩陣論的一個(gè)新型研究分支，是近年來(lái)在組合數(shù)學(xué)中較為活躍的一個(gè)研究方向.符號(hào)矩陣[19]是指元素取自集合{+,-,0}或{1,-1,0}的矩陣.本文主要是對(duì)取值于集合{1,0}的符號(hào)矩陣的填充問(wèn)題進(jìn)行研究.符號(hào)矩陣的填充問(wèn)題主要應(yīng)用于生物醫(yī)學(xué)領(lǐng)域.基因變異是指基因在結(jié)構(gòu)上發(fā)生堿基對(duì)組成或排列順序的改變，基因變異在臨床疾病診斷和治療、細(xì)菌和疫苗中都有重要的研究意義，而這種變異可以用單倍體(染色體的單核苷酸多態(tài)性) 來(lái)識(shí)別，單倍體含有本物種配子染色體數(shù)及其全套染色體組，也就是有生活必需的全套基因，而每條單倍體可以看作是由{1,0}所組成的符號(hào)序列.然而，由于硬件的限制，單倍體不能被完全觀測(cè)，只能得到一部分信息.如何從已知的部分信息來(lái)得到完整的單倍體信息就需要通過(guò)求解符號(hào)矩陣的填充問(wèn)題來(lái)實(shí)現(xiàn).

本文結(jié)構(gòu)安排如下：第1節(jié)首先回顧已有的對(duì)一般矩陣填充的ALM算法，然后詳細(xì)介紹針對(duì)符號(hào)矩陣填充的SM-ALM算法和GA算法；第2節(jié)給出了SM-ALM算法的收斂性分析；第3節(jié)通過(guò)數(shù)值實(shí)驗(yàn)給出了SM-ALM算法和GA算法對(duì)符號(hào)矩陣填充的結(jié)果；最后在第4節(jié)對(duì)全文進(jìn)行總結(jié).

1 算法

首先回顧已有的對(duì)一般矩陣填充的ALM算法：

1.1 矩陣填充的ALM算法

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

min ‖A‖*

(2)

s.t.A+E=D,PΩ(E)=0

其Lagrange函數(shù)為：

(3)

其中Y∈Rn1×n2.

算法1(ALM算法)

第0步：給定下標(biāo)集合Ω，樣本矩陣D，參數(shù)μ0>0，ρ>1,以及初始矩陣Y0=0,E0=0,k=0;

第2步：令

第3步：通過(guò)給定參數(shù)，若‖D-Ak+1-Ek+1‖F(xiàn)/‖D‖F(xiàn)<ε1，并且μk‖Ek+1-Ek‖F(xiàn)/‖D‖F(xiàn)<ε2，停止；否則，轉(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；否則，轉(zhuǎn)第1步.

1.2 符號(hào)矩陣填充的算法

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

1.2.1 修正的ALM算法(SM-ALM算法)

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

min ‖A‖*

(4)

s.t.A+E=D,PΩ(E)=0

其Lagrange函數(shù)為：

(5)

其中A,D,E都是符號(hào)矩陣，Y∈Rn1×n2.

算法2(SM-ALM算法)

第0步：給定下標(biāo)集合Ω，樣本矩陣D，參數(shù)μ0>0，ρ>1,以及初始矩陣Y0=0,E0=0,k=0；

第2步：令

第3步：令

第4步：通過(guò)給定參數(shù)，若‖D-Ak+1-Ek+1‖F(xiàn)/‖D‖F(xiàn)<ε1，并且μk‖Ek+1-Ek‖F(xiàn)/‖D‖F(xiàn)<ε2，停止；否則，轉(zhuǎn)第5步；

第5步：令Yk+1=Yk+μk(D-Ak+1-Ek+1)，如果μk‖Ek+1-Ek‖F(xiàn)/‖D‖F(xiàn)<ε2，令μk+1=ρμk；否則，轉(zhuǎn)第1步.

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

1.2.2 遺傳算法

遺傳算法(GA)[20]是計(jì)算機(jī)科學(xué)人工智能領(lǐng)域中用于解決最優(yōu)化的一種搜索啟發(fā)式算法，是進(jìn)化算法的一種.它是美國(guó)的J.Holland教授1975年提出的，這種啟發(fā)式通常用來(lái)生成有用的解決方案來(lái)優(yōu)化和搜索問(wèn)題.進(jìn)化算法最初是借鑒了進(jìn)化生物學(xué)中的一些現(xiàn)象而發(fā)展起來(lái)的，這些現(xiàn)象包括遺傳、突變、自然選擇以及雜交等.遺傳算法在適應(yīng)度函數(shù)選擇不當(dāng)?shù)那闆r下有可能收斂于局部最優(yōu)，而不能達(dá)到全局最優(yōu).

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

算法3(GA算法)

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

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

第3步：對(duì)pop中每一個(gè)個(gè)體進(jìn)行選擇，得到新種群newpop；

第4步：對(duì)新種群newpop進(jìn)行交叉，變異得到newpop1；

第7步：比較newpop1中每一個(gè)個(gè)體適應(yīng)度的大小，選出最優(yōu)個(gè)體.

2 收斂性分析

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

引理1[21]奇異值分解(SVD)秩為r的矩陣X∈Rn1×n2，則必存在正交矩陣U∈Rn1×r和V∈Rn2×r，使得X=UΣrVT，Σr=diag(σ1，…，σr)，其中σ1≥σ2≥…≥σr>0.

引理 2[22](奇異值閾值算子) 對(duì)于任意參數(shù)τ≥0，秩為r的矩陣X∈Rn1×n2，存在奇異值分解X=UΣrVT，奇異值閾值算子Dτ定義為：

Dτ(X)=UDτ(Σ)VT,Dτ(Σ)=diag({σi-τ}+)

其中：

證明

Yk=Yk-1+μk-1(D-Ak-Ek)=

證明

Yk=Yk-1+μk-1(D-Ak-Ek)

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

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

在本節(jié)中，通過(guò)數(shù)值實(shí)驗(yàn)比較SM-ALM算法與GA算法.

表1 小矩陣的計(jì)算結(jié)果(使用MALM算法)

表2 大矩陣的計(jì)算結(jié)果(使用MALM算法)

表3 使用GA算法對(duì)符號(hào)矩陣進(jìn)行填充

4 總結(jié)

在本文中，使用SM-ALM算法和GA算法來(lái)填充符號(hào)矩陣，結(jié)果表明SM-ALM算法是可行的，并能在很短的時(shí)間和很少的迭代步數(shù)內(nèi)找到精確的解.而使用 GA 算法只能經(jīng)過(guò)有限步迭代輸出結(jié)果，降低誤差，不能達(dá)到收斂的效果，更找不到精確的解.