非凸低秩張量補全的隨機算法

南佳琨,王川龍*

(太原師范學院 數學與統計學院 山西省智能優化計算與區塊鏈技術重點實驗室,山西 晉中 030619)

0 引言

張量是向量和矩陣的高階推廣,隨著信息的飛速發展,關于張量及其應用的研究受到越來越多的關注,張量補全更是成為許多學者的研究熱點之一.張量補全可以應用到圖像恢復[1,2]、數據挖掘[3]、機器學習[4]及信號處理[5]等領域.張量補全是指從存在缺失、污染的數據中恢復原始數據,其數學模型為:

(1)

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

(2)

(3)

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

(4)

1 符號和預備知識

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

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

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

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

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

2 算法

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

(5)

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

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

第2步:計算

fori=1∶Ndo

end for

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

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

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

3 收斂性分析

假設A

其中第一項為

(6)

第二項可以被表示為

(7)

證明

(8)

(9)

在算法2中,對

(10)

4 數值實驗

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

4.1 隨機張量補全

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

表1 當p=0.3時,算法SADMM、LRTC-Log、HaLRTC的比較

表2 當p=0.2時,算法SADMM、LRTC-Log、HaLRTC的比較

表3 當p=0.1時,算法SADMM、LRTC-Log、HaLRTC的比較

實驗結果表明,新算法比LRTC-Log算法和HaLRTC算法所需的CPU時間更少且精度好.

4.2 圖像填充

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

表4 “lena”圖像在不同采樣率下,三個算法的比較

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

5 總結

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