針對(duì)魯棒矩陣補(bǔ)全的加權(quán)冪分解方法

涂劍凱 李春光

（浙江大學(xué)信息與電子工程學(xué)院，浙江杭州 310027）

1 引言

矩陣補(bǔ)全旨在通過(guò)部分觀測(cè)的數(shù)據(jù)點(diǎn)來(lái)恢復(fù)一個(gè)完整的矩陣。由于大量的實(shí)際數(shù)據(jù)天然都是以矩陣形式進(jìn)行組織的，矩陣補(bǔ)全在許多研究領(lǐng)域都引起了廣泛的關(guān)注，包括圖像修復(fù)［1-3］，推薦系統(tǒng)［4-7］與視頻靜態(tài)背景提?。?-10］。相較于基于數(shù)據(jù)學(xué)習(xí)的方式［11］，矩陣補(bǔ)全僅針對(duì)單個(gè)樣本即可完成上述任務(wù)，不需要額外的訓(xùn)練數(shù)據(jù)。但在沒(méi)有額外信息的情況下，完整恢復(fù)部分觀測(cè)的矩陣幾乎是不可能的。在許多場(chǎng)景中，需要恢復(fù)的矩陣存在低秩的特性。核范數(shù)啟發(fā)式理論的提出證明了在矩陣存在低秩特性時(shí)，可以以較高的概率完整重構(gòu)出這一矩陣［12-13］。具體而言，可以將矩陣的秩轉(zhuǎn)換為矩陣的核范數(shù)，矩陣補(bǔ)全問(wèn)題因此可以建模成一個(gè)半正定的凸優(yōu)化問(wèn)題。但隨著大數(shù)據(jù)時(shí)代的到來(lái)以及高分辨率數(shù)字圖像的廣泛使用，矩陣補(bǔ)全問(wèn)題的規(guī)模不斷擴(kuò)大，傳統(tǒng)的半正定規(guī)劃算法［14］因其沒(méi)有很好地利用矩陣的低秩特性，面臨著巨大的效率問(wèn)題。

近年來(lái)，許多方法被提出來(lái)高效地解決矩陣補(bǔ)全問(wèn)題，同時(shí)利用矩陣低秩特性來(lái)進(jìn)一步增強(qiáng)補(bǔ)全的性能。許多基于完整的（full）或者截?cái)嗟模╰runcated）奇異值分解（SVD）的方法被提出來(lái)以最小化矩陣的核范數(shù)，如奇異值閾值約束（SVT）方法［15］，定點(diǎn)連續(xù)化方法（FPC）［16］，硬閾值歸一化迭代方法（NIHT）［17］。但這一類算法在每個(gè)迭代環(huán)節(jié)中需要進(jìn)行奇異值分解，這給每個(gè)迭代的計(jì)算過(guò)程帶來(lái)了較高的計(jì)算復(fù)雜度。為了解決這一問(wèn)題，冪分解（Power Factorization（PF））模型［18-19］被提出來(lái)并應(yīng)用于矩陣補(bǔ)全問(wèn)題［20-21］。PF 模型將矩陣分解成兩個(gè)秩r矩陣的乘積，其中r遠(yuǎn)小于矩陣的大小。因此，矩陣的低秩特性自然地得到了滿足，從而避免了高復(fù)雜度的SVD 操作。從另外一個(gè)角度來(lái)看，這種分解可以理解為將矩陣分解成r個(gè)秩1 分量的相加。PF 模型一個(gè)主要的問(wèn)題在于需要一個(gè)較為精確的矩陣秩參數(shù)r的估計(jì)值。在實(shí)際場(chǎng)景中，我們只知道一小部分觀測(cè)的元素，因而對(duì)秩參數(shù)r進(jìn)行精確估計(jì)是不現(xiàn)實(shí)的。此外，如果將這個(gè)低秩矩陣視為秩1 矩陣的和，PF 模型對(duì)每個(gè)秩1 分量都分配相同的權(quán)重，然而實(shí)際上，不同分量之間的權(quán)值可能并不一致，這可能會(huì)影響PF 模型的性能。

受上述問(wèn)題的驅(qū)使，想要建立一種自動(dòng)的秩選擇和度量學(xué)習(xí)機(jī)制。在本論文中，我們提出了加權(quán)PF 模型（WPF）。相較于傳統(tǒng)的PF 方法，引入了一個(gè)輔助變量并對(duì)其施加稀疏約束，其目的有兩個(gè)方面。第一，其可以區(qū)分不同秩1 分量間的重要性并學(xué)習(xí)不同分量間的最佳度量，并分配給不同秩1 分量以不同的權(quán)重。第二，通過(guò)稀疏約束，其可以定位不必要的秩1分量，并將其擯棄。因此，通過(guò)給定一個(gè)足夠大的秩參數(shù)，其可以自動(dòng)地尋找矩陣秩最小化的目標(biāo)，從而避免了需要事先估計(jì)一個(gè)準(zhǔn)確的秩參數(shù)的問(wèn)題。

更進(jìn)一步，考慮當(dāng)觀測(cè)的矩陣元素被噪聲污染的情況。已經(jīng)有不少算法采用l2或l1范數(shù)來(lái)應(yīng)對(duì)噪聲環(huán)境下的矩陣補(bǔ)全問(wèn)題［22-23］。它們?cè)诟咚乖肼暛h(huán)境下有比較好的表現(xiàn)，但對(duì)于非高斯噪聲，比如含有異常值情況，其效果往往不佳。一類采用了lp范數(shù)的方法［24-25］可以應(yīng)對(duì)不同的噪聲環(huán)境，但其需要針對(duì)不同的環(huán)境給出不同的參數(shù)p，這在現(xiàn)實(shí)中是難以做到的。為了消除異常值等非高斯噪聲帶來(lái)的影響，同時(shí)保留l2與l1范數(shù)的優(yōu)點(diǎn)，我們結(jié)合信息論理論并采用了相關(guān)熵（Correntropy）［26］來(lái)作為噪聲的懲罰以達(dá)到魯棒矩陣補(bǔ)全的效果。此外，還采用了半相關(guān)（HQ）理論［27-28］與交替梯度下降（AGD）算法對(duì)WPF模型進(jìn)行優(yōu)化。

為了驗(yàn)證我們提出的WPF方法的性能，在理論層面，分析了WPF方法的計(jì)算復(fù)雜度來(lái)說(shuō)明我們的方法相較于基于SVD 方法的優(yōu)勢(shì)。在實(shí)驗(yàn)層面，利用合成數(shù)據(jù)與真實(shí)數(shù)據(jù)的實(shí)驗(yàn)結(jié)果來(lái)進(jìn)一步說(shuō)明我們提出的WPF 方法的優(yōu)勢(shì)。并探索了WPF 模型在圖像修復(fù)中的應(yīng)用。

本論文的總體規(guī)劃如下。在第2節(jié)中對(duì)矩陣補(bǔ)全問(wèn)題作一個(gè)介紹。在第3 節(jié)中，建立我們的魯棒加權(quán)冪分解模型，并且在第4 節(jié)中給出優(yōu)化的方法與復(fù)雜度的分析。第5 節(jié)中，呈現(xiàn)了針對(duì)仿真數(shù)據(jù)和真實(shí)數(shù)據(jù)的實(shí)驗(yàn)結(jié)果。最后，在第6 節(jié)中進(jìn)行總結(jié)。

2 矩陣補(bǔ)全問(wèn)題

矩陣補(bǔ)全問(wèn)題通常假定需要補(bǔ)全的矩陣擁有一種低秩或近似低秩的結(jié)構(gòu)［12］。給定一個(gè)矩陣，其中只有一個(gè)子集Ω 的元素被觀測(cè)到。我們想要在低秩約束下恢復(fù)完整的矩陣，這個(gè)矩陣補(bǔ)全問(wèn)題就可以描述為：

其中Xij（Mij）表示矩陣X（M）第i行第j列的元素。上述問(wèn)題已經(jīng)被證明為一個(gè)NP-難的問(wèn)題［12］?？紤]到rank 函數(shù)的非凸性，可以通過(guò)矩陣核范數(shù)‖X‖*，即矩陣的奇異值之和，來(lái)對(duì)rank 函數(shù)進(jìn)行松弛近似。核范數(shù)啟發(fā)式理論［13］表明這一近似下的低秩矩陣仍可以以一個(gè)相對(duì)高的概率精確恢復(fù)。那么上述問(wèn)題就轉(zhuǎn)換為：

對(duì)上述矩陣核范數(shù)進(jìn)行優(yōu)化時(shí)通常采用迭代的算法，而在每個(gè)迭代過(guò)程中通常需要對(duì)矩陣進(jìn)行奇異值分解。奇異值分解的操作在規(guī)模較大的矩陣中是一個(gè)非常耗時(shí)的操作，于是就有人提出采用PF模型來(lái)求解矩陣補(bǔ)全問(wèn)題，其原理在于事先對(duì)矩陣進(jìn)行低秩分解，即X=UV?，其中，是兩個(gè)低秩矩陣，符號(hào)?表示矩陣轉(zhuǎn)置。在對(duì)矩陣進(jìn)行分解后，其低秩特性自然得到滿足，從而避免了對(duì)核范數(shù)的優(yōu)化，進(jìn)而避免了奇異值分解的操作。由此，矩陣補(bǔ)全問(wèn)題可以轉(zhuǎn)換成：

其中L表示對(duì)矩陣補(bǔ)全效果的度量，在這里我們用ZΩ表示任意一個(gè)指定的矩陣，其元素為Zij，如果(i，j)∈Ω，元素為0，如果(i，j) ?Ω。需要說(shuō)明的是這里對(duì)不在采樣子集Ω內(nèi)的元素賦值為0僅是為了存儲(chǔ)與計(jì)算上的簡(jiǎn)便，在建模與優(yōu)化過(guò)程中并不會(huì)涉及不在采樣子集Ω 內(nèi)的元素。但PF 模型存在的一個(gè)問(wèn)題在于其通常需要對(duì)矩陣的秩參數(shù)r有一個(gè)較為精確的估計(jì)，這在僅知道部分觀察數(shù)據(jù)MΩ的情況下是難以實(shí)現(xiàn)的。

進(jìn)一步考慮觀測(cè)矩陣元素含有噪聲的情況。在有噪聲情況下，相應(yīng)的觀測(cè)矩陣可以表示為MΩ=XΩ+EΩ，其中EΩ表示噪聲矩陣。這時(shí)L需要用于對(duì)噪聲進(jìn)行懲罰。常見(jiàn)的魯棒矩陣補(bǔ)全算法［22-25］對(duì)含有高斯噪聲的矩陣補(bǔ)全問(wèn)題有較好的效果，但對(duì)于非高斯噪聲，其表現(xiàn)通常不佳。

3 魯棒加權(quán)冪分解模型

3.1 加權(quán)冪分解模型

冪分解（PF）模型的核心思想在于將一個(gè)矩陣分解為兩個(gè)低秩矩陣的乘積，然后對(duì)這兩個(gè)低秩矩陣進(jìn)行交替優(yōu)化，即對(duì)于一個(gè)待補(bǔ)全的矩陣，將其表示為兩個(gè)低秩矩陣，的乘積：

這種方式保證了矩陣的低秩特性，從而避免了對(duì)矩陣核范數(shù)的優(yōu)化，進(jìn)而避免了奇異值分解的操作。但是，其問(wèn)題在于需要事先對(duì)矩陣估計(jì)一個(gè)較為精確的秩參數(shù)r，而這一點(diǎn)在現(xiàn)實(shí)中通常是難以做到的。從另一個(gè)角度可以將其理解為把矩陣X分解成r個(gè)秩1 矩陣的和。從這個(gè)角度來(lái)看，PF 的方法對(duì)每個(gè)秩1 分量賦予相等的權(quán)重，而不同的秩1分量間可能存在不同的重要性程度。

為了解決上述問(wèn)題，我們提出加權(quán)冪分解（weighted power factorization（WPF））模型。具體而言，在PF 模型基礎(chǔ)上再引入一個(gè)輔助變量將待補(bǔ)全的矩陣分解成三個(gè)矩陣的乘積，即X=UΣV?，其中，并且要求Σ=diag {σ1，…，σr}為一個(gè)對(duì)角矩陣。從另一個(gè)角度而言，對(duì)上述PF 模型中每個(gè)秩1分量加上各自的權(quán)重參數(shù)σi，i=1，…，r。用數(shù)學(xué)語(yǔ)言來(lái)描述即：

相較于PF 模型，我們引入了額外的變量Σ，其對(duì)角線各元素充當(dāng)了各個(gè)秩1分量的權(quán)重參數(shù)。相較于奇異值分解（SVD），不要求矩陣U，V是正交矩陣，并且針對(duì)待補(bǔ)全的矩陣事先進(jìn)行分解，對(duì)分解后的變量U，V，Σ進(jìn)行直接優(yōu)化，而不會(huì)在后續(xù)優(yōu)化過(guò)程中對(duì)矩陣進(jìn)行奇異值分解。從權(quán)重的角度理解，我們希望引入輔助變量Σ來(lái)學(xué)習(xí)不同秩1分量間的重要程度，從而對(duì)不同的秩1 分量賦予不同的權(quán)值。這種針對(duì)不同分量賦予不同權(quán)重的方式可以讓模型確定重要分量的過(guò)程具有更大的自由度，從而提高模型的性能。對(duì)應(yīng)的矩陣補(bǔ)全模型就可以建模成：

在PF 模型中，我們需要事先估計(jì)一個(gè)較為精確的矩陣秩參數(shù)r，但這在現(xiàn)實(shí)中是難以做到的。因此，希望可以實(shí)現(xiàn)一種秩自動(dòng)選擇的機(jī)制，即給定一個(gè)足夠大的秩參數(shù)r，希望模型可以自動(dòng)地確定合適的秩參數(shù)r。觀察到非零σi的個(gè)數(shù)等價(jià)于矩陣的秩，如同矩陣補(bǔ)全問(wèn)題最初的建模（1），希望盡可能地優(yōu)化問(wèn)題使得矩陣的秩盡可能小，即希望Σ中為零的σi盡可能多。為了達(dá)到這一目的，對(duì)變量Σ加入一個(gè)稀疏約束，引入的變量Σ就可以自動(dòng)優(yōu)化來(lái)找到一個(gè)稀疏的解，即確定一些不必要的秩1 分量并將其擯棄，從而實(shí)現(xiàn)變量Σ的稀疏，即實(shí)現(xiàn)矩陣的低秩。因此在WPF模型中，我們只需要事先給定一個(gè)足夠大的矩陣的秩的估計(jì)，在優(yōu)化過(guò)程中，WPF 會(huì)自動(dòng)尋找合適的秩參數(shù)，從而使得模型達(dá)到低秩的效果。

通常可以選用l0范數(shù)來(lái)進(jìn)行稀疏約束，l0稀疏優(yōu)化問(wèn)題通?？梢酝ㄟ^(guò)匹配追蹤算法［29］或迭代閾值算法［30］進(jìn)行優(yōu)化，但前者算法穩(wěn)定性不佳且對(duì)于復(fù)雜的目標(biāo)函數(shù)不易計(jì)算，后者容易陷入局部最優(yōu)解且算法對(duì)噪聲較為敏感。因此采用凸松弛的方法，選用l2，1范數(shù)來(lái)近似l0約束，l2，1范數(shù)的定義如下式：

至此，我們的WPF模型可以表示為：

其中γ是稀疏約束的參數(shù)。因?yàn)槲覀円螃彩且粋€(gè)對(duì)角矩陣，稀疏約束‖Σ‖2，1就等價(jià)于‖diag (Σ)‖1。

3.2 基于相關(guān)熵的魯棒加權(quán)冪分解模型

考慮上述模型（8）中觀測(cè)數(shù)據(jù)受到非高斯噪聲干擾的情況，即L需要用于對(duì)噪聲進(jìn)行懲罰。文獻(xiàn)中最常見(jiàn)的關(guān)于噪聲的懲罰函數(shù)L的選擇是均方誤差（Mean square error），但其在噪聲是非零均值的，非高斯的，且含有異常值的情況下表現(xiàn)不佳［26］。為了解決這一問(wèn)題，結(jié)合信息論理論并利用相關(guān)熵來(lái)構(gòu)建懲罰函數(shù)L。已有研究［26］表明相關(guān)熵可以在保持良好的回歸性能的同時(shí)盡可能避免非高斯噪聲，尤其是異常值的影響。

相關(guān)熵（Correntropy）是信息論理論中一種描述兩個(gè)變量之間相似度的非線性度量［26］。對(duì)于兩個(gè)給定的矩陣，其相關(guān)熵定義為：

其中

在這里我們定義e=p-q，而符號(hào)δ是一個(gè)需要預(yù)先設(shè)定的參數(shù)值。

如文獻(xiàn)［26］中所述，相關(guān)熵在兩個(gè)變量較近時(shí)的表現(xiàn)等價(jià)于l2范數(shù)，稍遠(yuǎn)時(shí)類似于l1范數(shù)，然后當(dāng)距離進(jìn)一步加大時(shí)趨向于l0范數(shù)。因此，可以通過(guò)極大化相關(guān)熵使得矩陣補(bǔ)全過(guò)程中降低非高斯噪聲，尤其是異常值的影響，同時(shí)保持一個(gè)較好的補(bǔ)全性能。

在矩陣補(bǔ)全問(wèn)題中，針對(duì)我們觀測(cè)到的元素，極大化相關(guān)熵準(zhǔn)則可以描述為下述的一個(gè)極小化的損失函數(shù)：

其中(UΣV?)ij表示矩陣UΣV?第i行第j列的元素。將上述損失函數(shù)（11）簡(jiǎn)化表達(dá)為Jδ=‖(M-UΣV?)Ω‖δ。

采用上述損失函數(shù)作為噪聲的懲罰函數(shù)，對(duì)應(yīng)的矩陣補(bǔ)全問(wèn)題可以表示為：

至此，建立了加權(quán)冪分解（WPF）模型來(lái)應(yīng)對(duì)含有非高斯噪聲的矩陣補(bǔ)全問(wèn)題。在文獻(xiàn)中，矩陣加權(quán)模型這一概念有被應(yīng)用于矩陣低秩近似問(wèn)題［31］與噪聲干擾矩陣補(bǔ)全問(wèn)題［32］，前者針對(duì)給定的加權(quán)矩陣求解最優(yōu)的矩陣低秩近似，后者采用一種硬閾值約束的方式對(duì)數(shù)據(jù)進(jìn)行加權(quán)，從而在一定程度上避免噪聲的干擾。而WPF 模型的加權(quán)體現(xiàn)在兩方面，其一是對(duì)矩陣秩1 分量進(jìn)行加權(quán)，通過(guò)稀疏優(yōu)化的方式來(lái)自適應(yīng)地確定最優(yōu)秩參數(shù)與最優(yōu)秩1 分量權(quán)重，其二在于對(duì)數(shù)據(jù)進(jìn)行加權(quán)，通過(guò)引入相關(guān)熵，對(duì)數(shù)據(jù)噪聲進(jìn)行加權(quán)抑制，不同于硬閾值抑制，WPF 采用數(shù)據(jù)加權(quán)方式從而避免在模型優(yōu)化早期對(duì)一些疑似噪聲項(xiàng)進(jìn)行剔除。

4 WPF模型優(yōu)化

WPF 模型中含有三個(gè)變量，對(duì)于聯(lián)合變量的優(yōu)化是一個(gè)比較復(fù)雜的優(yōu)化問(wèn)題。但對(duì)于單個(gè)變量?jī)?yōu)化，問(wèn)題的規(guī)模就會(huì)簡(jiǎn)單許多，因此我們考慮采用交替優(yōu)化的方式來(lái)對(duì)問(wèn)題（12）進(jìn)行優(yōu)化。

4.1 模型轉(zhuǎn)換

考慮到問(wèn)題（12）中相關(guān)熵是一個(gè)非凸且復(fù)雜的函數(shù)，我們采用半二次（Half-Quadratic（HQ））理論［27-28］來(lái)對(duì)我們提出的損失函數(shù)進(jìn)行轉(zhuǎn)換，以使這個(gè)優(yōu)化問(wèn)題變得更加簡(jiǎn)單。HQ 理論可以將含有相關(guān)熵的優(yōu)化問(wèn)題建模等價(jià)轉(zhuǎn)換為一個(gè)半二次的優(yōu)化問(wèn)題建模，使得其優(yōu)化效率比普通的基于梯度的方法更高［33］。并且轉(zhuǎn)換后對(duì)于其他變量的交替優(yōu)化也會(huì)變得更加簡(jiǎn)單。

根據(jù)HQ 理論，對(duì)于我們提出的損失函數(shù)中相關(guān)熵的部分，即Jδ(e)=2δ2(1-exp (-e2/2δ2))，存在一個(gè)嚴(yán)格凸且非負(fù)的函數(shù)ψ，有

并且在給定e時(shí)，上式等號(hào)右側(cè)的最小值可以在w=時(shí)取到。

基于公式（13），對(duì)于損失函數(shù)（12）中含有相關(guān)熵的一項(xiàng)可以轉(zhuǎn)換為：

其中Ψ(·)表示δ2ψ(·)。

因此，WPF模型就可以轉(zhuǎn)換為：

其中符號(hào)°表示哈達(dá)瑪積，即矩陣之間對(duì)應(yīng)元素相乘，符號(hào)‖Z‖F(xiàn)表示矩陣Z的Frobenius 范數(shù)。上述的優(yōu)化問(wèn)題可以通過(guò)交替優(yōu)化W與其他變量來(lái)實(shí)現(xiàn)。對(duì)于W的優(yōu)化，HQ 理論給出了在其他變量固定時(shí)的閉式解：

由模型（15）可知，HQ 理論引入的輔助變量W相當(dāng)于一個(gè)權(quán)值矩陣，對(duì)于數(shù)據(jù)中的非高斯噪聲，尤其是異常值而言，會(huì)給它們賦予一個(gè)足夠小的權(quán)重來(lái)減小它們的影響。因此，相關(guān)熵的引入可以視作為對(duì)矩陣采樣元素的一種加權(quán)。

4.2 交替梯度下降

在經(jīng)過(guò)模型轉(zhuǎn)換后，WPF 模型存在四個(gè)優(yōu)化變量，我們考慮采用交替優(yōu)化的方式來(lái)對(duì)各個(gè)變量進(jìn)行優(yōu)化。針對(duì)優(yōu)化變量W，按照HQ 理論給出的閉式解來(lái)進(jìn)行優(yōu)化，即如果(i，j)∈Ω，Wij=0，如果(i，j) ?Ω。

對(duì)于給定的W，上述的優(yōu)化問(wèn)題變?yōu)椋?/p>

PF 模型通常采用線性最小二乘估計(jì)方法對(duì)其分解的變量進(jìn)行優(yōu)化［18-19］，但在觀測(cè)數(shù)據(jù)含有非高斯噪聲時(shí)，這種方案易受到噪聲干擾而對(duì)初值敏感且性能不佳，因此我們考慮采用交替梯度下降（Alternating Gradient Descent（AGD））方法來(lái)對(duì)變量U，V，Σ進(jìn)行優(yōu)化。交替梯度下降（AGD）方法每次針對(duì)一個(gè)變量沿著其負(fù)梯度方向移動(dòng)一個(gè)特定的步長(zhǎng)，對(duì)初值的敏感度比較低，并且能得到比較好的收斂效果。具體而言，在每個(gè)迭代過(guò)程中，我們計(jì)算優(yōu)化變量U，V，Σ關(guān)于上述損失函數(shù)L（17）的梯度gU，gV，gΣ，并沿著該梯度方向的負(fù)方向進(jìn)行更新。根據(jù)經(jīng)驗(yàn)，可以在更新過(guò)程設(shè)定一個(gè)給定的步長(zhǎng)或確定變化的步長(zhǎng)，從而來(lái)達(dá)到一個(gè)較好的性能，在本論文中，我們對(duì)U，V設(shè)定一個(gè)確定的步長(zhǎng)μ，對(duì)Σ設(shè)定一個(gè)逐步增加的步長(zhǎng)α。在開(kāi)始時(shí)對(duì)Σ賦與一個(gè)較小的步長(zhǎng)，使模型重點(diǎn)關(guān)注U，V的優(yōu)化以達(dá)到一個(gè)較好的補(bǔ)全效果，再逐步提升Σ的優(yōu)化步長(zhǎng)來(lái)得到一個(gè)稀疏的解。在交替迭代優(yōu)化過(guò)程中，設(shè)定收斂條件為：‖Lt-Lt-1‖F(xiàn)＜?，其中?是一個(gè)預(yù)先設(shè)定的閾值，即當(dāng)?shù)膿p失函數(shù)的變化量小于一定閾值時(shí)，我們終止迭代。先呈現(xiàn)我們完整的算法偽代碼，再給出具體的計(jì)算各變量梯度的細(xì)節(jié)：

在Algorithm 1中，參數(shù)T是最大迭代次數(shù)，參數(shù)a被定義為優(yōu)化變量Σ梯度下降的起始步長(zhǎng)，參數(shù)b決定了步長(zhǎng)α最終收斂的值與收斂的速度。

4.3 U和V的梯度計(jì)算

我們對(duì)優(yōu)化變量U，V，Σ采取交替梯度下降，每次固定住其他變量而對(duì)一個(gè)變量計(jì)算相應(yīng)的梯度并更新。當(dāng)要對(duì)變量U進(jìn)行優(yōu)化時(shí)，將變量V，Σ視為固定的參數(shù)，并且定義。將損失函數(shù)（17）關(guān)于變量U展開(kāi)得到：

上述損失函數(shù)相對(duì)于每一個(gè)元素Umn的梯度可以表示為：

則損失函數(shù)L(U)關(guān)于U的梯度可以表示為：

4.4 Σ的梯度計(jì)算

損失函數(shù)L關(guān)于Σ的導(dǎo)數(shù)相較于變量U，V有所不同。將損失函數(shù)重新寫(xiě)成：

其中Σ=diag {σ1，…，σr}。

在計(jì)算變量Σ的梯度之前，首先將l1范數(shù)的導(dǎo)數(shù)定義為如下的符號(hào)函數(shù)形式：

將損失函數(shù)（22）的第一項(xiàng)定義為：J=。則J關(guān)于每一個(gè)元素σs的導(dǎo)數(shù)如下：

因此，損失函數(shù)L關(guān)于每一個(gè)σs(s=1，…，r)的梯度為：

4.5 算法復(fù)雜度分析

下面對(duì)WPF 模型的交替優(yōu)化算法進(jìn)行復(fù)雜度分析。由于我們采用了一種迭代的優(yōu)化算法，主要考慮每次迭代過(guò)程中的復(fù)雜度計(jì)算?？紤]到篇幅限制，忽略復(fù)雜度計(jì)算的細(xì)節(jié)推導(dǎo)而直接給出復(fù)雜度結(jié)果。假定給定的矩陣規(guī)模為。在每次迭代過(guò)程中，我們需要對(duì)四個(gè)優(yōu)化變量進(jìn)行更新，其中W根據(jù)HQ 理論給出的閉式解進(jìn)行更新，其復(fù)雜度為O(p·n1n2)，其中為采樣點(diǎn)的比例。對(duì)于U，V的優(yōu)化，主要涉及U，V矩陣的乘積，以及矩陣之間的元素點(diǎn)乘，對(duì)于U，V矩陣的乘積，其復(fù)雜度為O(n1n2r)，元素點(diǎn)乘復(fù)雜度為O(n1n2)，因此U，V更新的復(fù)雜度為O(n1n2r)。最后討論對(duì)于Σ的更新，在計(jì)算Σ梯度中涉及的矩陣乘法的復(fù)雜度為O(r2(n1+n2)+n1n2r)。忽略常數(shù)項(xiàng)，得到WPF 模型的交替優(yōu)化算法的復(fù)雜度為O(n1n2r+r2(n1+n2))，假定n1=n2=n，且r?n，則其復(fù)雜度為O(n2r)。SVD操作的復(fù)雜度為O(n3)，因此我們的方法在理論上的復(fù)雜度要優(yōu)于基于奇異值分解的方法的復(fù)雜度。

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

為了展現(xiàn)所提出的WPF 方法的性能與自動(dòng)秩選擇機(jī)制，我們將提出的WPF方法在合成數(shù)據(jù)與真實(shí)圖像數(shù)據(jù)上進(jìn)行實(shí)驗(yàn)。

實(shí)現(xiàn)了下列四種方法，包括基于l2的PF模型通過(guò)最小二乘法優(yōu)化（L2PF-LS）方法［20］，基于相關(guān)熵的迭代軟閾值方法（CIST）［34］，基于相關(guān)熵的PF 方法通過(guò)最小二乘優(yōu)化（HQPF-LS）方法［35］與基于相關(guān)熵的PF 方法通過(guò)交替最速下降優(yōu)化（PF-ASD）方法［35］，來(lái)代表利用l2范數(shù)的算法，基于SVD 的算法與基于PF 的算法。將這些算法與我們提出的WPF方法進(jìn)行比較。

所有的實(shí)驗(yàn)都是基于一臺(tái)處理器為Intel i5-4590 CPU@3.3 GHz，內(nèi)存為24 GB 的臺(tái)式電腦在MATLAB 2019b環(huán)境下實(shí)現(xiàn)的。矩陣的補(bǔ)全效果用相對(duì)誤差（RE）來(lái)評(píng)估［35］，定義相對(duì)誤差（RE）為：

其中X表示補(bǔ)全出來(lái)的矩陣，M表示真實(shí)無(wú)噪聲且未采樣的矩陣。需要說(shuō)明的是，這里真實(shí)的矩陣M僅在計(jì)算相對(duì)誤差時(shí)使用，在不同方法補(bǔ)全過(guò)程中不會(huì)進(jìn)行使用。

一些在實(shí)驗(yàn)部分常用的符號(hào)我們將其用表1的形式展現(xiàn)出來(lái)。

表1 實(shí)驗(yàn)部分常用符號(hào)與標(biāo)記Tab.1 Notations used frequently in the experiment

為了生成非高斯噪聲的環(huán)境，并模擬異常值，在每次實(shí)驗(yàn)時(shí)先生成一個(gè)全為零的噪聲矩陣，其中隨機(jī)選取ρ0×n1×n2個(gè)元素位置并從一個(gè)四自由度的卡方分布中隨機(jī)采樣得到噪聲數(shù)值，然后將噪聲矩陣E作用于實(shí)驗(yàn)數(shù)據(jù)來(lái)模擬非高斯環(huán)境下的噪聲。

5.1 合成數(shù)據(jù)

我們將上述算法在六種不同的秩的估計(jì)下，在兩個(gè)不同的ρs以及兩個(gè)不同的ρo條件下進(jìn)行實(shí)驗(yàn)。并將五種算法的性能結(jié)果與運(yùn)行時(shí)間列在表2 中。L2PF-LS 與HQPF-LS 方法采用LS 方法進(jìn)行優(yōu)化，不同于梯度下降的方法其不需要較多次數(shù)的迭代，因此其在時(shí)間復(fù)雜度上優(yōu)勢(shì)明顯，但其問(wèn)題在于求解精度不高，且在不同情況下表現(xiàn)非常不穩(wěn)定。在分析中，我們主要對(duì)比CIST，PF-ASD與WPF三種算法的運(yùn)行時(shí)間。表格中的Inf表示該次優(yōu)化未能收斂，從而達(dá)到迭代次數(shù)后得到一個(gè)偏離結(jié)果非常大的值，超出數(shù)值表示范圍。將性能結(jié)果中表現(xiàn)最佳的結(jié)果用加粗的內(nèi)容來(lái)表示。

表2 合成數(shù)據(jù)不同采樣率不同噪聲率不同預(yù)估秩參數(shù)下矩陣補(bǔ)全效果與效率Tab.2 Matrix completion performance and efficiency on synthetic data under different sampling rates，different noise rates，and different estimated rank parameters

通過(guò)表2 結(jié)果，可以看到：第一，基于相關(guān)熵的方法在面對(duì)非高斯噪聲時(shí)能較好地進(jìn)行矩陣補(bǔ)全，而基于l2范數(shù)的方法受到噪聲的嚴(yán)重影響導(dǎo)致補(bǔ)全失?。坏诙?，相較于基于SVD 的CIST 方法，基于PF的PF-ASD的方法與我們提出的WPF的方法在給定一個(gè)較大范圍的預(yù)估參數(shù)re下其效率都比CIST 方法要高。我們提出的WPF 方法在相對(duì)較小的re下補(bǔ)全效率上較有優(yōu)勢(shì)，隨著re的增加，WPF 方法中對(duì)于Σ的優(yōu)化相較于其他參數(shù)復(fù)雜度增加較多，使得WPF的效率逐步降低。而觀察到PF-ASD方法效率隨著re增加逐步變高，可能因增加了re使得其優(yōu)化變量的維度進(jìn)一步增大，從而使其方法更易落入一個(gè)局部最優(yōu)值，因而更快地收斂，由此也可以看到PF-ASD 方法的補(bǔ)全性能也在逐步降低。第三，WPF 方法在不同的re下可以獲得一個(gè)穩(wěn)定的結(jié)果，其可以表示W(wǎng)PF 模型通過(guò)自動(dòng)秩選擇機(jī)制以確定一個(gè)最優(yōu)的秩，因此在不同的re下，其都能保持一個(gè)較為穩(wěn)定的結(jié)果。第四，WPF 方法在所有方法中的性能達(dá)到最優(yōu)，相較于PF-ASD，其能達(dá)到更優(yōu)的效果，這說(shuō)明了WPF模型中引入的輔助變量可以更好地學(xué)習(xí)不同秩1 分量間的度量關(guān)系，從而賦予它們不同的權(quán)重，以獲得一個(gè)更好地的補(bǔ)全效果。

5.2 真實(shí)圖像數(shù)據(jù)

更進(jìn)一步，我們考慮將不同的方法用于真實(shí)圖像數(shù)據(jù)。一個(gè)具體的應(yīng)用場(chǎng)景是單像素成像［36］，需要使用單個(gè)像素來(lái)對(duì)一幅完整的圖像進(jìn)行成像。但對(duì)每個(gè)元素進(jìn)行采樣會(huì)消耗大量的時(shí)間，因此希望通過(guò)采樣少數(shù)的像素點(diǎn)，來(lái)恢復(fù)出完整的圖像，從而加速成像的過(guò)程。在采樣的過(guò)程中，因?yàn)椴僮鞯膯?wèn)題或者器件本身的問(wèn)題，不可避免地會(huì)在采樣的數(shù)據(jù)上產(chǎn)生噪聲，在這里我們同樣考慮現(xiàn)實(shí)中更為常見(jiàn)的非高斯噪聲，在這個(gè)實(shí)驗(yàn)中仍采用卡方分布產(chǎn)生的噪聲矩陣。在這個(gè)實(shí)驗(yàn)中，參數(shù)設(shè)置與合成數(shù)據(jù)中的設(shè)置基本一致，除了將γ設(shè)為1000，并在每個(gè)迭代過(guò)程中將其減少一半，直至其值小于5后保持不變，這是因?yàn)楝F(xiàn)實(shí)中的圖像，通常只能將其視為一個(gè)近似低秩的矩陣，而非合成數(shù)據(jù)中真實(shí)低秩的矩陣，因此我們加強(qiáng)對(duì)稀疏的約束，使其找到一個(gè)盡量低秩的結(jié)果而不要受限于高秩矩陣的局部最優(yōu)點(diǎn)。

在圖1～圖3 中，呈現(xiàn)了三個(gè)具有典型代表的灰度圖片在不同的采樣率、噪聲率與預(yù)先設(shè)定的re下用不同的方法恢復(fù)的效果。如同合成數(shù)據(jù)中所看到的，基于l2的L2PF-LS 方法無(wú)法完成重構(gòu)的任務(wù)，相較于基于SVD 的CIST 方法，基于PF 的方法在恢復(fù)效率上有較大的優(yōu)勢(shì)。我們提出的WPF 方法在恢復(fù)的精度上達(dá)到了最優(yōu)。

圖1 城堡圖像不同方法恢復(fù)性能對(duì)比（E：相對(duì)誤差（%），T：時(shí)間（s）），ρs=0.5，ρo=0.5，re=15Fig.1 Image inpainting performance comparison of different methods on castle image（E：relative error（%），T：time（s））with ρs=0.5，ρo=0.5，re=15

圖2 門圖像不同方法恢復(fù)性能對(duì)比（E：相對(duì)誤差（%），T：時(shí)間（s）），ρs=0.5，ρo=0.3，re=20Fig.2 Image inpainting performance comparison of different methods on door image（E：relative error（%），T：time（s））with ρs=0.5，ρo=0.3，re=20

圖3 Lena圖像不同方法恢復(fù)性能對(duì)比（E：相對(duì)誤差（%），T：時(shí)間（s）），ρs=0.7，ρo=0.2，re=30Fig.3 Image inpainting performance comparison of different methods on Lena image（E：relative error（%），T：time（s））with ρs=0.7，ρo=0.2，re=30

希望進(jìn)一步探究我們提出的方法在自動(dòng)秩選擇機(jī)制上的作用，通過(guò)比較不同預(yù)估re值下的恢復(fù)相對(duì)誤差RE 來(lái)說(shuō)明WPF 模型的自動(dòng)秩選擇機(jī)制。由于CIST 方法是基于SVD 的方法，L2PF-LS 無(wú)法完成實(shí)驗(yàn)，而HQPF-LS 方法在不同的re下表現(xiàn)不穩(wěn)定，因此在這個(gè)部分比較PF-ASD 方法與我們提出的WPF 方法。由于這部分實(shí)驗(yàn)適合針對(duì)單張圖像進(jìn)行實(shí)驗(yàn)，我們對(duì)多幅圖像進(jìn)行了測(cè)試，在圖4中僅給出有代表性的城堡圖像與門圖像的對(duì)比結(jié)果，其他圖像結(jié)果相近，在此不再贅述。

圖4 不同re下PF-ASD與WPF的矩陣補(bǔ)全相對(duì)誤差Fig.4 The completion relative errors of PF-ASD and WPF under different re

對(duì)于兩個(gè)實(shí)驗(yàn)，我們均設(shè)置ρs=0.5，ρo=0.5。在圖4 的RE-Rank 的曲線圖中，可以看到在初始秩參數(shù)設(shè)定過(guò)小時(shí)，PF-ASD 與WPF 均不能很好地補(bǔ)全圖像。隨著秩參數(shù)逐漸接近真實(shí)圖像的秩，兩種方法的補(bǔ)全性能都逐漸增強(qiáng)。隨著秩參數(shù)的進(jìn)一步增加，PF-ASD 的補(bǔ)全效果顯著惡化，因?yàn)椴痪_的秩參數(shù)使其無(wú)法較好地對(duì)圖像進(jìn)行重構(gòu)。而WPF 在較大的秩參數(shù)下影響較小，因其可以自適應(yīng)地對(duì)秩進(jìn)行選擇，將不必要的秩進(jìn)行擯棄，從而達(dá)到近似于精確秩參數(shù)下的性能。從圖中可以直觀地看到WPF模型的自動(dòng)秩選擇機(jī)制，給一個(gè)相對(duì)較大的re，WPF模型均可以收斂到比較好的結(jié)果，即其可以選擇一個(gè)比較好的秩。結(jié)果也進(jìn)一步說(shuō)明，當(dāng)給定的秩較小時(shí)，WPF 模型無(wú)法發(fā)揮很大的優(yōu)勢(shì)。從圖4（b）中，還可以更明顯地看到，WPF 能達(dá)到的最優(yōu)值優(yōu)于PF-ASD，說(shuō)明在這幅圖像中，不同秩1分量間權(quán)重不同會(huì)對(duì)結(jié)果產(chǎn)生較大的影響。

上述實(shí)驗(yàn)主要是針對(duì)單張圖像進(jìn)行的矩陣補(bǔ)全，為了進(jìn)一步檢驗(yàn)我們提出的WPF 方法的性能，從Caltech101 中選擇向日葵類圖像，為了避免不同尺寸大小的圖與不同秩圖像對(duì)結(jié)果的影響，首先篩除一些明顯不類似的圖像，余下45 張圖像。對(duì)這45 張圖像將其尺寸歸一化到200 × 200，并利用奇異值分解的方法將其用前20個(gè)奇異值分量來(lái)表示，以此來(lái)進(jìn)行實(shí)驗(yàn)。在不同的噪聲率與采樣率下，選擇不同的估計(jì)re值，并對(duì)每種情況進(jìn)行30 次獨(dú)立實(shí)驗(yàn)以求得結(jié)果平均值。將不同算法的性能結(jié)果與運(yùn)行時(shí)間列在表3中。需要說(shuō)明的是在此處對(duì)圖像進(jìn)行奇異值分解來(lái)計(jì)算前20個(gè)奇異值分量，是為了避免不同圖像間的性能干擾，以得到更適合不同方法性能對(duì)比的圖像數(shù)據(jù)集。這些方法都可以針對(duì)單幅圖像進(jìn)行實(shí)驗(yàn)，對(duì)單幅圖像的實(shí)驗(yàn)中，不需要事先對(duì)圖像進(jìn)行奇異值分解。

表3 向日葵圖像不同采樣率不同噪聲率不同預(yù)估秩參數(shù)下矩陣補(bǔ)全效果與效率Tab.3 Matrix completion performance and efficiency on sunflower image under different sampling rates，different noise rates，and different estimated rank parameters

表3 中真實(shí)圖像結(jié)果與仿真數(shù)據(jù)結(jié)果基本一致，需要注意的一點(diǎn)是，我們提出的WPF 模型利用稀疏的方式來(lái)對(duì)模型的秩進(jìn)行自動(dòng)的選擇，由此，首先需要給定較為充足的秩來(lái)讓其進(jìn)行稀疏化。因此，當(dāng)給定一個(gè)較小的re時(shí)，其并不能做到模型的自動(dòng)選擇，其效果與PF方法基本相當(dāng)，當(dāng)秩過(guò)小時(shí)，補(bǔ)全效果受到過(guò)低的秩的約束而表現(xiàn)不佳。上述實(shí)驗(yàn)結(jié)果表明了我們的方法在真實(shí)圖像上也能有很好地應(yīng)用。

此外，我們進(jìn)一步探究矩陣補(bǔ)全算法在圖像修復(fù)中的應(yīng)用。在這一部分，主要意圖在于探究矩陣補(bǔ)全算法更廣闊的應(yīng)用范圍，因此只采用我們提出的WPF 方法，并且通過(guò)恢復(fù)圖像的直觀結(jié)果進(jìn)行分析。

圖像修復(fù)任務(wù)中通常會(huì)遇到圖像中部分內(nèi)容受損的情況。在圖5 中，我們?nèi)藶榈貙?duì)彩色的lena圖像中加入一些污染，這些污染在真實(shí)圖像處理中經(jīng)常會(huì)碰到，比如一些老照片的部分區(qū)域可能遭遇各種情況的破壞，這時(shí)候，我們可以通過(guò)WPF 方法來(lái)恢復(fù)原始的圖像。通過(guò)補(bǔ)全圖像結(jié)果可以看到WPF 方法能夠?qū)⑹艿轿廴镜膱D像較好地進(jìn)行補(bǔ)全。值得說(shuō)明的是對(duì)于一幅彩色采樣圖像，可以將三個(gè)通道分離，對(duì)每個(gè)通道進(jìn)行獨(dú)立恢復(fù)，最后將三個(gè)通道重新組合，從而實(shí)現(xiàn)彩色圖像的矩陣補(bǔ)全。

圖5 彩色部分受損圖像WPF補(bǔ)全效果圖Fig.5 Completion result of WPF on partially damaged color image

我們進(jìn)一步考慮矩陣補(bǔ)全算法在修復(fù)一些圖像上固有的缺陷上的應(yīng)用。在一些圖片中，本身圖片就存在一些缺陷希望能夠進(jìn)行補(bǔ)全，比如圖6 中一些窗戶存在破損的情況，影響了整幅圖像的觀感，在這種情況下，可以將這些破損的地方視作沒(méi)有采樣的點(diǎn)，從而利用WPF 方法來(lái)對(duì)其進(jìn)行補(bǔ)全，從補(bǔ)全結(jié)果中可以看到WPF 方法可以有效地將圖像中本身存在的破損進(jìn)行補(bǔ)全。

圖6 彩色固有缺陷圖像WPF補(bǔ)全效果圖Fig.6 Completion result of WPF on inherently defective color images

6 結(jié)論

在本論文中，我們提出了一種Weighted Power Factorization（WPF）的模型來(lái)完成矩陣補(bǔ)全問(wèn)題。通過(guò)引入一個(gè)輔助變量，WPF 模型不僅擁有PF 模型中已有的優(yōu)勢(shì)，即通過(guò)事先對(duì)矩陣進(jìn)行分解從而避免奇異值分解的操作來(lái)減少計(jì)算復(fù)雜度，而且其可以減緩PF 模型中存在的需要對(duì)模型秩進(jìn)行精確估計(jì)的問(wèn)題，并且避免PF 模型中對(duì)各個(gè)秩1 分量賦予相等權(quán)重的問(wèn)題。我們考慮當(dāng)觀測(cè)到的矩陣元素受到非高斯噪聲污染的情況。利用信息論理論并結(jié)合相關(guān)熵，我們的WPF模型可以有效應(yīng)對(duì)魯棒矩陣補(bǔ)全問(wèn)題。首先利用HQ 理論來(lái)對(duì)WPF 模型的建模進(jìn)行轉(zhuǎn)換，隨后采取交替梯度下降的方法來(lái)進(jìn)行優(yōu)化。在合成數(shù)據(jù)與真實(shí)圖像上的不同方法間的性能與效率的比較結(jié)果上來(lái)看，我們提出的WPF 方法擁有模型自動(dòng)秩選擇的機(jī)制，并且相較于傳統(tǒng)的基于SVD或者PF的方法 WPF方法具有更優(yōu)良的性能。更進(jìn)一步地，我們探究了WPF方法在更多圖像修復(fù)上的應(yīng)用。