南佳琨,王川龍*

(太原師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院 山西省智能優(yōu)化計(jì)算與區(qū)塊鏈技術(shù)重點(diǎn)實(shí)驗(yàn)室,山西 晉中 030619)

0 引言

張量是向量和矩陣的高階推廣,隨著信息的飛速發(fā)展,關(guān)于張量及其應(yīng)用的研究受到越來越多的關(guān)注,張量補(bǔ)全更是成為許多學(xué)者的研究熱點(diǎn)之一.張量補(bǔ)全可以應(yīng)用到圖像恢復(fù)[1,2]、數(shù)據(jù)挖掘[3]、機(jī)器學(xué)習(xí)[4]及信號(hào)處理[5]等領(lǐng)域.張量補(bǔ)全是指從存在缺失、污染的數(shù)據(jù)中恢復(fù)原始數(shù)據(jù),其數(shù)學(xué)模型為:

(1)

與矩陣的秩不同,張量的秩是更復(fù)雜的.在現(xiàn)有的工作中,張量的秩可以表示為多種形式,如CP秩[6],Tucker秩[7],張量火車(TT)秩[8],張量環(huán)(TR)秩[9]等等.本文主要討論Tucker秩模型.當(dāng)Tucker秩是已知的情況下,張量由HOSVD生成的核心張量和因子矩陣組成[10].當(dāng)模型(1)的秩為Tucker秩時(shí),可以寫成如下形式:

(2)

(3)

并提出三種有效算法來求解此凸模型.Gandy等[12]用張量的秩作為稀疏表示,提出張量恢復(fù)問題的Douglas-Rachford算法.Ng等[13]通過考慮不同展開矩陣所起的作用不同賦予不同的權(quán)重,給出了自適應(yīng)加權(quán)張量核范數(shù)模型,該模型對(duì)張量按模展開的矩陣進(jìn)行了有效地平衡,從而獲得更好的補(bǔ)全結(jié)果.王川龍等[14]基于模型(3)利用隨機(jī)思想設(shè)計(jì)高效的交替方向法,進(jìn)一步減少計(jì)算復(fù)雜度提高算法效率.低秩張量補(bǔ)全的凸松弛模型能收斂到全局最優(yōu)解并且有很好的理論保證.但是在很多情況下,凸松弛模型的解并不能很好地近似原問題的解.為此,非凸逼近模型受到了關(guān)注.Li等[15]給出一種用張量每個(gè)模展開的p-范數(shù)近似Tucker秩的非凸Schatten-p范數(shù)模型,并采用交替方向乘子法求解此問題.Ji等[16]提出了一種基于對(duì)張量的每種模式展開進(jìn)行對(duì)數(shù)加權(quán)求和的非凸對(duì)數(shù)函數(shù)模型來逼近低Tucker秩張量模型,其對(duì)數(shù)函數(shù)(Log-Det)模型為:

(4)

1 符號(hào)和預(yù)備知識(shí)

定義1(奇異值分解(SVD)[17]) 對(duì)于秩為r的矩陣X∈I1×I2,則必存在正交矩陣U∈I1×r和V∈I2×r,滿足

X=UΣrVT,Σr=diag(σ1,σ2,…,σr),

其中σ1≥σ2≥…≥σr≥0.

定義2(矩陣核范數(shù)的次微分[18]) 對(duì)于秩為r的矩陣A∈I1×I2,存在奇異值分解A=UΣrVT,則的次微分為:

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

2 算法

通過引入輔助變量,模型(4)可以等價(jià)為如下模型:

(5)

文獻(xiàn)[16]基于模型(4),并結(jié)合交替方向乘子法(ADMM)框架,給出如下算法求解非凸對(duì)數(shù)函數(shù)模型.該算法具有較好的補(bǔ)全效果,其算法如下:

算法1基于Log-Det的低秩張量補(bǔ)全(LRTC-Log)算法.

第2步:計(jì)算

fori=1∶Ndo

end for

由算法1可以看出,在每次迭代過程中,都需要計(jì)算N次奇異值分解,此時(shí)花費(fèi)時(shí)間較大,引入隨機(jī)思想,使得每次迭代過程中,隨機(jī)選取一個(gè)張量模展開面進(jìn)行奇異值分解,大大減少了計(jì)算時(shí)間.其算法如下:

算法2基于Log-Det的隨機(jī)ADMM算法(SADMM)

第1步:令Rk+1=randperm(N,1),

3 收斂性分析

假設(shè)A

其中第一項(xiàng)為

(6)

第二項(xiàng)可以被表示為

(7)

證明

(8)

(9)

在算法2中,對(duì)

(10)

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

將算法2與算法1,HaLRTC算法在隨機(jī)張量補(bǔ)全,圖像修復(fù)的數(shù)值試驗(yàn)中進(jìn)行比較,從而證明算法2的有效性.所有數(shù)值代碼均在Matlab(R2019b)軟件編寫,運(yùn)行環(huán)境為戴爾(DELL)PowerEdge R740xd高性能2U機(jī)架式并行運(yùn)算服務(wù)器.

4.1 隨機(jī)張量補(bǔ)全

在隨機(jī)生成的數(shù)據(jù)上比較所提出的算法,隨機(jī)張量通過張量的Tucker分解生成:

表1 當(dāng)p=0.3時(shí),算法SADMM、LRTC-Log、HaLRTC的比較

表2 當(dāng)p=0.2時(shí),算法SADMM、LRTC-Log、HaLRTC的比較

表3 當(dāng)p=0.1時(shí),算法SADMM、LRTC-Log、HaLRTC的比較

實(shí)驗(yàn)結(jié)果表明,新算法比LRTC-Log算法和HaLRTC算法所需的CPU時(shí)間更少且精度好.

4.2 圖像填充

圖1 (a)(f)(k)為原始彩色圖像,(b)(g)(l)分別為采樣0.3,0.2,0.1的圖像,(c)(h)(m)為SADMM算法的補(bǔ)全圖像,(d)(i)(n)為L(zhǎng)RTC-Log算法的補(bǔ)全圖像,(e)(j)(o)為HaLRTC算法的補(bǔ)全圖像

表4 “l(fā)ena”圖像在不同采樣率下,三個(gè)算法的比較

針對(duì)彩色圖片填充的實(shí)際問題,表4可以看出,在時(shí)間花費(fèi)上,新算法明顯少于其他兩種算法,修復(fù)效果較好.

5 總結(jié)

基于非凸對(duì)數(shù)函數(shù)的張量補(bǔ)全,引入一種隨機(jī)算法.該算法在迭代過程中,不需要對(duì)每一步的所有變量進(jìn)行更新,只隨機(jī)選取一個(gè)子問題進(jìn)行優(yōu)化,大大減少了計(jì)算量,提高了計(jì)算效率.隨后在一定假設(shè)條件下,證明了算法的收斂性.最后,通過隨機(jī)張量補(bǔ)全數(shù)值實(shí)驗(yàn)可以看出,新算法比其他算法的花費(fèi)時(shí)間少且精確度好,對(duì)比彩色圖像修復(fù)實(shí)驗(yàn),新算法同樣在時(shí)間上占據(jù)一定的優(yōu)勢(shì).