求解L0最小化问题的几种方法

求解L0最小化问题的几种方法一、引言在几次课程实验中，以数独问题为例介绍了L0问题的建模和将其松弛为L1问题的方法。实际上，L0问题在图像重建、稀疏信号恢复、特征提取、压缩感知等诸多领域应用广泛,学界对该问题的求解也进行了深入的研究。由于L0问题是典型的组合优化问题，是非凸的，直接对其求解计算量太大。因此现有研究集中在对L0问题进行转化，将其松弛后进行求解。典型的松弛方法是将其转化为L1问题⑴。文献［2］以空间建模的方式说明L1问题是对L0问题最好的凸近似。前几次课程实验中，也均通过求解 L1问题来获得L0问题的解，从而实现数独求解。然而使用L1问题来近似L0问题的求解仍存在一些问题：一个是L1问题与L0问题的等价性，即某些情况下L0问题近似为L1问题时二者最优解不相同；另一个存在于工程应用中，即在噪声环境下做信号恢复时， L1问题对噪声比较敏感。特别针对数独问题，由于可以确定稀疏水平为 81,这一先验条件也没能应用于优化求解中。本文介绍了几种求解L0范数最小化问题的方法，在不同程度上能够避免或改善上述问题。下面分别予以描述。、L0问题概述及其L1近似考虑系统特征为NM的矩阵A，系统方程为Ax=b，其中b为输出信号，x为输入信号。L0问题即输入信号的0范数最小化，是一种重要的信号重建的方法。如下所示：minX0s.t.Ax=b然而，直接对该问题进行求解时NP难的。最典型的求解方法是考虑使用如下的L1问题进行近似：minx1s.t.Ax=bL1问题是非凸的且存在一系列的线性优化方法进行求解。文献［2］说明，L1问题是对L0问题最好的凸近似。因此，L1近似成为常用的L0问题求解方法。然而，L1问题与L0的等价性要求一定的条件，典型的条件包括零空间性质( NullSpaceProperty,NSP和受限正交条件(RestrictedIsometryPrinciple,RIP)等⑶。在不满足上述条件时，求解得到的 L1问题最优解不再满足0范数最小化，二者不等价。因此L1近似在求解此类情况时无法求解成功。此外，在存在噪声的情况下进行信号重建时， L1近似对方法对噪声较为敏感，求

81,当使用81,当使用L1近似因此近年来又涌现出一大批不同的L0问题求解方法，他们有的是对L1近似的改进,有的是使用一种易于求解的函数去模拟L0问题，有的则根据L0问题的空间特征进行求解。下面分别予以介绍。三、加权L1近似L1问题与L0问题的主要区别在于目标函数不同， 分别为输入分量的L1范数和L0范数，如下所示：=0-0|x||Tc,G=J0，Xi11y X.，X=0可以看出，二者的主要区别在于x各个分量的尺度不同，L0范数将尺度统一变为1后加起来，而L1范数则保留原来的尺度不变相加，这样导致了二者目标函数的差距。直观上看，最好的改进方法应该是将 L1范数中大的分量变小，即使用加权的方法将 L1范数中各个分量平均化，转化为如下所示：可以看出，使用与分量大小成反比例的权值，转化为分量幅度均匀的向量的 L1范数，即可使L1范数与L0范数最大的近似。理想的权值设置为:1,*丸wi::,*=0参考加权L0范数:WXI。，XWXI。，Xj=°〔J"1,X"可以看出，由于Wx0=x0,则相比x1Wx1与x0更为近似F面以图解的方式来描述加权 L1法的优点"2111考虑一个三维的输入信号x0=[010]t,系统特征为&=J ，考虑从输出112y=©x°二[11]t恢复*0。如下图所示，黑线围成的三维块内表示L1范数小于等于1的“球”范围，红线表示y=&x约束，x0位于二者交点处，为一个解。从图 1(b)可以看

出，如果红线与“球”范围相交，其相交线上的解均为可行解，此时取在L1范数最小值点X*二[1/301/3]t，该值成为L1问题的解，却不是对应L0问题的解。在图1(c)中可知，取权值矩阵为W二diag[313]t，加权L1问题由于W使L1范数“球”范围得到调整，使得其与约束条件不再相交，从而得到正确的解。(a) (b) (c)图1L1最小化问题空间示意图可以看出，W具有一定的可行取值范围，只要在这一范围内，均可保证加权 L1问题解的唯一性。当然，W仍需满足与输入分量大小成反比的规律。下面给出一种迭代更新的方法来获得可行的W值。算法步骤如下所示：1、设迭代次数m为0,初始权值为w0=1,i=1川，n；3、根据上一步求得的最优解更新权值: Wm12、求解Wm加权L1最小化问题：Xm=argmin||wmx|3、根据上一步求得的最优解更新权值: Wm1琴|+&4、若收敛或达到最大迭代次数，停止；否则将m加1后跳至步骤2继续执行。；的添加是为了加入扰动保障得到最优的解。 ；的经验值一般以略小于最优解的最小幅度为佳。以上迭代方法可以随着迭代的进行将大幅度分量找出来并通过加权将其幅度缩小，以便后续将小的非零分量也找出来，从而提高信号恢复的准确度。四、平滑近似法平滑近似法[5,6]的主要思想是使用一个平滑函数来近似 L0范数，从而可以使用梯度方法进行求解，并且该方法对噪声不敏感。下面对平滑近似法进行简要介绍。0x=0定义函数'(X) ，则X的L0范数可写作：l1,xH0nX，\"xji—显然L0范数的不连续性主要来源于函数 (x)的不连续性，因此只要找到对..(x)的平滑近似，即可得到对L0范数的平滑近似。考虑如下函数：f;：(x)=exp—x2.2匚2我们得到：因此也f』x)=1—v(x)，定义Fy(X)=Lf/N)，则有所以L0范数最小化问题可以转化为 x)的最大化问题。其中二取值越小，近似效果越好；匚取值越大，平滑程度越高。在二取值非常小的情况下，L0范数最小化问题转化为：maxF;_(x)s.tAx=b然而，匚较小时，F--(x)有很多局部极大值，因此很难直接求解得到最大值。而随着二变大，F；：・(x)变得越来越平滑，当二足够大时，F-(x)不再有局部极值。因此，对limF_(x)最大化问题的求解思路为：首先在足够大的 -时使用最速下降法获得最优解，—0然后逐渐减小匚并在上一步最优解的附近获取极值解作为最优解。由于 ；「值变化较慢,最速下降法的初始值始终在最大值附近，因此该问题陷入局部极值点的可能性比较小。一种具体的求解步骤如下所示：1、 初始化：选择Ax=b的最小均方解七作为x的初始值，并为二选择一个递减序列［6,6,川，匚」，其中K为迭代次数。2、 对k=1,2,|l|,K循环：令，x〃心在可行集？：：x|Ax=b｝上使用最速下降法求解R-(x)的最大化问题并迭代J次：对j=1,2J||,J循环:

令x=令x=%exp—x;2「2山，xexp2匚k;令x：_X-'「X,其中二为较小的正常数;将x投影到可行集？上：x「x_AtAAt一Ax_b。3、令Vk=x。迭代完成后，取VK作为最优解。该方法由于使用了另外一种对L0范数的近似方法，因此避免了L1近似法中由于等价条件不满足导致的求解错误的问题。此外，平滑近似也提高了对噪声的鲁棒性。五、正交匹配追踪法正交匹配追踪法(OrthogonalMatchingPursuit,OMP)是一种贪婪迭代算法。在该方法中，将系统特征矩阵A的各个列看作各个测量向量，则输出信号 b为输入信号中非零分量对应的各个测量向量的线性组合，即只有这些测量向量对 b的形成做了贡献。OMP的思想是使用贪婪算法将这些测量分量找出来。 每个迭代周期，将对b的剩余部分贡献最大的列找出来，然后从该剩余部分中减去它贡献的部分并在剩余部分中继续迭代。考虑输入信号的稀疏水平(非零分量的个数)为d，则算法希望经过d次循环后将正确的列辨识出来。下面详细描述OMP算法的步骤。1、初始化：剩余部分『°二b，非零分量索引集合上。工必，已选定列向量集合Qe,迭代索引为t=1。2、找出对rtA贡献最大的列向量的索引三，即求解如下优化问题:Nargmax(—训j出ll,M-其中商为矩阵A的第j列。3、更新非零分量索引集合上t=-'町t't』及已选定列向量集合Q二札。4、根据已选定向量集合求解一个输入信号的最小均方估计， 即求解如下优化问题：舄二argmin|Qtx「b25、 求解已找出的列向量贡献的分量，得到at二Qtxt；求解剩余分量，得到rt二b-at6、 将t加1,若t::4,返回步骤2。最终得到上m的各个值即为输入信号中非零分量的索引，输入信号第 k个分量的值

即为Xm第k个分量的值Qt正交，因此，每次迭从步骤3、4、5可知，剩余分量rQt正交，因此，每次迭代均能选出新的非零分量，从而实现算法的意图。从文献［7］的分析可以看出，OMP算法的时间复杂度要小于基于线性优化的L1近似法，然而，相比于L1近似法，OMP算法缺少可证明的求解性能，无法获取理论上的正确率。后续的改进包括分段式OMP算法、正规化OMP算法等，六、总结六、总结本文分析了使用线性优化方法求解L1近似的L0最优化时存在的问题，并介绍了加权L1近似法、平滑近似法和匹配追踪法三种不同思想的L0优化问题解法，这三种方法相比线性求解的L1近似法各有优点，可应用于不同的场景，也为L0优化问题的求解打开了思路，有助于对L0优化问题各个性质的进一步研究。参考文献S.S.Chen,D.L.Donoho,andM.A.Saunders.“AtomicDecompositionbyBasisPursuit,SIAMJournalonScientificComputing,vol.20,pp.33-61,1998.Ramirez,Carlos,VladikKreinovich,andMiguelArgaez."Whyl1isaGoodApproximationtol0:AGeometricExplanation."JournalofUncertainSystems,2013:203-207.HuiZhang,WotaoYin,LizhiCheng."Necessaryandsufficientconditionsofsolutionuniquenessinl1minimization."Journalofoptimizationtheoryandapplications,2015,164(1):109-122.Candes,EmmanuelJ.,MichaelB.Wakin,andStephenP.Boyd."Enhancingsparsitybyreweighted?1minimization."JournalofFourieranalysisandapplications14.5-6(2008):877-905.G.H.Mohimani,M.Babaie-Zadeh,andC.Jutten,“Fastsparserepresentationbasedonsmoothedl0norm,”7thinInternationalConferenceonIndependentComponentAnalysisandSignalSeparation,2007,pp.389-396.Hyder,Mashud,andKaushikMahata."AnapproximateL0normminimizationalgorithmforcompressedsensing."Acoustics,Spee