ADMM算法在3D彩色图像恢复中的应用

Application of ADMM Algorithm in 3D Color Image Recovery

摘要: 本文讨论稀疏信号的恢复和分离问题。利用加权l1范数进行稀疏诱导，提出了加权l1范数极小化约束模型，利用ADMM算法进行求解。在适当地假设下证明了算法的收敛性。对带有盐噪声和椒盐噪声的3D彩色图像进行了数值实验，并与JP算法及YALL1算法进行了数值比对。实验结果的峰值信噪比PSNR和相对误差RelErr表明，我们的算法具有较好的恢复效果。

Abstract: This paper discusses the recovery and demixing problem of sparse signals. We propose a weighted l₁ norm minimization model. Then the ADMM algorithm is applied to this model. We also prove the convergence property of our algorithm under mild conditions. At last, we do two numerical experiments for 3D color image, in which salt noise and salt-and-pepper noise are chosen. In addition, we compare our algorithm with two other algorithms: the JP and the YALL1. Numerical results of PSNR and RelErr show that our algorithm gives relatively better behavior.

1. 引言

本文考虑如下两个稀疏信号的恢复问题

$y=A_1{x}_1+A_2{x}_2$ (1)

其中 $x_k\in R^{n_k}$， $k=1,2$ 为稀疏信号， $y\in R^m$ 为测量向量且 $m\ll n_1$， $m\ll n_2$， $A_k\in R^{m\times n_k}$， $k=1,2$ 为观测矩阵。该问题在信号处理、医学成像以及雷达系统等跨学科领域中都有着广泛的应用。近年来得到了高度的关注及深入的研究，其中文献 [1] [2] 讨论了其在图像纹理分离方面的应用。文献 [3] [4] 给出了其在图像，音频，视频的超分辨率和修复问题上的应用。本文对稀疏信号恢复问题的ADMM算法及其应用进行了研究。

文献 [5] 提出了ADMM算法及BCD算法对该问题进行对比研究并取得了较好的结果。受该文启发，本文提出该问题的加权 $l_1$ 范数极小化约束模型，通过对模型的等价转化，ADMM算法的推广进行求解。在适当的假设下证明了算法的全局收敛性。在数值实验中对两类3D彩色图像进行了重建测试，其中一类含有30%的盐噪声，另一类含有30%的椒盐噪声。实验过程中将ADMM算法与JP算法及YALL1算法的恢复效果进行了数值对比。实验结果表明无论从峰值信噪比PSNR还是从相对误差RelErr角度考察，我们方法的数值结果都明显得到了改善，因而该方法具有较好的图像恢复效果。

2. 模型的转化

本节给出求解问题(1)的如下加权 $l_1$ 范数极小化模型：

$\underset{x_1,x_2}{\min }\{\mu {\displaystyle \underset{i=1}{\overset{n_1}{\sum }}{\omega }_{1_i}\left|x_{1_i}\right|+{\displaystyle \underset{j=1}{\overset{n_2}{\sum }}{\omega }_{2_j}\left|x_{2_j}\right|}\}},\text{s}\text{.t}.A_1{x}_1+A_2{x}_2=y$ (2)

其中 ${\omega }_{1_i}=0.3{{\displaystyle \left(x_{1_i}^2+{0.01}^2\right)}}^{-\frac{1}{4}},{\omega }_{2_j}=0.3{{\displaystyle \left(x_{2_j}^2+{0.01}^2\right)}}^{-\frac{1}{4}},i=1,\cdots ,n_1;j=1,\cdots ,n_2$ 为加权因子。

显然，对充分小的 $\epsilon >0$，(2)可近似为

$\underset{x_1,x_2}{\min }\{\mu {\displaystyle \underset{i=1}{\overset{n_1}{\sum }}{\omega }_{1_i}\left|x_{1_i}\right|+{\displaystyle \underset{j=1}{\overset{n_2}{\sum }}{\omega }_{2_j}\left|x_{2_j}\right|}\}},\text{s}\text{.t}.{\Vert A_1{x}_1+A_2{x}_2-y\Vert }_2\le \epsilon$ (3)

因此， $\epsilon$ 充分小时，(3)的解趋于(2)的解。该约束优化问题可以转化为下述无约束形式

$\underset{x_1,x_2}{\min }\left\{\frac{1}{\beta }{\Vert A_1{x}_1+A_2{x}_2-y\Vert }_2^2+\mu {\displaystyle \underset{i=1}{\overset{n_1}{\sum }}{\omega }_{1_i}\left|x_{1_i}\right|}+{\displaystyle \underset{j=1}{\overset{n_2}{\sum }}{\omega }_{2_j}\left|x_{2_j}\right|}\right\}$ (4)

这里 $\beta >0$ 是一个惩罚因子，问题(3)中的较小的 $\epsilon$ 相当于问题(4)中较小的 $\beta$。随着 $\beta \to 0$，(4)的解满足 ${\Vert A_1{x}_1+A_2{x}_2-y\Vert }_2\to 0$，且问题(4)近似于问题(2)。因此，取一个充分小的 $\beta$ 可使得

${\Vert A_1{x}_1+A_2{x}_2-y\Vert }_2\approx 0$

3. 算法及收敛性证明

3.1. ADMM算法

ADMM是一个非常适合解决高维优化问题的算法，可以较容易地处理全局问题。因此本文应用ADMM算法求解(4)。通过引入辅助变量 $z_1,z_2$，(4)等价于

$\underset{x_1,x_2,z_1,z_2}{\min }\left\{{\Vert A_1{x}_1+A_2{x}_2-y\Vert }_2^2+\beta \mu {\displaystyle \underset{i=1}{\overset{n_1}{\sum }}{\omega }_{1_i}\left|z_{1_i}\right|}+\beta {\displaystyle \underset{j=1}{\overset{n_2}{\sum }}{\omega }_{2_j}\left|z_{2_j}\right|}\right\},\text{s}\text{.t}\text{.}A{x}_1=z_1,x_2=z_2$

其增广拉格朗日函数为

$\begin{array}{l}L\left(x_1,x_2,z_1,z_2,w_1,w_2\right)\\ ={\Vert A_1{x}_1+A_2{x}_2-y\Vert }_2^2+\beta \mu {\displaystyle \underset{i=1}{\overset{n_1}{\sum }}{\omega }_{1_i}\left|z_{1_i}\right|}+\beta {\displaystyle \underset{j=1}{\overset{n_2}{\sum }}{\omega }_{2_j}\left|z_{2_j}\right|}+\langle w_1,x_1-z_1\rangle +\langle w_2,x_2-z_2\rangle +\frac{{\rho }_1}{2}{\Vert x_1-z_1\Vert }_2^2+\frac{{\rho }_2}{2}{\Vert x_2-z_2\Vert }_2^2,\end{array}$

这里的 $w_1$ 和 $w_2$ 是对偶变量， ${\rho }_1$ 和 ${\rho }_2$ 是正惩罚因子。ADMM算法迭代格式如下：

$z_1^{k+1}=\arg \underset{z_1}{\min }\left(\beta \mu {\displaystyle \underset{i=1}{\overset{n_1}{\sum }}{\omega }_{1_i}\left|z_{1_i}\right|+}\frac{{\rho }_1}{2}{\Vert x_1^k-z_1+\frac{w_1^k}{{\rho }_1}\Vert }_2^2\right)$ (5)

$z_2^{k+1}=\arg \underset{z_2}{\min }\left(\beta {\displaystyle \underset{j=1}{\overset{n_2}{\sum }}{\omega }_{2_j}\left|z_{2_j}\right|}+\frac{{\rho }_2}{2}{\Vert x_2^k-z_2+\frac{w_2^k}{{\rho }_2}\Vert }_2^2\right)$ (6)

$x_1^{k+1}=\arg \underset{x_1}{\min }\left({\Vert A_1{x}_1+A_2{x}_2^k-y\Vert }_2^2+\frac{{\rho }_1}{2}{\Vert x_1-z_1^{k+1}+\frac{w_1^k}{{\rho }_1}\Vert }_2^2\right)$ (7)

$x_2^{k+1}=\arg \underset{x_2}{\min }\left({\Vert A_1{x}_1^{k+1}+A_2{x}_2-y\Vert }_2^2+\frac{{\rho }_2}{2}{\Vert x_2-z_2^{k+1}+\frac{w_2^k}{{\rho }_2}\Vert }_2^2\right)$ (8)

$w_1^{k+1}=w_1^k+{\rho }_1\left(x_1^{k+1}-z_1^{k+1}\right)$ (9)

$w_2^{k+1}=w_2^k+{\rho }_2\left(x_2^{k+1}-z_2^{k+1}\right)$ (10)

3.2. 加权l₁范数的临近算子

为求解(5)和(6)，我们引入加权 $l_1$ 范数的临近算子。

定义1 [5] 对 $x\in R^m$，其 $l_q$ 范数( $0\le q\le 1$ )函数的临近算子定义为

${\text{prox}}_{q,\eta }\left(t\right)=\arg \underset{x}{\min }\left\{{\Vert x\Vert }_q^q+\frac{\eta }{2}{\Vert x-t\Vert }_2^2\right\}$

其中 $\eta >0$ 为惩罚因子。当 $q=1$ 时，其解的表达形式为

${\text{prox}}_{1,\eta }{\left(t\right)}_i=\text{sign}\left(t_i\right)\max \left\{\left|t_i\right|-1/\eta ,0\right\},i=1,\cdots ,m$

下面对 $x\in R^m$ 定义本文的加权 $l_1$ 范数函数的临近算子

${\text{prox}}_{1,\eta }\left(t\right)=\arg \underset{x}{\min }\left\{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{h}_i\left|x_i\right|}+\frac{\eta }{2}{\Vert x-t\Vert }_2^2\right\}$

其中 $h_i=0.3{\left(x_i^2+{0.01}^2\right)}^{-\frac{1}{4}},i=1,\cdots ,m$。可将其化简为

${\text{prox}}_{1,\eta }\left(t\right)=\arg \underset{x}{\min }\left\{{\displaystyle \underset{i=1}{\overset{m}{\sum }}\left(h_i\left|x_i\right|+\frac{\eta }{2}{\left(x_i-t_i\right)}^2\right)}\right\}$ (11)

当 $x_i\ge 0$ 时，(11)等价为

$x_i=t_i-\frac{h_i}{\eta },t_i=x_i+\frac{h_i}{\eta },i=1,\cdots ,m$

因此 $t_i\ge 0$。当 $t_i-\frac{h_i}{\eta }\le 0$ 时，结合 $x_i\ge 0$ 可得 $x_i=0$。综上可表述为

${\text{prox}}_{1,\eta }{\left(t\right)}_i=\max \{t_i-\frac{h_i}{\eta },0\},t_i\ge 0,i=1,\cdots ,m$ (12)

同理当 $x_i\le 0$ 时，(11)等价为

$x_i=-\left(-t_i-\frac{h_i}{\eta }\right),t_i=x_i-\frac{h_i}{\eta },i=1,\cdots ,m$

因此 $t_i\le 0$。当 $-t_i-\frac{h_i}{\eta }\le 0$ 时，结合 $x_i\le 0$ 可得 $x_i=0$。综上可表述为

${\text{prox}}_{1,\eta }{\left(t\right)}_i=-\max \{-t_i-\frac{h_i}{\eta },0\},t_i\le 0,i=1,\cdots ,m$ (13)

结合(12)与(13)可得，加权 $l_1$ 范数函数的临近算子解的表达形式为

${\text{prox}}_{1,\eta }{\left(t\right)}_i=\text{sign}\left(t_i\right)\max \left\{\left|t_i\right|-h_i/\eta ,0\right\},i=1,\cdots ,m$

3.3. 收敛性证明

此处我们讨论ADMM算法的收敛性。

为叙述方便，定义如下符号： ${\lambda }_i={\lambda }_{\max }\left(A_i^{{\rm T}}{A}_i\right)$， ${\phi }_i={\lambda }_{\min }\left(A_i^{{\rm T}}{A}_i\right)$， $i=1,2$。设 $\left\{v^k\right\}$ 是本文算法产生的序列， $v^k:=\left(x_1^k,x_2^k,z_1^k,z_2^k,w_1^k,w_2^k\right)$。令 ${\tilde{v}}^k:=\left(x_1^k,x_2^k,z_1^k,z_2^k,w_1^k,w_2^k,x_2^{k-1}\right)$， $c_1=8{\lambda }_1{\lambda }_2/{\rho }_1$，

$\tilde{L}\left(v^k,\tilde{x}\right):=L\left(v^k\right)+c_1{\Vert x_2^k-\tilde{x}\Vert }_2^2$，从而 $\tilde{L}\left({\tilde{v}}^k\right):=L\left(v^k\right)+c_1{\Vert x_2^k-x_2^{k-1}\Vert }_2^2$。

引理 1 设序列 $\left\{v^k\right\}$ 由(5)~(10)产生，如果下式成立

${\rho }_1>\frac{16{\lambda }_1^2}{{\rho }_1}+\frac{16{\lambda }_1{\lambda }_2}{{\rho }_2}-2{\phi }_1,{\rho }_2>\frac{16{\lambda }_2^2}{{\rho }_2}+\frac{16{\lambda }_1{\lambda }_2}{{\rho }_1}-2{\phi }_2$ (14)

则

$\tilde{L}\left(v^{k+1},x_2^k\right)+c_2{\Vert x_1^{k+1}-x_1^k\Vert }_2^2+c_3{\Vert x_2^{k+1}-x_2^k\Vert }_2^2\le \tilde{L}\left(v^k,x_2^{k-1}\right)$

其中参数 $c_2>0$， $c_3>0$，且

$c_2=\frac{2{\phi }_1+{\rho }_1}{2}-\frac{8{\lambda }_1^2}{{\rho }_1}-\frac{8{\lambda }_1{\lambda }_2}{{\rho }_2},c_3=\frac{2{\phi }_2+{\rho }_2}{2}-\frac{8{\lambda }_2^2}{{\rho }_2}-\frac{8{\lambda }_1{\lambda }_2}{{\rho }_1}$

证明 此引理的证明与文献 [5] 的引理1的证明相似，故略。

引理2 设序列 $\left\{v^k\right\}$ 由(5~(10)产生，如果(14)满足，那么 $\underset{k\to \infty }{\lim }{\Vert v^{k+1}-v^k\Vert }_2^2=0$，故 $\left\{v^k\right\}$ 的任何聚点都是 $L$

的一个驻点。

证明 由(7)得出的最小值 $x_1^{k+1}$ 满足

$2A_1^{{\rm T}}\left(A_1{x}_1^{k+1}+A_2{x}_2^k-y\right)+{\rho }_1\left(x_1^{k+1}-z_1^{k+1}+w_1^k/{\rho }_1\right)=0$

将(9)代入其中有

$w_1^{k+1}=-2A_1^{{\rm T}}\left(A_1{x}_1^{k+1}+A_2{x}_2^k-y\right)$ (15)

从而结合 ${\lambda }_{\max }\left(A_1{A}_1^{{\rm T}}\right)={\lambda }_{\max }\left(A_1^{{\rm T}}{A}_1\right)={\lambda }_1$， ${\lambda }_{\max }^2\left(A_1^{{\rm T}}{A}_2\right)\le {\lambda }_1{\lambda }_2$ 有

${\Vert w_1^k\Vert }_2^2\le \frac{16}{3}{\lambda }_1{\Vert A_1{x}_1^k+A_2{x}_2^k-y\Vert }_2^2+16{\lambda }_1{\lambda }_2{\Vert x_2^k-x_2^{k-1}\Vert }_2^2$ (16)

类似地，结合(8)及(10)可得

$w_2^{k+1}=-2A_2^{{\rm T}}\left(A_1{x}_1^{k+1}+A_2{x}_2^{k+1}-y\right)$ (17)

${\Vert w_2^k\Vert }_2^2\le 4{\lambda }_2{\Vert A_1{x}_1^k+A_2{x}_2^k-y\Vert }_2^2$ (18)

因为 $\tilde{L}\left({\tilde{v}}^k\right)$ 下半连续，故下有界。由引理1可知当满足(14)时， $\tilde{L}\left({\tilde{v}}^k\right)$ 非增，因此收敛。对于 $k>1$，由 $\tilde{L}$ 的定义及(16)和(18)有

$\frac{8{\lambda }_1{\lambda }_2}{{\rho }_1}{\Vert x_2^k-x_2^{k-1}\Vert }_2^2-\frac{{\Vert w_1^k\Vert }_2^2}{2{\rho }_1}\ge -\frac{8{\lambda }_1}{3{\rho }_1}{\Vert A_1{x}_1^k+A_2{x}_2^k-y\Vert }_2^2,-\frac{{\Vert w_2^k\Vert }_2^2}{2{\rho }_2}\ge -\frac{2{\lambda }_2}{{\rho }_2}{\Vert A_1{x}_1^k+A_2{x}_2^k-y\Vert }_2^2$

因此

$\tilde{L}\left({\tilde{v}}^1\right)\ge \tilde{L}\left({\tilde{v}}^k\right)\ge c_4{\Vert A_1{x}_1^k+A_2{x}_2^k-y\Vert }_2^2+\beta \mu {\displaystyle \underset{i=1}{\overset{n_1}{\sum }}{\omega }_{1_i}^k\left|z_{1_i}^k\right|}+\beta {\displaystyle \underset{j=1}{\overset{n_2}{\sum }}{\omega }_{2_j}^k\left|z_{2_j}^k\right|}+\frac{{\rho }_1}{2}{\Vert x_1^k-z_1^k+\frac{w_1^k}{{\rho }_1}\Vert }_2^2+\frac{{\rho }_2}{2}{\Vert x_2^k-z_2^k+\frac{w_2^k}{{\rho }_2}\Vert }_2^2$

这里的 $c_4=1-\frac{8{\lambda }_1}{3{\rho }_1}-\frac{2{\lambda }_2}{{\rho }_2}$。令 $x=\frac{{\lambda }_1}{{\rho }_1}$， $y=\frac{{\lambda }_2}{{\rho }_2}$，且 ${\phi }_1\le {\lambda }_1$， ${\phi }_2\le {\lambda }_2$，故(14)可以转化为 $0<y<\frac{1}{16x}-x+\frac{1}{8}$， $0<x<\frac{1}{16y}-y+\frac{1}{8}$，且 $c_4=1-\frac{8}{3}x-2y$。由文献 [5] 的引理2证明过程可知，当 $x,y$ 同时满足上述两个不等式时， $f\left(x,y\right)=\frac{8}{3}x+2y$ 的最大值小于1，即 $1-\frac{8}{3}x-2y>0$。因此当(14)成立时，有 $c_4>0$。从而序列 $\left\{v^k\right\}$

有界。故对于有界序列 $\left\{{\tilde{v}}^k\right\}$，必存在一个收敛子列 $\left\{{\tilde{v}}^{k_j}\right\}$ 收敛到聚点 ${\tilde{v}}^{\ast }$，又 $\tilde{L}\left({\tilde{v}}^k\right)$ 在 $c_2,c_3>0$ 时非增收敛，

那么对任意 $k\ge 1$ 都有 $\tilde{L}\left({\tilde{v}}^k\right)\ge \tilde{L}\left({\tilde{v}}^{\ast }\right)$，从而结合引理1可得

$c_2{\displaystyle \underset{k=1}{\overset{N}{\sum }}{\Vert x_1^{k+1}-x_1^k\Vert }_2^2}+c_3{\displaystyle \underset{k=1}{\overset{N}{\sum }}{\Vert x_2^{k+1}-x_2^k\Vert }_2^2}\le {\displaystyle \underset{k=1}{\overset{N}{\sum }}\left[\tilde{L}\left({\tilde{v}}^k\right)-\tilde{L}\left({\tilde{v}}^{k+1}\right)\right]}$

综上

$c_2{\displaystyle \underset{k=1}{\overset{N}{\sum }}{\Vert x_1^{k+1}-x_1^k\Vert }_2^2}+c_3{\displaystyle \underset{k=1}{\overset{N}{\sum }}{\Vert x_2^{k+1}-x_2^k\Vert }_2^2}\le {\displaystyle \underset{k=1}{\overset{N}{\sum }}\left[\tilde{L}\left({\tilde{v}}^k\right)-\tilde{L}\left({\tilde{v}}^{k+1}\right)\right]}=\tilde{L}\left({\tilde{v}}^1\right)-\tilde{L}\left({\tilde{v}}^{N+1}\right)\le \tilde{L}\left({\tilde{v}}^1\right)-\tilde{L}\left({\tilde{v}}^{\ast }\right)<\infty$

令 $N\to \infty$，当 $c_2,c_3>0$ 时有

${\displaystyle \underset{k=1}{\overset{\infty }{\sum }}{\Vert x_1^{k+1}-x_1^k\Vert }_2^2}<\infty ,{\displaystyle \underset{k=1}{\overset{\infty }{\sum }}{\Vert x_2^{k+1}-x_2^k\Vert }_2^2}<\infty$ (19)

由(15)有

${\Vert w_1^{k+1}-w_1^k\Vert }_2^2\le 4{\left({\Vert A_1^{{\rm T}}{A}_1\left(x_1^{k+1}-x_1^k\right)\Vert }_2+{\Vert A_1^{{\rm T}}{A}_2\left(x_2^k-x_2^{k-1}\right)\Vert }_2\right)}^2\le 8{\lambda }_1^2{\Vert x_1^{k+1}-x_1^k\Vert }_2^2+8{\lambda }_1{\lambda }_2{\Vert x_2^k-x_2^{k-1}\Vert }_2^2$ (20)

同理由(17)可得

${\Vert w_2^{k+1}-w_2^k\Vert }_2^2\le 8{\lambda }_1{\lambda }_2{\Vert x_1^{k+1}-x_1^k\Vert }_2^2+8{\lambda }_2^2{\Vert x_2^{k+1}-x_2^k\Vert }_2^2$ (21)

再结合(20)有

${\displaystyle \underset{k=1}{\overset{\infty }{\sum }}{\Vert w_1^{k+1}-w_1^k\Vert }_2^2}<\infty ,{\displaystyle \underset{k=1}{\overset{\infty }{\sum }}{\Vert w_2^{k+1}-w_2^k\Vert }_2^2}<\infty$ (22)

再据(19)和(22)可得 ${\displaystyle \underset{k=1}{\overset{\infty }{\sum }}{\Vert z_1^{k+1}-z_1^k\Vert }_2^2}<\infty$， ${\displaystyle \underset{k=1}{\overset{\infty }{\sum }}{\Vert z_2^{k+1}-z_2^k\Vert }_2^2}<\infty$。因此 $\underset{k\to \infty }{\lim }{\Vert v^{k+1}-v^k\Vert }_2^2=0$。故可知由(5)~(10)

产生的序列 $\left\{v^k\right\}$ 的任何聚点都是 $L$ 的一个驻点，且由最优性条件可知其满足

$\{\begin{array}{l}0\in \beta \mu \partial {\displaystyle \underset{i=1}{\overset{n_1}{\sum }}{\omega }_{1_i}^{k+1}\left|z_{1_i}^{k+1}\right|-w_1^{k+1}+{\rho }_1\left(x_1^{k+1}-x_1^k\right),}\hfill \\ 0\in \beta \partial {\displaystyle \underset{j=1}{\overset{n_2}{\sum }}{\omega }_{2_j}^{k+1}\left|z_{2_j}^{k+1}\right|-w_2^{k+1}+{\rho }_2\left(x_2^{k+1}-x_2^k\right),}\hfill \\ 0=w_1^{k+1}+2A_1^{{\rm T}}\left(A_1{x}_1^{k+1}+A_2{x}_2^k-y\right),\hfill \\ 0=w_2^{k+1}+2A_2^{{\rm T}}\left(A_1{x}_1^{k+1}+A_2{x}_2^{k+1}-y\right),\hfill \\ w_1^{k+1}=w_1^k+{\rho }_1\left(x_1^{k+1}-z_1^{k+1}\right),\hfill \\ w_2^{k+1}=w_2^k+{\rho }_2\left(x_2^{k+1}-z_2^{k+1}\right).\hfill \end{array}$ (23)

取 $\left\{v^k\right\}$ 的一个收敛子列 $\left\{v^{k_j}\right\}$。因 $\underset{k\to \infty }{\lim }{\Vert v^{k+1}-v^k\Vert }_2^2=0$，从而 $v^{k_j}$ 和 $v^{k_j+1}$ 有相同的极限点 $v^{\ast }:=\left(x_1^{\ast },x_2^{\ast },z_1^{\ast },z_2^{\ast },w_1^{\ast },w_2^{\ast }\right)$。由于 $\tilde{L}\left({\tilde{v}}^k\right)$ 收敛，故 ${\displaystyle \underset{i=1}{\overset{n_1}{\sum }}{\omega }_{1_i}^{k+1}\left|z_{1_i}^{k+1}\right|}$， ${\displaystyle \underset{j=1}{\overset{n_2}{\sum }}{\omega }_{2_j}^{k+1}\left|z_{2_j}^{k+1}\right|}$ 收敛。对(23)两侧求极限可得

$x_1^{\ast }=z_1^{\ast },x_2^{\ast }=z_2^{\ast },w_1^{\ast }\in \beta \mu \partial {\displaystyle \underset{i=1}{\overset{n_1}{\sum }}{\omega }_{1_i}^{\ast }\left|z_{1_i}^{\ast }\right|},w_2^{\ast }\in \beta \partial {\displaystyle \underset{j=1}{\overset{n_2}{\sum }}{\omega }_{2_j}^{\ast }\left|z_{2_j}^{\ast }\right|}$

$-w_1^{\ast }=2A_1^{{\rm T}}\left(A_1{x}_1^{\ast }+A_2{x}_2^{\ast }-y\right),-w_2^{\ast }=2A_2^{{\rm T}}\left(A_1{x}_1^{\ast }+A_2{x}_2^{\ast }-y\right)$

故 $v^{\ast }$ 是 $L$ 的一个驻点。

引理3 函数 $\tilde{L}\left(v^k,\tilde{x}\right)$ 如前定义，若(14)成立，则存在常数 $c_5>0$，使得

$\text{dist}\left(0,\partial \tilde{L}\left(v^{k+1},x_2^k\right)\right)\le c_5({\Vert x_1^{k+1}-x_1^k\Vert }_2+{\Vert x_2^{k+1}-x_2^k\Vert }_2+{\Vert x_2^k-x_2^{k-1}\Vert }_2)$

证明 由 $\tilde{L}$ 的定义可得

${\partial }_{z_1}\tilde{L}\left({\tilde{v}}^{k+1}\right)=\beta \mu \partial {\displaystyle \underset{i=1}{\overset{n_1}{\sum }}{\omega }_{1_i}^{k+1}}\left|z_{1_i}^{k+1}\right|-w_1^{k+1}-{\rho }_1\left(x_1^{k+1}-z_1^{k+1}\right)=\beta \mu \partial {\displaystyle \underset{i=1}{\overset{n_1}{\sum }}{\omega }_{1_i}^{k+1}\left|z_{1_i}^{k+1}\right|}-w_1^{k+1}-\left(w_1^{k+1}-w_1^k\right)$

结合(23)有 ${\rho }_1\left(x_1^k-x_1^{k+1}\right)+\left(w_1^k-w_1^{k+1}\right)\in {\partial }_{z_1}\tilde{L}\left({\tilde{v}}^{k+1}\right)$。类似可得：

$\begin{array}{l}{\rho }_2\left(x_2^k-x_2^{k+1}\right)+\left(w_2^k-w_2^{k+1}\right)\in {\partial }_{z_2}\tilde{L}\left({\tilde{v}}^{k+1}\right),{\partial }_{\tilde{x}}\tilde{L}\left({\tilde{v}}^{k+1}\right)=2c_1\left(x_2^k-x_2^{k+1}\right),\\ {\partial }_{x_1}\tilde{L}\left({\tilde{v}}^{k+1}\right)=w_1^{k+1}-w_1^k,{\partial }_{x_2}\tilde{L}\left({\tilde{v}}^{k+1}\right)=\left(w_2^{k+1}-w_2^k\right)+2c_1\left(x_2^{k+1}-x_2^k\right),\\ {\partial }_{w_1}\tilde{L}\left({\tilde{v}}^{k+1}\right)=\left(w_1^{k+1}-w_1^k\right)/{\rho }_1,{\partial }_{w_2}\tilde{L}\left({\tilde{v}}^{k+1}\right)=\left(w_2^{k+1}-w_2^k\right)/{\rho }_2.\end{array}$

因此，存在常数 $c_6>0$ 使得

$\text{dist}\left(0,\partial \tilde{L}\left({\tilde{v}}^{k+1}\right)\right)\le c_6\left({\Vert x_1^{k+1}-x_1^k\Vert }_2+{\Vert x_2^{k+1}-x_2^k\Vert }_2+{\Vert w_1^{k+1}-w_1^k\Vert }_2+{\Vert w_2^{k+1}-w_2^k\Vert }_2\right)$

再由引理2的证明可得结论。

注：这个结论为迭代间隙提供了一个次梯度下界，同时结合引理2可得出当 $k\to \infty$ 时，

$\text{dist}\left(0,\partial \tilde{L}\left({\tilde{v}}^{k+1}\right)\right)\to 0$

定理1 若(14)成立，则本文算法产生的点列 $\left\{v^k\right\}$ 收敛到问题(4)的一个聚点。

证明 首先证明序列 $\left\{v^k\right\}$ 满足

${\displaystyle \underset{k=0}{\overset{\infty }{\sum }}\Vert v^{k+1}-v^k\Vert }{}_2<\infty$ (24)

对于本文定义的加权 $l_1$ 范数 ${\displaystyle \underset{i=1}{\overset{m}{\sum }}{h}_i\left|x_i\right|}={\displaystyle \underset{i=1}{\overset{m}{\sum }}0.3{\left(x_i^2+\epsilon \right)}^{-\frac{1}{4}}\left|x_i\right|}$，当 $\epsilon \to 0$ 时， $0.3{\left(x_i^2+\epsilon \right)}^{-\frac{1}{4}}\left|x_i\right|\to 0.3{\left|x_i\right|}^{\frac{1}{2}}$。取定任意小的正数 $\delta$，当 $\epsilon \in \left(0,\delta \right)$ 时， $0.3{\left(x_i^2+\epsilon \right)}^{-\frac{1}{4}}\left|x_i\right|=0.3{\left|x_i\right|}^{\frac{1}{2}}+o\left(\epsilon \right)$。因 ${\left|x_i\right|}^{\frac{1}{2}}$ 是KL函数，故当 $\epsilon$ 充分小时， ${\displaystyle \underset{i=1}{\overset{m}{\sum }}{h}_i\left|x_i\right|}={\displaystyle \underset{i=1}{\overset{m}{\sum }}0.3{\left(x_i^2+\epsilon \right)}^{-\frac{1}{4}}\left|x_i\right|}$ 是KL函数，从而 $\tilde{L}$ 也为KL函数，故(24)成立。因此迭代点列 $\left\{v^k\right\}$ 是

柯西列且收敛，结合引理2可得迭代点列 $\left\{v^k\right\}$ 全局收敛到 $L$ 的一个聚点。关于(24)的详细证明可参考文献 [6]，此处略去。

4. 数值实验

本节测试两组3D彩色图像恢复实验，程序用Matlab2017a编写。为加速算法，对参数 $\beta$ 采取如下措施：对于 ${\beta }_k>{10}^{-6}$， ${\beta }_k=0.97{\beta }_{k-1}$，否则 ${\beta }_k={10}^{-6}$。取 $A_2=I$， $A_1$ 为逆离散余弦变换(IDCT)矩阵，因此 $x_1$ 是图像的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的减少量也较大。由此可见，基于本文提出的加权 $l_1$ 范数极小化模型的ADMM算法在3D彩色图像重建中具有有效性。

5. 结论

本文针对具有两个稀疏信号的恢复问题，提出了加权 $l_1$ 范数极小化模型，通过模型的等价转化应用ADMM算法进行求解。在适当地假设下证明了算法的收敛性。在数值试验中，对具有30%盐噪声和30%椒盐噪声的3D彩色图像分别进行了恢复，并与经典的JP算法及YALL1算法进行了数值比对。实验结果表明相比于其他两个算法，ADMM算法的峰值信噪比PSNR明显提高，而相对误差RelErr明显降低，因此具有较好的图像恢复效果。