低秩張量填充的隨機算法

郭雄偉，王川龍

（太原師范學院 數(shù)學系，山西 晉中030619）

0 引言

張量填充（TC）問題是張量研究中最活躍的熱點之一.張量填充可以應(yīng)用于很多領(lǐng)域，如圖像恢復(fù)［1，2］、數(shù)據(jù)挖掘［3］、信號處理、機器學習［4］、高階網(wǎng)絡(luò)鏈接分析［5］等.張量填充問題可以表述為如下形式：

其中A，Γ都是n-模張量，且每個模的大小相同，rank（A）表示張量A的某種秩，PΩ是集合Ω上的正交投影，Ω是基數(shù)為m的隨機子集，其中m是采樣元素的個數(shù).當（i1，i2，…，in）∈Ω時，PΩ（A）的第（i1，i2，…，in）個元素等于Γi1i2…in，否則等于0.張量的秩的計算是NP-難問題.因此，一些學者將模型（1）松弛為如下凸優(yōu)化模型：

其中αi≥0且張量填充問題可以看作是矩陣填充問題的高維形式.

在張量填充的優(yōu)化算法方面，已有一些研究成果.文獻［6］中Liu等人給出了張量的核范數(shù)的定義，并基于模型（2）提出了三種有效算法：簡單低秩張量填充算法（Simple Low Rank Tensor Completion algorithm，SiLRTC）、快速低秩張量填充算法（Fast Low Rank Tensor Completion algorithm，F(xiàn)aLRTC）以及高精度低秩張量填充算法（High accuracy Low Rank Tensor Completion algorithm，HaLRTC）.在文獻［7］中，Gandy等人用張量的秩作為稀疏表示，將其模型轉(zhuǎn)換為更容易求解的凸模型，提出了張量恢復(fù)的Douglas-Rachford算法（Douglas-Rachford splitting algorithm for Tensor Recovery）以及交替方向乘子法（Alternating direction method of multipliers）.受矩陣填充算法的啟發(fā)，Tan等人［8］將張量填充問題矩陣化為n個矩陣填充問題，提出了低多線性秩張量填充（Low Multilinear Rank Tensor Completion，LMRTC）算法.為了保持張量原有的內(nèi)部結(jié)構(gòu)以及避免矩陣化的計算花費，Kilmer等人［9］提出了張量的奇異值分解，且能夠很好地保留張量原有的內(nèi)部結(jié)構(gòu)信息.基于張量的奇異值分解和管秩的定義，Zhang等人［10］利用交替方向乘子法框架，給出了相應(yīng)的算法.此外，還有很多學者研究張量的CP秩以及基于CP秩的張量填充算法，詳見文獻［11-13］.

本文主要研究張量填充問題.基于Liu等人［6］提出的高精度低秩張量填充算法，引入隨機的思想，并給出相應(yīng)的算法，同時通過數(shù)值實驗和圖像填充驗證算法的有效性.

本文的結(jié)構(gòu)安排如下：第1節(jié)介紹張量及矩陣的相關(guān)符號說明和定義；第2節(jié)回顧高精度低秩張量填充算法，在此算法的基礎(chǔ)上引入隨機的思想，給出隨機高精度低秩張量填充算法的具體步驟；第3節(jié)通過數(shù)值實驗以及圖像填充與HaLRTC及DR-TR算法比較，驗證算法的有效性；第4節(jié)對全文進行總結(jié).

1 符號說明及定義

為方便起見，RI1×I2表示I1×I2的實矩陣全體.矩陣的核范數(shù)和F-范數(shù)分別表示為‖X‖＊和‖X‖F(xiàn).矩陣的內(nèi)積表示為表示n-模張量，它的元素表示為，其中表示張量的模-k展開.與其相反的運算定義為表示張量Χ的秩.用表示張量的F-范數(shù).

定義1（奇異值分解（SVD））［14］秩r的矩陣，則必存在正交矩陣滿足：

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

定義2（奇異值閾值算子）［15］對于任意參數(shù)τ≥0，奇異值閾值算子Dτ定義為：

2 算法

文獻［6］基于模型（2），并結(jié)合交替方向乘子法（ADMM）框架，給出了高精度低秩張量填充算法.該算法具有較好的填充效果，其算法如下：

算法1 高精度低秩張量填充算法（High accuracy Low Rank Tensor Completion algorithm，簡稱HaLRTC）［6］

給定采樣集合Ω，采樣矩陣PΩ（Γ），參數(shù)αi，ρ0，t，ε，以及初始張量0，k：=0；

第1步：計算

第3步：若‖Χk+1-Χk‖F(xiàn)／‖Χk‖F(xiàn)＜ε，停止迭代；否則轉(zhuǎn)第4步.

由算法1可知，在每次迭代過程中，該算法需要計算n次奇異值分解，張量展開以及矩陣折疊，需要較大的計算花費.在此算法的基礎(chǔ)上，我們引入隨機的思想，即在每次迭代過程中，只對隨機產(chǎn)生的一個模進行奇異值分解，張量展開以及矩陣折疊，減少了計算花費.其算法如下：

算法2 低秩張量填充的隨機算法（Low Rank Tensor Completion Random algorithm，簡稱LRTCR）

給定采樣集合Ω，采樣矩陣PΩ（Γ），參數(shù)αi，ρ0，t，ε，以及初始張量0，k：=0；

第1步：令

第3步：若‖Χk+1-Χk‖F(xiàn)／‖Χk‖F(xiàn)＜ε，停止迭代；否則轉(zhuǎn)第4步；

3 數(shù)值實驗

本節(jié)通過隨機張量填充和圖像填充將新算法與HaLRTC以及DR-TR算法比較.

3.1 隨機張量填充

在本小節(jié)中，利用隨機生成的維數(shù)為50×50×50，50×60×70的秩分別為（2，2，2）和（5，5，5）的三維張量，在采樣率為0.2，0.3，0.4的情況下，比較其實驗結(jié)果，實驗結(jié)果見表1、表2、表3.Χ＊表示這三種算法的輸出張量，Γ為原始張量.

表1 p=0.2時，算法LRTCR與算法HaLRTC、DR-TR比較

表2 p=0.3時，算法LRTCR與算法HaLRTC、DR-TR比較

表3 p=0.4時，算法LRTCR與算法HaLRTC、DR-TR比較

3.2 圖像填充

在本小節(jié)中，使用維數(shù)為181×217×181的立體MRI①http：／／brainweb.bic.mni.mcgill.ca／brainweb／selection normal.html.數(shù)據(jù)比較新算法與HaLRTC及DR-TR算法的填充效果.隨機選取MRI數(shù)據(jù)中的某一切片，在采樣率分別為0.2，0.3，0.4的情況下，其填充效果見圖1.為了直觀展現(xiàn)其填充效率，表4中展示填充時間、迭代次數(shù)以及相對誤差.

圖1 填充效果圖

表4 MRI在不同采樣率下，算法LRTCR、HaLRTC、DR-TR比較

續(xù)表4

4 總結(jié)

本文提出了一種新的高精度低秩張量填充隨機算法，簡稱LRTCR.該算法在原有的算法的基礎(chǔ)上，引入隨機的思想，有效地降低了算法在每次迭代過程中的計算花費.由表1-3可以看出，新算法與原有的算法相比，精度上大致相同，但新算法在時間花費上占有很大優(yōu)勢.此外，由圖1及表4可以看出，針對MRI圖像填充，新算法同樣占有優(yōu)勢.