欠定线性方程组稀疏解的算法求解

摘 要：研究针对欠定线性方程组稀疏解的算法进行研究，通过分析既往文献中的求解算法进行分析，认为可以从不同角度对稀疏解求解算法进行改进。通过对稀疏解算法的改进，得到比较相似的两种算法，并对两种算法进行了分析，通过实验对比发现，不同算法可能在恢复稀疏解成功率上有所不同，但收敛速度基本一致，这说明两种算法均快速有效。

关键词：欠定线性方程组；函数算法；迭代重加权变化；稀疏解算法

稀疏解研究在很多领域具有广泛应用，比如图像消旋、密码系统、纠错码及实域解码等领域。在最近几年，稀疏解计算已经引起大量学者的兴趣，并且投入到稀疏解的研究中。因稀疏解对压缩感知研究能够起到重要的促进作用，成为可采用少量预先测量值确定信号的方式，在数学计算领域价值突出。

一、 欠定线性方程算法

在以往的文献研究中，有学者给出一个嵌入方法，形成与通常线性方程相类似的线性函数，除了恰定情形，还包含超定线性方程和欠定线性方程，本文针对的是欠定线性方程的稀疏解算法研究。这里使令φ是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.

作者简介：李明伟，云南省昆明市，云南开放大学。