欠定線性方程組稀疏解的算法求解

摘 要：研究針對(duì)欠定線性方程組稀疏解的算法進(jìn)行研究，通過分析既往文獻(xiàn)中的求解算法進(jìn)行分析，認(rèn)為可以從不同角度對(duì)稀疏解求解算法進(jìn)行改進(jìn)。通過對(duì)稀疏解算法的改進(jìn)，得到比較相似的兩種算法，并對(duì)兩種算法進(jìn)行了分析，通過實(shí)驗(yàn)對(duì)比發(fā)現(xiàn)，不同算法可能在恢復(fù)稀疏解成功率上有所不同，但收斂速度基本一致，這說明兩種算法均快速有效。

關(guān)鍵詞：欠定線性方程組；函數(shù)算法；迭代重加權(quán)變化；稀疏解算法

稀疏解研究在很多領(lǐng)域具有廣泛應(yīng)用，比如圖像消旋、密碼系統(tǒng)、糾錯(cuò)碼及實(shí)域解碼等領(lǐng)域。在最近幾年，稀疏解計(jì)算已經(jīng)引起大量學(xué)者的興趣，并且投入到稀疏解的研究中。因稀疏解對(duì)壓縮感知研究能夠起到重要的促進(jìn)作用，成為可采用少量預(yù)先測(cè)量值確定信號(hào)的方式，在數(shù)學(xué)計(jì)算領(lǐng)域價(jià)值突出。

一、 欠定線性方程算法

在以往的文獻(xiàn)研究中，有學(xué)者給出一個(gè)嵌入方法，形成與通常線性方程相類似的線性函數(shù)，除了恰定情形，還包含超定線性方程和欠定線性方程，本文針對(duì)的是欠定線性方程的稀疏解算法研究。這里使令φ是m×N（m

在以往的文獻(xiàn)中，求解l0的最小范數(shù)屬于NP問題，其對(duì)噪音具有較高敏感性，導(dǎo)致了在求解上一公式時(shí)帶來了巨大難度。但即便如此，仍然有研究學(xué)者通過研究得出以l0范數(shù)直接來求解計(jì)算的方式，并且指出在這個(gè)難題中的關(guān)鍵問題是因l0范數(shù)并不是連續(xù)函數(shù)所致。因此，筆者認(rèn)為，可通過采取可微的期望值等于0的高斯函數(shù)類來替換不連續(xù)的函數(shù)||x||0，讓兩者近似相等，在采用最速下降法通過精確求解對(duì)應(yīng)的非線性系統(tǒng)去證明算法的收斂性。對(duì)于上述問題，很多研究學(xué)者已經(jīng)在研究中取得了許多成果，其中基追蹤算法（Basis Pursuit， BP）就是其中一種，該方式比較成功，主要將問題轉(zhuǎn)化成l1范數(shù)求解最小化問題，可得：

通過對(duì)min{||x||1x∈RN，φx=Y}精確的恢復(fù)信號(hào)，并且該問題可通過線性規(guī)劃（LP）方法求解，所以前一個(gè)問題可通過快速LP算法，特別是內(nèi)點(diǎn)LP方法去計(jì)算，從而對(duì)規(guī)模較大的問題也能夠通過計(jì)算求解來獲得。但由于該方法收斂慢，所以有研究學(xué)者在此基礎(chǔ)上進(jìn)行算法改進(jìn)，通過一定方式改善收斂速度，更好的處理有噪音的干擾。另外一種求解的成功方式就是采用迭代重加權(quán)最小化范數(shù)解，此方法比BP更快。

二、 改進(jìn)算法研究

基于上述稀疏解算法，對(duì)于相關(guān)研究中的算法進(jìn)行一種改進(jìn)，采用ε1+q代替算法中的ε2，并且在q接近0值時(shí)，采用改進(jìn)后算法可增強(qiáng)信號(hào)稀疏恢復(fù)的能力。而以上算法是基于l0范數(shù)得來的，但這種算法可以看作是文獻(xiàn)[11]中算法在q=0時(shí)算法的一種延伸，這種方法具有比上一算法更強(qiáng)的恢復(fù)稀疏信號(hào)能力。本文對(duì)改進(jìn)的欠定線性方程稀疏解算法進(jìn)行研究，具體如下：

當(dāng)εn=0時(shí)，應(yīng)結(jié)束算法，獲得其稀疏解。

三、 實(shí)驗(yàn)印證分析

針對(duì)算法右端項(xiàng)y，可取不同x*及q。通過主要算法C，針對(duì)不同q值的條件下將算法C與算法B在解的恢復(fù)能力上進(jìn)行對(duì)比，實(shí)驗(yàn)過程如下：

選取滿足N（0，1/m）的高斯獨(dú)立分布的m×N矩陣φ進(jìn)行k-稀疏向量x*，結(jié)合文獻(xiàn)中證明的矩陣可大概率滿足優(yōu)化邊界的BIP性質(zhì)，在已知的算法B、算法C中取不同權(quán)w，從量算法格式上發(fā)現(xiàn)q值逐漸降低，趨近于0，這一過程算法格式差距越來越明顯。兩種算法終止條件均為εn，如果其<10-8，則當(dāng)q=0.8時(shí)，算法C在恢復(fù)稀疏解時(shí)效果比算法B更好，而當(dāng)q=0.2時(shí)，則算法那C恢復(fù)稀疏解成功率遠(yuǎn)遠(yuǎn)高于算法B。但從兩種算法的收斂速度上看，兩種算法差別不大，研究證實(shí)其迭代步數(shù)基本一致。詳情見圖1、圖2。

四、 結(jié)論

欠定線性方程組的稀疏解算法有很多，但不同的算法在很大程度上具有相似性，可能在權(quán)值及其他方面存在一定的差異，但均能獲得最終的稀疏解。本文通過對(duì)方程的稀疏解算法進(jìn)行改進(jìn)，從而形成算法B和算法C，兩種算法同樣能夠得出恢復(fù)稀疏解，雖然恢復(fù)稀疏解成功率存在差異，但收斂速度上相差無幾。

參考文獻(xiàn)：

[1] Lai M J. On sparse solutions of underdetermined linear systems[J]. J Concrete and Applicable Mathematics， 2010（8）：296-327.

[2] 崔安剛，李海洋，任璐.帶有噪音的稀疏解的穩(wěn)定性分析的注[N].山東大學(xué)學(xué)報(bào)（工學(xué)版），2015，45（4）：91-94.

[3] 廖蕓，劉曉紅，李文娟.求解絕對(duì)值方程組稀疏解的兩種算法[N].天津理工大學(xué)學(xué)報(bào)，2015（5）：57-60.

[4] Saab R， Yilmaz OS_parse recovery by non-convex optimization-instance optimality[J].Appl Comput Harmon Anal， 2010（29）：30-48.

[5] 孔繁鏘，郭文駿，沈秋等.復(fù)合正則化聯(lián)合稀疏貝葉斯學(xué)習(xí)的高光譜稀疏解混算法[N].紅外與毫米波學(xué)報(bào)，2016，35（2）：219-226.

[6] 趙春暉，肖健鈺，齊濱.一種改進(jìn)的OMP高光譜稀疏解混算法[N].沈陽大學(xué)學(xué)報(bào)（自然科學(xué)版），2015，27（3）：206-213.

[7] Rudelson M，Vershynin R. On sparse reconstruction from Fourier and Gaussian measurements[J]. Comm Pure Appl Math，2008（61）：1025-1045.

[8] 焦力賓.解稀疏插值問題的代數(shù)幾何方法[D].大連理工大學(xué)，2016.

[9] 薛會(huì)祥，趙擁軍，郭磊.基于交替下降求解的稀疏信號(hào)重建算法[N].信息工程大學(xué)學(xué)報(bào)，2012，13（2）：211-217.

[10] 謝志鵬.迭代式正交匹配追蹤及稀疏解[J].微電子學(xué)與計(jì)算機(jī)，2009，26（10）：53-56.

[11] Daubechies I， DeVore R， Fornasier M， Gunturk C S.Iteratively reweighted least squares minimization for sparse recovery[J]. Commun on Pure and Appl Math， 2010，63：1-38.

[12] 武昕，韓笑.基于信號(hào)稀疏化欠定求解的居民用戶非侵入式負(fù)荷分解算法[J].電網(wǎng)技術(shù)，2017，41（9）：3033-3040.

[13] 王汗三，陳杰.稀疏重構(gòu)算法[J].電子科技，2013，26（5）：106-108.

[14] Donoho D L，Tanner J.Counting faces of randomlyprojected polytopes when the projection radically lowers dimension[J].J Amer Math Soc， 2009，22：1-53.

作者簡介：李明偉，云南省昆明市，云南開放大學(xué)。