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

求解L0最小化问题的几种方法一、引言在几次课程实验中，以数独问题为例介绍了L0问题的建模和将其松弛为L1问题的方法。实际上，L0问题在图像重建、稀疏信号恢复、特征提取、压缩感知等诸多领域应用广泛，学界对该问题的求解也进行了深入的研究。由于L0问题是典型的组合优化问题，是非凸的，直接对其求解计算量太大。因此现有研究集中在对L0问题进行转化，将其松弛后进行求解。典型的松弛方法是将其转化为L1问题1。文献2以空间建模的方式说明L1问题是对L0问题最好的凸近似。前几次课程实验中，也均通过求解L1问题来获得L0问题的解，从而实现数独求解。然而，使用L1问题来近似L0问题的求解仍存在一些问题：一个是L1问题与L0问题的等价性，即某些情况下L0问题近似为L1问题时二者最优解不相同；另一个存在于工程应用中，即在噪声环境下做信号恢复时，L1问题对噪声比较敏感。特别针对数独问题，由于可以确定稀疏水平为81，这一先验条件也没能应用于优化求解中。本文介绍了几种求解L0范数最小化问题的方法，在不同程度上能够避免或改善上述问题。下面分别予以描述。二、L0问题概述及其L1近似考虑系统特征为的矩阵，系统方程为，其中为输出信号，为输入信号。L0问题即输入信号的0范数最小化，是一种重要的信号重建的方法。如下所示：然而，直接对该问题进行求解时NP难的。最典型的求解方法是考虑使用如下的L1问题进行近似：L1问题是非凸的且存在一系列的线性优化方法进行求解。文献2说明，L1问题是对L0问题最好的凸近似。因此，L1近似成为常用的L0问题求解方法。然而，L1问题与L0的等价性要求一定的条件，典型的条件包括零空间性质（Null Space Property, NSP）和受限正交条件（Restricted Isometry Principle, RIP）等3。在不满足上述条件时，求解得到的L1问题最优解不再满足0范数最小化，二者不等价。因此L1近似在求解此类情况时无法求解成功。此外，在存在噪声的情况下进行信号重建时，L1近似对方法对噪声较为敏感，求解失败的概率较大。特别针对数独问题，由于可以确定稀疏水平为81，当使用L1近似时，这一先验条件也没能应用于优化求解中。因此，近年来又涌现出一大批不同的L0问题求解方法，他们有的是对L1近似的改进，有的是使用一种易于求解的函数去模拟L0问题，有的则根据L0问题的空间特征进行求解。下面分别予以介绍。三、加权L1近似L1问题与L0问题的主要区别在于目标函数不同，分别为输入分量的L1范数和L0范数，如下所示：可以看出，二者的主要区别在于各个分量的尺度不同，L0范数将尺度统一变为1后加起来，而L1范数则保留原来的尺度不变相加，这样导致了二者目标函数的差距。直观上看，最好的改进方法应该是将L1范数中大的分量变小，即使用加权的方法将L1范数中各个分量平均化，转化为如下所示：可以看出，使用与分量大小成反比例的权值，转化为分量幅度均匀的向量的L1范数，即可使L1范数与L0范数最大的近似。理想的权值设置为：参考加权L0范数：可以看出，由于，则相比，与更为近似。下面以图解的方式来描述加权L1法的优点。考虑一个三维的输入信号，系统特征为，考虑从输出恢复。如下图所示，黑线围成的三维块内表示L1范数小于等于1的“球”范围，红线表示约束，位于二者交点处，为一个解。从图1(b)可以看出，如果红线与“球”范围相交，其相交线上的解均为可行解，此时L1范数最小值点取在，该值成为L1问题的解，却不是对应L0问题的解。在图1(c)中可知，取权值矩阵为，加权L1问题由于使L1范数“球”范围得到调整，使得其与约束条件不再相交，从而得到正确的解。图1 L1最小化问题空间示意图可以看出，具有一定的可行取值范围，只要在这一范围内，均可保证加权L1问题解的唯一性。当然，仍需满足与输入分量大小成反比的规律。下面给出一种迭代更新的方法来获得可行的值。算法步骤如下所示：1、设迭代次数为0，初始权值为；2、求解加权L1最小化问题：；3、根据上一步求得的最优解更新权值：；4、若收敛或达到最大迭代次数，停止；否则将加1后跳至步骤2继续执行。的添加是为了加入扰动保障得到最优的解。的经验值一般以略小于最优解的最小幅度为佳。以上迭代方法可以随着迭代的进行将大幅度分量找出来并通过加权将其幅度缩小，以便后续将小的非零分量也找出来，从而提高信号恢复的准确度。四、平滑近似法平滑近似法5,6的主要思想是使用一个平滑函数来近似L0范数，从而可以使用梯度方法进行求解，并且该方法对噪声不敏感。下面对平滑近似法进行简要介绍。定义函数，则的L0范数可写作：显然L0范数的不连续性主要来源于函数的不连续性，因此只要找到对的平滑近似，即可得到对L0范数的平滑近似。考虑如下函数：我们得到：因此，定义，则有所以L0范数最小化问题可以转化为的最大化问题。其中取值越小，近似效果越好；取值越大，平滑程度越高。在取值非常小的情况下，L0范数最小化问题转化为：然而，较小时，有很多局部极大值，因此很难直接求解得到最大值。而随着变大，变得越来越平滑，当足够大时，不再有局部极值。因此，对最大化问题的求解思路为：首先在足够大的时使用最速下降法获得最优解，然后逐渐减小并在上一步最优解的附近获取极值解作为最优解。由于值变化较慢，最速下降法的初始值始终在最大值附近，因此该问题陷入局部极值点的可能性比较小。一种具体的求解步骤如下所示：1、初始化：选择的最小均方解作为的初始值，并为选择一个递减序列，其中为迭代次数。2、对循环：令，在可行集上使用最速下降法求解的最大化问题并迭代次：对循环： 令； 令，其中为较小的正常数； 将投影到可行集上：。3、令。迭代完成后，取作为最优解。该方法由于使用了另外一种对L0范数的近似方法，因此避免了L1近似法中由于等价条件不满足导致的求解错误的问题。此外，平滑近似也提高了对噪声的鲁棒性。五、正交匹配追踪法正交匹配追踪法（Orthogonal Matching Pursuit, OMP）是一种贪婪迭代算法。在该方法中，将系统特征矩阵的各个列看作各个测量向量，则输出信号为输入信号中非零分量对应的各个测量向量的线性组合，即只有这些测量向量对的形成做了贡献。OMP的思想是使用贪婪算法将这些测量分量找出来。每个迭代周期，将对的剩余部分贡献最大的列找出来，然后从该剩余部分中减去它贡献的部分并在剩余部分中继续迭代。考虑输入信号的稀疏水平（非零分量的个数）为，则算法希望经过次循环后将正确的列辨识出来。下面详细描述OMP算法的步骤。1、初始化：剩余部分，非零分量索引集合，已选定列向量集合，迭代索引为。2、找出对贡献最大的列向量的索引，即求解如下优化问题：其中为矩阵的第列。3、更新非零分量索引集合及已选定列向量集合。4、根据已选定向量集合求解一个输入信号的最小均方估计，即求解如下优化问题：5、求解已找出的列向量贡献的分量，得到；求解剩余分量，得到。6、将加1， 若，返回步骤2。最终得到的各个值即为输入信号中非零分量的索引，输入信号第个分量的值即为第个分量的值。从步骤3、4、5可知，剩余分量总是与已选定列向量集合正交，因此，每次迭代均能选出新的非零分量，从而实现算法的意图。从文献7的分析可以看出，OMP算法的时间复杂度要小于基于线性优化的L1近似法，然而，相比于L1近似法，OMP算法缺少可证明的求解性能，无法获取理论上的正确率。后续的改进包括分段式OMP算法、正规化OMP算法等，六、总结本文分析了使用线性优化方法求解L1近似的L0最优化时存在的问题，并介绍了加权L1近似法、平滑近似法和匹配追踪法三种不同思想的L0优化问题解法，这三种方法相比线性求解的L1近似法各有优点，可应用于不同的场景，也为L0优化问题的求解打开了思路，有助于对L0优化问题各个性质的进一步研究。参考文献1 S. S. Chen, D. L. Donoho, and M. A. Saunders. “Atomic Decomposition by Basis Pursuit,” SIAM Journal on Scientific Computing, vol. 20, pp. 3361, 1998.2 Ramirez, Carlos, Vladik Kreinovich, and Miguel Argaez. Why l1 is a Good Approximation to l0: A Geometric Explanation. Journal of Uncertain Systems, 2013: 203-207.3 Hui Zhang, Wotao Yin, Lizhi Cheng. Necessary and sufficient conditions of solution uniqueness in l1 minimization. Journal of optimization theory and applications, 2015, 164(1): 109-122.4 Candes, Emmanuel J., Michael B. Wakin, and Stephen P. Boyd. Enhancing sparsity by reweighted 1 minimization. Journal of Fourier analysis and applications 14.5-6 (2008): 877-905.5 G. H. Mohimani, M. Babaie-Zadeh, and C. Jutten, “Fast sparse representation based on smoothed l0 norm,” in 7th International Conference on Independent Component Analysis and Signal Separation, 2007, pp. 389396.6 Hyder, Mashud, and Kaushik Mahata. An approximate L0 norm minimization algorithm for compressed sensing. Acoustics, Speech and Signal Processing, 2009. ICAS