1. 引言
本文考虑如下两个稀疏信号的恢复问题
(1)
其中
,
为稀疏信号,
为测量向量且
,
,
,
为观测矩阵。该问题在信号处理、医学成像以及雷达系统等跨学科领域中都有着广泛的应用。近年来得到了高度的关注及深入的研究,其中文献 [1] [2] 讨论了其在图像纹理分离方面的应用。文献 [3] [4] 给出了其在图像,音频,视频的超分辨率和修复问题上的应用。本文对稀疏信号恢复问题的ADMM算法及其应用进行了研究。
文献 [5] 提出了ADMM算法及BCD算法对该问题进行对比研究并取得了较好的结果。受该文启发,本文提出该问题的加权
范数极小化约束模型,通过对模型的等价转化,ADMM算法的推广进行求解。在适当的假设下证明了算法的全局收敛性。在数值实验中对两类3D彩色图像进行了重建测试,其中一类含有30%的盐噪声,另一类含有30%的椒盐噪声。实验过程中将ADMM算法与JP算法及YALL1算法的恢复效果进行了数值对比。实验结果表明无论从峰值信噪比PSNR还是从相对误差RelErr角度考察,我们方法的数值结果都明显得到了改善,因而该方法具有较好的图像恢复效果。
2. 模型的转化
本节给出求解问题(1)的如下加权
范数极小化模型:
(2)
其中
为加权因子。
显然,对充分小的
,(2)可近似为
(3)
因此,
充分小时,(3)的解趋于(2)的解。该约束优化问题可以转化为下述无约束形式
(4)
这里
是一个惩罚因子,问题(3)中的较小的
相当于问题(4)中较小的
。随着
,(4)的解满足
,且问题(4)近似于问题(2)。因此,取一个充分小的
可使得
3. 算法及收敛性证明
3.1. ADMM算法
ADMM是一个非常适合解决高维优化问题的算法,可以较容易地处理全局问题。因此本文应用ADMM算法求解(4)。通过引入辅助变量
,(4)等价于
其增广拉格朗日函数为
这里的
和
是对偶变量,
和
是正惩罚因子。ADMM算法迭代格式如下:
(5)
(6)
(7)
(8)
(9)
(10)
3.2. 加权l1范数的临近算子
为求解(5)和(6),我们引入加权
范数的临近算子。
定义1 [5] 对
,其
范数(
)函数的临近算子定义为
其中
为惩罚因子。当
时,其解的表达形式为
下面对
定义本文的加权
范数函数的临近算子
其中
。可将其化简为
(11)
当
时,(11)等价为
因此
。当
时,结合
可得
。综上可表述为
(12)
同理当
时,(11)等价为
因此
。当
时,结合
可得
。综上可表述为
(13)
结合(12)与(13)可得,加权
范数函数的临近算子解的表达形式为
3.3. 收敛性证明
此处我们讨论ADMM算法的收敛性。
为叙述方便,定义如下符号:
,
,
。设
是本文算法产生的序列,
。令
,
,
,从而
。
引理 1 设序列
由(5)~(10)产生,如果下式成立
(14)
则
其中参数
,
,且
证明 此引理的证明与文献 [5] 的引理1的证明相似,故略。
引理2 设序列
由(5~(10)产生,如果(14)满足,那么
,故
的任何聚点都是
的一个驻点。
证明 由(7)得出的最小值
满足
将(9)代入其中有
(15)
从而结合
,
有
(16)
类似地,结合(8)及(10)可得
(17)
(18)
因为
下半连续,故下有界。由引理1可知当满足(14)时,
非增,因此收敛。对于
,由
的定义及(16)和(18)有
因此
这里的
。令
,
,且
,
,故(14)可以转化为
,
,且
。由文献 [5] 的引理2证明过程可知,当
同时满足上述两个不等式时,
的最大值小于1,即
。因此当(14)成立时,有
。从而序列
有界。故对于有界序列
,必存在一个收敛子列
收敛到聚点
,又
在
时非增收敛,
那么对任意
都有
,从而结合引理1可得
综上
令
,当
时有
(19)
由(15)有
(20)
同理由(17)可得
(21)
再结合(20)有
(22)
再据(19)和(22)可得
,
。因此
。故可知由(5)~(10)
产生的序列
的任何聚点都是
的一个驻点,且由最优性条件可知其满足
(23)
取
的一个收敛子列
。因
,从而
和
有相同的极限点
。由于
收敛,故
,
收敛。对(23)两侧求极限可得
故
是
的一个驻点。
引理3 函数
如前定义,若(14)成立,则存在常数
,使得
证明 由
的定义可得
结合(23)有
。类似可得:
因此,存在常数
使得
再由引理2的证明可得结论。
注:这个结论为迭代间隙提供了一个次梯度下界,同时结合引理2可得出当
时,
定理1 若(14)成立,则本文算法产生的点列
收敛到问题(4)的一个聚点。
证明 首先证明序列
满足
(24)
对于本文定义的加权
范数
,当
时,
。取定任意小的正数
,当
时,
。因
是KL函数,故当
充分小时,
是KL函数,从而
也为KL函数,故(24)成立。因此迭代点列
是
柯西列且收敛,结合引理2可得迭代点列
全局收敛到
的一个聚点。关于(24)的详细证明可参考文献 [6],此处略去。
4. 数值实验
本节测试两组3D彩色图像恢复实验,程序用Matlab2017a编写。为加速算法,对参数
采取如下措施:对于
,
,否则
。取
,
为逆离散余弦变换(IDCT)矩阵,因此
是图像的DCT系数。然后根据DCT系数的相对误差(ReLErr)和恢复图像的峰值信噪比(PSNR)来评估算法的效果,并与JP [7],YALL1 [8] 算法进行对比。实验一、二、三修复的是三张含有30%盐噪声的图像。实验四、五、六重建的是三张含有30%椒盐噪声的图像,其中含有25%盐噪声和5%胡椒噪声。
实验一
Figure 1. Comparisons of ADMM algorithm, the JP and the YALL1 (30% of the pixels are corrupted by salt noise)
图1. ADMM算法与JP和YALL1算法的对比结果(30%盐噪声)
实验二
Figure 2. Comparisons of ADMM algorithm, the JP and the YALL1 (30% of the pixels are corrupted by salt noise)
图2. ADMM算法与JP和YALL1算法的对比结果(30%盐噪声)
实验三
Figure 3. Comparisons of ADMM algorithm, the JP and the YALL1 (30% of the pixels are corrupted by salt noise)
图3. ADMM算法与JP和YALL1算法的对比结果(30%盐噪声)
实验四
Figure 4. Comparisons of ADMM algorithm, the JP and the YALL1 (30% of the pixels are corrupted by salt-and-pepper noise)
图4. ADMM算法与JP和YALL1算法的对比结果(30%椒盐噪声)
实验五
Figure 5. Comparisons of ADMM algorithm, the JP and the YALL1 (30% of the pixels are corrupted by salt-and-pepper noise)
图5. ADMM算法与JP和YALL1算法的对比结果(30%椒盐噪声)
实验六
Figure 6. Comparisons of ADMM algorithm, the JP and the YALL1 (30% of the pixels are corrupted by salt-and-pepper noise)
图6. ADMM算法与JP和YALL1算法的对比结果(30%椒盐噪声)
由图1~3可以看出,当彩色图片中含30%的盐噪声时,与JP算法相比,本文的ADMM算法的峰值信噪比PSNR提高了3~7 dB;与YALL1算法相比,本文的ADMM算法的峰值信噪比PSNR提高了1~3.3 dB。相应的相对误差RelErr明显降低。由图4~6可以看出,当彩色图片中含30%的椒盐噪声时,与JP算法相比,本文的ADMM算法的峰值信噪比PSNR提高了1~2.6 dB;与YALL1算法相比,ADMM算法的峰值信噪比PSNR提高了0.3~2 dB,相对误差ReLErr的减少量也较大。由此可见,基于本文提出的加权
范数极小化模型的ADMM算法在3D彩色图像重建中具有有效性。
5. 结论
本文针对具有两个稀疏信号的恢复问题,提出了加权
范数极小化模型,通过模型的等价转化应用ADMM算法进行求解。在适当地假设下证明了算法的收敛性。在数值试验中,对具有30%盐噪声和30%椒盐噪声的3D彩色图像分别进行了恢复,并与经典的JP算法及YALL1算法进行了数值比对。实验结果表明相比于其他两个算法,ADMM算法的峰值信噪比PSNR明显提高,而相对误差RelErr明显降低,因此具有较好的图像恢复效果。