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

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

關鍵詞：欠定線性方程組；函數算法；迭代重加權變化；稀疏解算法

稀疏解研究在很多領域具有廣泛應用，比如圖像消旋、密碼系統、糾錯碼及實域解碼等領域。在最近幾年，稀疏解計算已經引起大量學者的興趣，并且投入到稀疏解的研究中。因稀疏解對壓縮感知研究能夠起到重要的促進作用，成為可采用少量預先測量值確定信號的方式，在數學計算領域價值突出。

一、 欠定線性方程算法

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

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

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

二、 改進算法研究

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

當εn=0時，應結束算法，獲得其稀疏解。

三、 實驗印證分析

針對算法右端項y，可取不同x*及q。通過主要算法C，針對不同q值的條件下將算法C與算法B在解的恢復能力上進行對比，實驗過程如下：

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

四、 結論

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

參考文獻：

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

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

[3] 廖蕓，劉曉紅，李文娟.求解絕對值方程組稀疏解的兩種算法[N].天津理工大學學報，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] 孔繁鏘，郭文駿，沈秋等.復合正則化聯合稀疏貝葉斯學習的高光譜稀疏解混算法[N].紅外與毫米波學報，2016，35（2）：219-226.

[6] 趙春暉，肖健鈺，齊濱.一種改進的OMP高光譜稀疏解混算法[N].沈陽大學學報（自然科學版），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] 焦力賓.解稀疏插值問題的代數幾何方法[D].大連理工大學，2016.

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

[10] 謝志鵬.迭代式正交匹配追蹤及稀疏解[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] 武昕，韓笑.基于信號稀疏化欠定求解的居民用戶非侵入式負荷分解算法[J].電網技術，2017，41（9）：3033-3040.

[13] 王汗三，陳杰.稀疏重構算法[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.

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