Toeplitz矩陣填充的加速臨近梯度截?cái)嗨惴?/h1>
2021-11-10 11:13閆喜紅姬路鑫
閆喜紅, 姬路鑫, 王 政
(太原師范學(xué)院a. 數(shù)學(xué)系; b. 管理系, 太原 030619)
矩陣填充問(wèn)題因在機(jī)器學(xué)習(xí)[1]、圖像恢復(fù)[2]、計(jì)算機(jī)視覺(jué)[3]等領(lǐng)域被廣泛應(yīng)用而備受關(guān)注．Candès等[4]認(rèn)為, 通過(guò)求解優(yōu)化問(wèn)題
min ‖X‖*, s.t.Xij=Mij,?(i,j)∈Ω
(1)
Toeplitz矩陣作為一種特殊的重要矩陣, 在圖像處理, 信號(hào)處理等方面起到了至關(guān)重要的作用[9]．針對(duì)Toeplitz矩陣的特殊結(jié)構(gòu), 王川龍等人利用Toeplitz矩陣的快速奇異值分解算法, 提出了Toeplitz矩陣填充的均值算法[10]和改進(jìn)的増廣Lagrange乘子算法[11]等, 這些算法都能使每步的迭代矩陣保持Toeplitz矩陣結(jié)構(gòu)．眾所周知,加速技巧可以使算法在運(yùn)算效率方面進(jìn)一步提高[8]．本文擬利用文獻(xiàn)[8]中給出的截?cái)嗉夹g(shù),針對(duì)Toeplitz矩陣提出了兩種加速臨近梯度截?cái)嗨惴ǎ?/p>
1 預(yù)備知識(shí)
定義11個(gè)n×n的Toeplitz矩陣定義為
定義2(奇異值分解(singular value decomposition,SVD)) 對(duì)于秩為r的矩陣X∈Rn1×n2, 則必存在正交矩陣U∈Rn1×r和V∈Rn2×r, 使得X=UFrVT, 其中Fr=diag(σ1,…,σr), 式中σ1≥σ2≥…≥σr≥0．
注文獻(xiàn)[8]中提出的APG算法是針對(duì)求解一般矩陣填充問(wèn)題的算法; 而本文要解決的填充問(wèn)題是針對(duì)Toeplitz矩陣的, 故本文提到的APG算法是在文獻(xiàn)[8]的APG算法步3中將矩陣X進(jìn)行Toeplitz化后再進(jìn)行迭代．
2 加速臨近梯度截?cái)嗨惴?/h2>
眾所周知, 對(duì)未運(yùn)用任何加速技巧的APG算法, 迭代矩陣Xk的奇異值通常會(huì)分離成2個(gè)簇, 且第一個(gè)簇的均值比第二個(gè)簇的均值要大得多, 從而可以把第一個(gè)簇類中奇異值的數(shù)量看作模型(1)低秩最優(yōu)解秩的一個(gè)估計(jì)數(shù)．此外, 第二個(gè)簇中較小的正奇異值(在μ/τ附近)可能導(dǎo)致數(shù)據(jù)M中存在噪聲, 故可將第二個(gè)簇中奇異值拋棄而不影響算法的收斂性．因此, 本文提出第一種算法(A), 步驟如圖1所示．
圖1 加速臨近梯度截?cái)嗨惴?A)流程圖Fig.1 Accelerated proximal gradient truncation algorithm(A)
算法A每次迭代過(guò)程中出現(xiàn)的截?cái)喽紩?huì)消耗時(shí)間, 故為了減少計(jì)算量, 提高算法的運(yùn)算效率, 提出了改進(jìn)的算法(B)．算法B的流程如圖2所示．
圖2 w步加速臨近梯度截?cái)嗨惴?B)流程圖Fig.2 w-Steps accelerated proximal gradient truncation algorithm(B)
3 收斂性分析
利用模型(1)的罰函數(shù)可以將Toeplitz矩陣填充問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題:
(2)
假設(shè)1假設(shè)模型(2)存在最優(yōu)解, 記為X*．
假設(shè)2對(duì)于矩陣Xk+1, 如下不等式成立:
證明 根據(jù)文獻(xiàn)[8]中引理2.1, 有F(Xk+1)≤Q(PL(Yk+1),Yk+1)≤Q(Xk+1,Yk+1), 從而
F(X)-F(Xk+1)≥F(X)-Q(Xk+1,Yk+1)．
(3)
又因f,g是凸的, 則f(Xk)≥f(Yk+1)+〈Xk-Yk+1,f(Yk+1)〉,g(Xk)≥g(Xk+1)+〈Xk-Xk+1,μ?‖Xk+1‖*〉．將上述不等式相加, 得F(Xk)≥f(Yk+1)+〈Xk-Yk+1,f(Yk+1)〉+μ‖Xk+1‖*+〈Xk-Xk+1,μ?‖Xk+1‖*〉, 代入式(3), 由假設(shè)2得F(X)-F(Xk+1)≥F(X)-Q(Xk+1,Yk+1)≥〈Xk-Yk+1,f(Yk+1)〉+〈Xk-Xk+1,μ?‖Xk+1‖*〉-〈Xk+1-Yk+1,f(Yk+1)〉-證畢．
證明 由引理1得
(4)
(5)
引理3[12]令{ak,bk}為正實(shí)數(shù)序列, 滿足ak-ak+1≥bk+1-bk, 并且對(duì)任意的k≥1, 有a1+b1≤c,c>0．那么, 對(duì)于任意的k≥1都有ak≤c．
引理4[12]正序列{tk}由算法A或B產(chǎn)生, 對(duì)于t1=1, 滿足任意的k≥1時(shí), 有tk≥(k+1)/2．
4 數(shù)值實(shí)驗(yàn)
通過(guò)數(shù)值實(shí)驗(yàn)比較本文算法與APG算法．計(jì)算機(jī)的CPU為Intel Core i3-4030U, 內(nèi)存4 GB, 操作系統(tǒng)為Windows 8, 所有代碼由MATLAB編寫(xiě)．實(shí)驗(yàn)中, Toeplitz矩陣的維數(shù)n分別取100,200,300,400,500,1 000,2 000,3 000; 采樣率p分別取 0.3,0.4,0.5;Y表示最優(yōu)解;m表示迭代次數(shù); 運(yùn)行時(shí)間t,s;r(X)=5; 參數(shù)Lf=1,ε=10-4．不同算法的數(shù)值實(shí)驗(yàn)結(jié)果對(duì)比見(jiàn)表1．從表1可以看出, 本文提出的2種新算法的迭代次數(shù)均比APG算法少, 運(yùn)行時(shí)間也較短, 且新算法的精度比APG算法更優(yōu)．
表1 不同算法的數(shù)值實(shí)驗(yàn)結(jié)果對(duì)比
猜你喜歡
基于應(yīng)變梯度的微尺度金屬塑性行為研究 云的識(shí)別指南百科探秘·航空航天(2022年6期)2022-06-28 一個(gè)具梯度項(xiàng)的p-Laplace 方程弱解的存在性 均值—方差分析及CAPM模型的運(yùn)用智富時(shí)代(2019年4期)2019-06-01 均值—方差分析及CAPM模型的運(yùn)用智富時(shí)代(2019年4期)2019-06-01 內(nèi)容、形式與表達(dá)——有梯度的語(yǔ)言教學(xué)策略研究福建基礎(chǔ)教育研究(2019年3期)2019-05-28 航磁梯度數(shù)據(jù)實(shí)測(cè)與計(jì)算對(duì)比研究西部資源(2018年1期)2018-11-01 均值不等式的小應(yīng)用發(fā)明與創(chuàng)新·中學(xué)生(2017年5期)2017-05-12 流程圖學(xué)習(xí)指南高中生學(xué)習(xí)·高二版(2014年1期)2014-02-14 應(yīng)用均值定理“四”注意中學(xué)生數(shù)理化·高考版(2008年2期)2008-11-01
閆喜紅, 姬路鑫, 王 政
(太原師范學(xué)院a. 數(shù)學(xué)系; b. 管理系, 太原 030619)
矩陣填充問(wèn)題因在機(jī)器學(xué)習(xí)[1]、圖像恢復(fù)[2]、計(jì)算機(jī)視覺(jué)[3]等領(lǐng)域被廣泛應(yīng)用而備受關(guān)注．Candès等[4]認(rèn)為, 通過(guò)求解優(yōu)化問(wèn)題
min ‖X‖*, s.t.Xij=Mij,?(i,j)∈Ω
(1)
Toeplitz矩陣作為一種特殊的重要矩陣, 在圖像處理, 信號(hào)處理等方面起到了至關(guān)重要的作用[9]．針對(duì)Toeplitz矩陣的特殊結(jié)構(gòu), 王川龍等人利用Toeplitz矩陣的快速奇異值分解算法, 提出了Toeplitz矩陣填充的均值算法[10]和改進(jìn)的増廣Lagrange乘子算法[11]等, 這些算法都能使每步的迭代矩陣保持Toeplitz矩陣結(jié)構(gòu)．眾所周知,加速技巧可以使算法在運(yùn)算效率方面進(jìn)一步提高[8]．本文擬利用文獻(xiàn)[8]中給出的截?cái)嗉夹g(shù),針對(duì)Toeplitz矩陣提出了兩種加速臨近梯度截?cái)嗨惴ǎ?/p>
1 預(yù)備知識(shí)
定義11個(gè)n×n的Toeplitz矩陣定義為
定義2(奇異值分解(singular value decomposition,SVD)) 對(duì)于秩為r的矩陣X∈Rn1×n2, 則必存在正交矩陣U∈Rn1×r和V∈Rn2×r, 使得X=UFrVT, 其中Fr=diag(σ1,…,σr), 式中σ1≥σ2≥…≥σr≥0．
注文獻(xiàn)[8]中提出的APG算法是針對(duì)求解一般矩陣填充問(wèn)題的算法; 而本文要解決的填充問(wèn)題是針對(duì)Toeplitz矩陣的, 故本文提到的APG算法是在文獻(xiàn)[8]的APG算法步3中將矩陣X進(jìn)行Toeplitz化后再進(jìn)行迭代．
2 加速臨近梯度截?cái)嗨惴?/h2>
眾所周知, 對(duì)未運(yùn)用任何加速技巧的APG算法, 迭代矩陣Xk的奇異值通常會(huì)分離成2個(gè)簇, 且第一個(gè)簇的均值比第二個(gè)簇的均值要大得多, 從而可以把第一個(gè)簇類中奇異值的數(shù)量看作模型(1)低秩最優(yōu)解秩的一個(gè)估計(jì)數(shù)．此外, 第二個(gè)簇中較小的正奇異值(在μ/τ附近)可能導(dǎo)致數(shù)據(jù)M中存在噪聲, 故可將第二個(gè)簇中奇異值拋棄而不影響算法的收斂性．因此, 本文提出第一種算法(A), 步驟如圖1所示．
圖1 加速臨近梯度截?cái)嗨惴?A)流程圖Fig.1 Accelerated proximal gradient truncation algorithm(A)
算法A每次迭代過(guò)程中出現(xiàn)的截?cái)喽紩?huì)消耗時(shí)間, 故為了減少計(jì)算量, 提高算法的運(yùn)算效率, 提出了改進(jìn)的算法(B)．算法B的流程如圖2所示．
圖2 w步加速臨近梯度截?cái)嗨惴?B)流程圖Fig.2 w-Steps accelerated proximal gradient truncation algorithm(B)
3 收斂性分析
利用模型(1)的罰函數(shù)可以將Toeplitz矩陣填充問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題:
(2)
假設(shè)1假設(shè)模型(2)存在最優(yōu)解, 記為X*．
假設(shè)2對(duì)于矩陣Xk+1, 如下不等式成立:
證明 根據(jù)文獻(xiàn)[8]中引理2.1, 有F(Xk+1)≤Q(PL(Yk+1),Yk+1)≤Q(Xk+1,Yk+1), 從而
F(X)-F(Xk+1)≥F(X)-Q(Xk+1,Yk+1)．
(3)
又因f,g是凸的, 則f(Xk)≥f(Yk+1)+〈Xk-Yk+1,f(Yk+1)〉,g(Xk)≥g(Xk+1)+〈Xk-Xk+1,μ?‖Xk+1‖*〉．將上述不等式相加, 得F(Xk)≥f(Yk+1)+〈Xk-Yk+1,f(Yk+1)〉+μ‖Xk+1‖*+〈Xk-Xk+1,μ?‖Xk+1‖*〉, 代入式(3), 由假設(shè)2得F(X)-F(Xk+1)≥F(X)-Q(Xk+1,Yk+1)≥〈Xk-Yk+1,f(Yk+1)〉+〈Xk-Xk+1,μ?‖Xk+1‖*〉-〈Xk+1-Yk+1,f(Yk+1)〉-證畢．
證明 由引理1得
(4)
(5)
引理3[12]令{ak,bk}為正實(shí)數(shù)序列, 滿足ak-ak+1≥bk+1-bk, 并且對(duì)任意的k≥1, 有a1+b1≤c,c>0．那么, 對(duì)于任意的k≥1都有ak≤c．
引理4[12]正序列{tk}由算法A或B產(chǎn)生, 對(duì)于t1=1, 滿足任意的k≥1時(shí), 有tk≥(k+1)/2．
4 數(shù)值實(shí)驗(yàn)
通過(guò)數(shù)值實(shí)驗(yàn)比較本文算法與APG算法．計(jì)算機(jī)的CPU為Intel Core i3-4030U, 內(nèi)存4 GB, 操作系統(tǒng)為Windows 8, 所有代碼由MATLAB編寫(xiě)．實(shí)驗(yàn)中, Toeplitz矩陣的維數(shù)n分別取100,200,300,400,500,1 000,2 000,3 000; 采樣率p分別取 0.3,0.4,0.5;Y表示最優(yōu)解;m表示迭代次數(shù); 運(yùn)行時(shí)間t,s;r(X)=5; 參數(shù)Lf=1,ε=10-4．不同算法的數(shù)值實(shí)驗(yàn)結(jié)果對(duì)比見(jiàn)表1．從表1可以看出, 本文提出的2種新算法的迭代次數(shù)均比APG算法少, 運(yùn)行時(shí)間也較短, 且新算法的精度比APG算法更優(yōu)．
表1 不同算法的數(shù)值實(shí)驗(yàn)結(jié)果對(duì)比
猜你喜歡
百科探秘·航空航天(2022年6期)2022-06-28
智富時(shí)代(2019年4期)2019-06-01
智富時(shí)代(2019年4期)2019-06-01
福建基礎(chǔ)教育研究(2019年3期)2019-05-28
西部資源(2018年1期)2018-11-01
發(fā)明與創(chuàng)新·中學(xué)生(2017年5期)2017-05-12
高中生學(xué)習(xí)·高二版(2014年1期)2014-02-14
中學(xué)生數(shù)理化·高考版(2008年2期)2008-11-01
