一种快速求解L1/2正则化问题的新算法

摘要

2008年，徐宗本提出了在Lq(0＜q≤1)正则化中具有代表性的L1/2正则化方法。文献[18，20，30]中指出，L1/2正则化能产生比L1正则化更稀疏的解，因此，它为求解稀疏问题提供了一种潜在的有力的新工具。但是，由于L1/2正则化问题是一类非凸、非光滑、非Lipschitz连续的优化问题，求解十分地困难。2012年，徐宗本提出了一种快速求解L1/2正则化问题的算法——半阈值迭代算法，该方法与求解L0正则化问题的硬阈值迭代算法、求解L1正则化问题的软阈值迭代算法相类似。
　　Amir Beck改进了软阈值迭代算法，提出了一种快速软阈值算法，该算法主要思想是应用加速近似梯度法(Accelerate Proximal Gradient Method，APG)和软阈值算子求解L1正则化问题。本文基于APG和半阈值算子的理论提出了一种新的求解L1/2正则化问题的算法，并且用该算法求解压缩感知和图像去噪等问题。所做的实验表明:(1)本文提出的算法比半阈值算法更快速、更高效，可做为求解L1/2正则化问题的又一求解器;(2)本文提出的算法简便实用，适合求解大规模问题;(3)当样本数较大时，我们的算法对较大的预估稀疏度问题具有鲁棒性;(4)本文提出的算法验证了L1/2正则化问题的解比L1正则化问题的解更稀疏。