一种求解Lasso问题的不精确邻近梯度算法

谢秋玲, 徐宇淼, 胡清洁

(桂林电子科技大学 数学与计算科学学院,广西 桂林 541004)

最小绝对值收缩和选择算子(least absolute shrinkage and selection operator,简称Lasso)问题由Tibshirani[1]提出,即利用l1正则化项求解线性回归问题的稀疏解。Lasso问题在稀疏规划和信号处理领域起着非常重要的作用,其应用包括稀疏信号修复、稀疏图回归、稀疏逆协方差、稀疏字典学习、图像修复、图像去噪和去模糊等[2]。因此,在理论和算法上深化和完善对该问题的研究,具有重要的理论意义和广泛的应用前景。

Lasso问题模型如下:

在利用邻近梯度法求解问题(1)时,需计算邻近算子[7]:在很多情况下,邻近子问题(2)无解析解或者精确求解的计算量较大,需考虑近似求解邻近算子。鉴于此,提出了一种带有邻近算子误差和梯度计算误差的不精确邻近梯度算法,并给出该算法的收敛速度分析和相应的数值实验。

1 不精确邻近梯度算法

与文献[5]中提出的FISTA-BKTR 算法相比,为了加速收敛,本算法在步骤5)中计算不精确邻近算子,即考虑在问题(1)中光滑项梯度计算和求解邻近子问题时存在误差。

根据算法中的步骤2),若选择的μ-k、μ0k分别满足μ0>1/L(f)、μk≥μk-1,则对∀k,有μk≥β/L(f)。若μ0>1/L(f),因此有

2 算法的有关性质

性质1[7]若

引理3 若对任意的y∈Rn,μ>0,使得

类似于文献[7],可得如下关于不精确邻近梯度算法的2个关键引理。

引理5 若假设算法中满足

3 收敛速度分析

为了得到形如

定理1 若上述假设成立,则在算法的第k次迭代中,

其中,

即

由引理6可得

其中:

从而定理得证。

4 数值实验

分别用FISTA[4](加速邻近梯度算法)、INEXACT FISTA (不精确加速邻……