一種求解矩陣填充問(wèn)題的混合增廣拉格朗日乘子算法

一種求解矩陣填充問(wèn)題的混合增廣拉格朗日乘子算法

0混合增廣拉格朗日乘子矩陣填充算法近年來(lái)，矩陣填充問(wèn)題引起了許多科學(xué)家的研究興趣。矩陣填充問(wèn)題是將已知的元素嵌入樣本矩陣，并使用重建的低秩矩陣接近樣本矩陣，這與計(jì)算機(jī)視覺(jué)接近。矩陣填充問(wèn)題首次由Cand’es和Recht有關(guān)凸優(yōu)化問(wèn)題（1）的研究，已經(jīng)有大量的成果．例如，F(xiàn)azel本文提出的混合型增廣拉格朗日乘子矩陣填充算法是通過(guò)定義混合型奇異值閾值算子，將經(jīng)典的增廣拉格朗日乘子算法進(jìn)行改進(jìn)后得到的．具體是對(duì)ALM算法運(yùn)行中奇異值分解所產(chǎn)生的閾值進(jìn)行混合型奇異值閾值算子處理．當(dāng)?shù)螖?shù)逐漸增加時(shí)，就會(huì)發(fā)現(xiàn)在奇異值數(shù)量減少，奇異值的數(shù)值減小的同時(shí)，矩陣填充的計(jì)算效率極大提高，從而節(jié)約了計(jì)算花費(fèi)．因此，新算法在求解矩陣填充問(wèn)題上明顯優(yōu)于經(jīng)典的增廣拉格朗日乘子算法．首先先給出一些定義：其中σ定義2（硬閾值算子）其中變量σ∈R，τ是閾值．定義3（軟閾值算子）其中變量σ定義4（奇異值閾值算子）在本文中，我們提出一種新的混合型奇異值閾值算子：當(dāng)閾值σ定義5（混合型奇異值閾值算子）對(duì)于任意參數(shù)τ≥0,z>1，矩陣的秩是r,其中也就是說(shuō)，當(dāng)σ1該算法1.1增廣拉格朗日乘子算法在這一節(jié)中，我們簡(jiǎn)要介紹增廣拉格朗日乘子算法，以便于后文數(shù)值實(shí)驗(yàn)中算法比較．增廣拉格朗日乘子法表示矩陣的奇異值分解，算法1增廣拉格朗日乘子法（ALM算法）給定采樣集合Ω，采樣矩陣D=P1.2基于lam的新算法在這一節(jié)中，我們提出新算法．具體步驟如下：算法2混合增廣拉格朗日乘子（HALM）算法．給定采樣集合Ω，采樣矩陣D=P第3-4步同ALM算法．與ALM算法相比，我們提出的新算法HALM是在其基礎(chǔ)上進(jìn)行改進(jìn)后得到的，具體是將ALM算法運(yùn)行中奇異值分解所產(chǎn)生的閾值進(jìn)行混合型奇異值閾值算子處理．在數(shù)值實(shí)驗(yàn)中，我們發(fā)現(xiàn)，當(dāng)?shù)螖?shù)逐漸增加時(shí)，奇異值數(shù)量減少，奇異值的數(shù)值也在減小，矩陣填充的計(jì)算效率極大提高，從而節(jié)約了計(jì)算花費(fèi)，進(jìn)而優(yōu)化了算法．2新算法halm中的混合閾值算子的運(yùn)行時(shí)間在本節(jié)中，我們對(duì)ALM算法和HALM算法進(jìn)行了比較，所有的數(shù)值實(shí)驗(yàn)都是在機(jī)器類(lèi)型為Intel(R)Core(TM)i7-6700CPU@3.40GHZ，內(nèi)存16GB,Windows7系統(tǒng)的個(gè)人機(jī)上用Matlab(R2016a）進(jìn)行的，也就是說(shuō)實(shí)驗(yàn)中所選取的M和P在數(shù)值實(shí)驗(yàn)中，M∈R此外，對(duì)于兩個(gè)算法，我們選取參數(shù)τ接下來(lái)，在新算法HALM中混合閾值算子中參數(shù)z的選擇，我們選取了n=1000,1500,2000的矩陣，比較不同的z和n在運(yùn)行時(shí)間上的差異．當(dāng)n=1000,1500,2000時(shí)，新算法HALM的運(yùn)行時(shí)間始終隨著z的變化而變化，而當(dāng)參數(shù)z選取z=1.4時(shí)，新算法HALM的運(yùn)行時(shí)間普遍較低．因此，在新算法HALM中，我們選擇混合閾值算子的參數(shù)z=1.4.從4個(gè)表中我們看到新算法HALM在計(jì)算時(shí)間上總是少于ALM算法的．針對(duì)同規(guī)模的矩陣而言，隨著采樣率p的增加，新算法HALM和ALM算法的迭代次數(shù)相差不大，但新算法HALM在時(shí)間上明顯少于ALM算法；針對(duì)相同的采樣率而言，隨著矩陣大小的變化，當(dāng)p∈{0.3,0.4,0.5,0.6}時(shí)，新算法HALM的收斂性和運(yùn)行時(shí)間都優(yōu)于ALM算法，特別是矩陣規(guī)模越大越明顯，這些都說(shuō)明新算法HALM的有效性和可行性．3增廣拉格朗日乘子算法本文先提出了一種新的閾值算子：混合型奇異值閾值算子．然后將該算子與經(jīng)典的算法增廣拉格朗日算法相結(jié)合，得到了一種新的矩陣填充算法，即混合型增廣拉格朗日乘子算法．與增廣拉格朗日乘子算法相比，該算法具有更高的精度．由表1-4可以看出，在相同參數(shù)下，我們的算法在運(yùn)行時(shí)間上明顯優(yōu)于增廣拉格朗日乘子算法．在新提出的算法中，對(duì)閾值的混合處理節(jié)省了大部分時(shí)間，能夠有效地填充矩陣．這些都是基于一般