基于l₁-al₂最小化的部分支集已知的信号重建

Signal Reconstruction with Known Partial Support Based on l₁-al₂ Minimization

摘要: 压缩感知中测量矩阵的限制等距性在一定条件下可以确保重建稀疏信号。文章在l₁-al₂(0 < a≤1)最小化问题模型下，根据已知信号的先验支撑信息，利用测量矩阵的限制等距性，研究了三种噪声(高斯噪声、脉冲噪声、均匀噪声)情形下信号恢复的充分条件。这些条件直观地揭示了测量矩阵的限制等距性和信号恢复之间的密切关系。

Abstract: The restricted isometry property of the measurement matrix in compressed sensing can ensure the reconstruction of sparse signals under certain conditions. In this paper, the sufficient conditions for signal recovery under three kinds of noise (Gaussian noise, impulse noise and uniform noise) are studied according to the known prior support information of the signal and the restricted isometry property of the measurement matrix under l₁-al₂(0 < a≤1) minimization model. These conditions intuitively reveal the close relationship between the restricted isometry property of the measurement matrix and signal recovery.

1. 引言

压缩感知的目标之一是研究从线性测量值 $y={\rm A}x+e$ 中恢复稀疏或可压缩信号 $x\in {ℝ}^n$，其中 ${\rm A}$ 是一个 $m\times n$ 测量矩阵( $m\ll n$ )，e是一个噪声向量。已经有许多文章介绍和研究了信号恢复方法。例如：凸 ${\mathcal{l}}_1$ 最小化 [1] [2] [3] [4] [5]，非凸 ${\mathcal{l}}_p\left(0<p<1\right)$ 最小化 [6] [7] [8]，非凸 ${\mathcal{l}}_{1-2}$ 最小化 [9] - [14]。

为了从 $y={\rm A}x+e$ 中恢复信号x，最直观的方法是通过求解 ${\mathcal{l}}_0$ 最小化问题找到最稀疏信号：

$\underset{x\in {ℝ}^n}{\min }{\Vert x\Vert }_0$ s.t. $b-{\rm A}x\in B,$ (1)

其中 ${\Vert x\Vert }_0$ 表示x中非零项的个数，B是由误差结构决定的一个有界集。然而问题(1)是NP-难，因此在高维情形下计算上是不可行的。为了获得式(1)的(近似)解，因此文献 [1] 提出了有约束的 ${\mathcal{l}}_1$ 最小化问题作为式(1)的一个凸松弛，即

$\underset{x\in {ℝ}^n}{\min }{\Vert x\Vert }_1$ s.t. $b-{\rm A}x\in B,$ (2)

近几年，文献 [10] [15] 提出了从 $y={\rm A}x+e$ 中恢复 $x\in {ℝ}^n$ 的非凸 ${\mathcal{l}}_1-\alpha {\mathcal{l}}_2$ $\left(0<\alpha \le 1\right)$ 最小化方法。

$\underset{x\in {ℝ}^n}{\min }{\Vert x\Vert }_1-\alpha {\Vert x\Vert }_2$ s.t. $b-{\rm A}x\in B,$ (3)

很明显，当 $\alpha =1$ 时，式(3)可化简为 ${\mathcal{l}}_{1-2}$ 最小化。事实上，非凸 ${\mathcal{l}}_1-\alpha {\mathcal{l}}_2$ 最小化方法在稀疏信号恢复问题上优于许多现存的压缩感知求解方法 [14] [16] [17]。其中，文献 [14] 说明了用 $\alpha =1$ 时的 ${\mathcal{l}}_1-\alpha {\mathcal{l}}_2$ 最小化方法得到基于测量矩阵限制等距性的信号恢复的充分条件要优于许多现存的压缩感知求解方法得到的类似条件；文献 [16] [17] 使用了一种分解向量的新方法，说明了在脉冲噪声、均匀噪声下利用 ${\mathcal{l}}_1-\alpha {\mathcal{l}}_2$ 最小化方法恢复信号的性能优于许多现存的压缩感知求解方法。在实际应用中，信号恢复通常会利用自身的一些先验信息来提高恢复的效率，减少测量次数，文献 [18] [19] [20] 证明了这类方法可以提高恢复的性能。其中，文献 [18] 基于此类方法提出了一种改进的基追踪算法，证明了该方法能够更好地恢复信号；文献 [19] 证明了当信号的先验支撑度至少为50%时，用标准 ${\mathcal{l}}_1$ 最小化方法得到信号恢复的充分条件要弱于类似条件，同时证明在附加条件下重建的误差上界更小；文献 [20] 证明了当信号的部分支集已知时，使用 ${\mathcal{l}}_p\left(0<p<1\right)$ 最小化来恢复稀疏和可压缩信号提高了性能，并且重建信号所需的样本数较少。正如Blanchard和Thompson [21] 指出的，在某些情况下，更高阶的高斯随机矩阵可以满足基于高阶限制等距性的充分条件。因此，获得基于高阶限制等距性的改进的充分条件具有理论和实践意义。

文章感兴趣的是利用 ${\mathcal{l}}_1-\alpha {\mathcal{l}}_2$ 最小化方法对部分支集已知的信号进行恢复的问题。现考虑如下约束优化问题：

$\underset{x\in {ℝ}^n}{\min }{\Vert x_{T^c}\Vert }_1-\alpha {\Vert x_{T^c}\Vert }_2$ s.t. $b-{\rm A}x\in B,$ (4)

其中，B取决于噪声的类型，如高斯噪声、脉冲噪声、均匀噪声。特别地，在无噪声情形下( $B=\left\{0\right\}$ )有：

$\underset{x\in {ℝ}^n}{\min }{\Vert x_{T^c}\Vert }_1-\alpha {\Vert x_{T^c}\Vert }_2$ s.t. $b={\rm A}x,$ (5)

其中，T为x的部分已知支撑， $T^c=\left[1,2,\cdots ,n\right]/T$。

受文献 [14] [16] [17] 的启发，文章使用将向量分解为稀疏向量的新方法，讨论了 ${\mathcal{l}}_1-\alpha {\mathcal{l}}_2$ $\left(0<\alpha \le 1\right)$ 最小化模型下，关于部分支撑信息已知的信号的恢复问题，尽可能有效地使用了限制等距性条件。据我们所知，这是首篇系统研究三种噪声下部分支撑信息已知的信号恢复的文章。

2. 预备知识

首先引入一些定义 [16] [22] 和引理 [13] [14] [16] [17] [23] 来为文章的主要结果作铺垫。

定义1 [16] 对于 $0<p\le 1$ 或 $p=2$， $s\in {\mathbb{Z}}_{+}$，我们将相对于测量矩阵 ${\rm A}$ 的s阶 $\left({\mathcal{l}}_2,{\mathcal{l}}_p\right)$ 受限等距常数对 $\left({\delta }_s^{lb},{\delta }_s^{ub}\right)$ 定义为：对所有s-稀疏信号x，使得

$\left(1-{\delta }_s^{lb}\right){\Vert x\Vert }_2^p\le {\Vert {\rm A}x\Vert }_p^p\le \left(1+{\delta }_s^{ub}\right){\Vert x\Vert }_2^p$ (6)

成立的最小数 ${\delta }_s^{lb}$ 和 ${\delta }_s^{ub}$。若对于相当大的s，式(6)中 ${\delta }_s^{lb}$ 和 ${\delta }_s^{ub}$ 是最小的，则称 ${\rm A}$ 满足 $\left({\mathcal{l}}_2,{\mathcal{l}}_p\right)$ -RIP(简称：限制等距性)。

定义2 [16] 若对所有s-稀疏向量 $x\in {ℝ}^n$，即 ${\Vert x\Vert }_0\le s$ (s是一个整数)，使得

$\left(1-{\delta }_s\right){\Vert x\Vert }_2^2\le {\Vert {\rm A}x\Vert }_2^2\le \left(1+{\delta }_s\right){\Vert x\Vert }_2^2$ (7)

成立( ${\delta }_s\in \left[0,1\right)$ )，则称矩阵 ${\rm A}\in {ℝ}^{m\times n}$ 满足s阶 $\left({\mathcal{l}}_2,{\mathcal{l}}_2\right)$ -RIP。最小常数 ${\delta }_s$ 被称为限制等距常数。

定义3 [22] 矩阵 ${\rm A}$ 的相干性 $\mu \left({\rm A}\right)$ 是 ${\rm A}$ 各列之间相互关联的最大绝对值，即

$\mu \left({\rm A}\right):=\underset{i\ne j}{\max }\frac{\left|\langle {{\rm A}}_i,{{\rm A}}_j\rangle \right|}{{\Vert {{\rm A}}_i\Vert }_2{\Vert {{\rm A}}_j\Vert }_2}.$

下面引理1是从文献( [13]，定理3.3)的证明中引出的一个引理，它是 ${\mathcal{l}}_1-\alpha {\mathcal{l}}_2$ $\left(0<\alpha \le 1\right)$ 在信号的部分支集已知的假设下的一个修正的锥约束不等式。

为叙述方便，在这里对符号进行说明：向量 $x,\hat{x}\in {ℝ}^n$，其中x是原始信号， $\hat{x}$ 是式(4)的解。令 $h=\hat{x}-x$，T是信号x的已知支集( $\left|T\right|=r$ )， $T_0$ 是h中 $s\in {\mathbb{Z}}_{+}$ 个最大绝对值项组成的指标集， $T_1$ 是 $h_{T_0{}^c}$ 中 $k\in {\mathbb{Z}}_{+}$ 个最大绝对值项组成的指标集， $T_{\overline{01}}=T\cup T_0\cup T_1$， $T_{\overline{01}}{}^c\subseteq \left[n\right]$ 是 $T_{\overline{01}}$ 的补集。

引理1对任意向量 $x,\hat{x}\in {ℝ}^n$，令 $h=\hat{x}-x$。假设 ${\Vert \hat{x}\Vert }_{\alpha ,1-2}\le {\Vert x\Vert }_{\alpha ,1-2}$，则

${\Vert h_{{\overline{T_0}}^c}\Vert }_1\le {\Vert h_{\overline{T_0}}\Vert }_1+2{\Vert x_{{\overline{T_0}}^c}\Vert }_1+\alpha {\Vert h\Vert }_2,$ (8)

${\Vert h_{{\overline{T_0}}^c}\Vert }_1-\alpha {\Vert h_{{\overline{T_0}}^c}\Vert }_2\le {\Vert h_{\overline{T_0}}\Vert }_1+2{\Vert x_{{\overline{T_0}}^c}\Vert }_1+\alpha {\Vert h_{\overline{T_0}}\Vert }_2,$ (9)

特别地，当x是s-稀疏时，得到

${\Vert h_{{\overline{T_0}}^c}\Vert }_1\le {\Vert h_{\overline{T_0}}\Vert }_1+\alpha {\Vert h\Vert }_2,$ (10)

${\Vert h_{{\overline{T_0}}^c}\Vert }_1-\alpha {\Vert h_{{\overline{T_0}}^c}\Vert }_2\le {\Vert h_{\overline{T_0}}\Vert }_1+\alpha {\Vert h_{\overline{T_0}}\Vert }_2,$ (11)

引理2是 ${\Vert x\Vert }_1-\alpha {\Vert x\Vert }_2$ $\left(0\le \alpha \le 1\right)$ 的基本性质。

引理2 [23] 对任意 $x\in {ℝ}^n$，以下陈述成立：

1) 对 $0\le \alpha \le 1$，令 $T=\mathrm{supp}\left(x\right)$ 且 ${\Vert x\Vert }_0=s$，则

$\left(s-\alpha \sqrt{s}\right)\underset{j\in T}{\min }\left|x_j\right|\le {\Vert x\Vert }_1-\alpha {\Vert x\Vert }_2\le \left(\sqrt{s}-\alpha \right){\Vert x\Vert }_2.$ (12)

2) 令 $S,S_1,S_2\subseteq \left[n\right]$ 满足 $S=S_1\cup S_2$ 和 $S_1\cap S_2=\varnothing$，则

${\Vert x_{S_1}\Vert }_1-\alpha {\Vert x_{S_1}\Vert }_2+{\Vert x_{S_2}\Vert }_1-\alpha {\Vert x_{S_2}\Vert }_2\le {\Vert x_S\Vert }_1-\alpha {\Vert x_S\Vert }_2.$ (13)

在信号的部分支集已知的假设下，文献( [17]，引理3)、文献( [16]，引理2.6)容易修正为如下引理3和引理4。

引理3 假设 ${\Vert \hat{x}\Vert }_{\alpha ,1-2}\le {\Vert x\Vert }_{\alpha ,1-2}$。令 $h=\hat{x}-x$， $T_{\overline{01}}=T\cup T_0\cup T_1$，其中T是信号x的已知支集( $\left|T\right|=r$ )， $T_0$ 是h中 $s\in {\mathbb{Z}}_{+}$ 个最大绝对值项组成的指标集， $T_1$ 是 $h_{T_0{}^c}$ 中 $k\in {\mathbb{Z}}_{+}$ 个最大绝对值项组成的指标集。那么

${\Vert h_{{\overline{T_{01}}}^c}\Vert }_2\le \frac{1}{2\sqrt{t}}\left({\Vert h_{\overline{T_{01}}}\Vert }_2+\frac{2{\Vert x_{{\overline{T_0}}^c}\Vert }_1+\alpha {\Vert h\Vert }_2}{\sqrt{r+s}}\right),$ (14)

且

${\Vert h\Vert }_2\le \left(1+\frac{1}{2\sqrt{t}}\right){\Vert h_{\overline{T_{01}}}\Vert }_2+\frac{{\Vert x_{{\overline{T_0}}^c}\Vert }_1}{\sqrt{t\left(r+s\right)}}+\frac{\alpha {\Vert h\Vert }_2}{2\sqrt{t\left(r+s\right)}},$ (15)

其中 $t=\frac{k}{r+s}$ 且 $T_{\overline{01}}{}^c\subseteq \left[n\right]$ 是 $T_{\overline{01}}$ 的补集。

引理4假设 ${\Vert \hat{x}\Vert }_{\alpha ,1-2}\le {\Vert x\Vert }_{\alpha ,1-2}$。令 $h=\hat{x}-x$， $T_{\overline{01}}=T\cup T_0\cup T_1$，其中T是信号x的已知支集( $\left|T\right|=r$ )， $T_0$ 是h中 $s\in {\mathbb{Z}}_{+}$ 个最大绝对值项组成的指标集， $T_1$ 是 $h_{T_0{}^c}$ 中 $k\in {\mathbb{Z}}_{+}$ 个最大绝对值项组成的指标集，矩阵 ${\rm A}$ 满足 $r+s+k$ 阶 $\left({\mathcal{l}}_2,{\mathcal{l}}_1\right)$ -RIP条件。那么

${\Vert {\rm A}h\Vert }_1\ge {\rho }_k{\Vert h_{\overline{T_{01}}}\Vert }_2-\frac{2\left(1+{\delta }_k^{ub}\right){\Vert x_{{\overline{T_0}}^c}\Vert }_1}{\sqrt{k}-\alpha },$ (16)

其中

${\rho }_k=1-{\delta }_{r+s+k}^{lb}-\frac{1+{\delta }_k^{ub}}{a\left(r+s,k;\alpha \right)}$

且 $a\left(r+s,k;\alpha \right)=\frac{\sqrt{k}-\alpha }{\sqrt{r+s}+\alpha }$。

引理5 [14] 描述了基于 ${\Vert x\Vert }_1-{\Vert x\Vert }_2$ 的任意稀疏向量的一个凸组合。

引理5 令向量 $v\in {ℝ}^n$ 满足 ${\Vert v\Vert }_{\infty }\le \theta$，其中 $\theta$ 是一个正常数。假设 ${\Vert v\Vert }_{1-2}\le \left(s-\sqrt{s}\right)\theta$ (s是一个正整数且 $s\le \left|\mathrm{supp}\left(v\right)\right|$ )。那么v能被表达为s-稀疏向量 $u^{\left(i\right)}$ 的一个凸组合，即

$v={\displaystyle \underset{i=1}{\overset{N}{\sum }}{\lambda }_i{u}^{\left(i\right)}},$

其中N是一个正整数，

$0<{\lambda }_i\le 1,{\displaystyle \underset{i=1}{\overset{N}{\sum }}{\lambda }_i}=1,$ (17)

$\mathrm{supp}\left(u^{\left(i\right)}\right)\subseteq \mathrm{supp}\left(v\right),{\Vert u^{\left(i\right)}\Vert }_0\le s,{\Vert u^{\left(i\right)}\Vert }_{\infty }\le \left(1+\frac{\sqrt{2}}{2}\right)\theta ,$

且

${\displaystyle \underset{i=1}{\overset{N}{\sum }}{\lambda }_i{\Vert u^{\left(i\right)}\Vert }_2^2}\le \left({\left(1+\frac{\sqrt{2}}{2}\right)}^2\left(s-\sqrt{s}\right)+1\right){\theta }^2.$ (18)

在信号的部分支集已知的假设下，文献( [17]，引理6)很容易修正为下面的引理6。

引理6假设 ${\Vert \hat{x}\Vert }_{\alpha ,1-2}\le {\Vert x\Vert }_{\alpha ,1-2}$。令 $h=\hat{x}-x$ 且

$\text{χ}=\frac{\sqrt{r+s}+\alpha }{\sqrt{r+s}-1}\frac{{\Vert h_{\overline{T_0}}\Vert }_2}{\sqrt{r+s}}+\frac{2}{r+s-\sqrt{r+s}}{\Vert x_{{\overline{T_0}}^c}\Vert }_1,$ (19)

其中 $s\ge 2$ 是一个正整数。并且定义两个指标集

${\text{W}}_1=\left\{i:\left|h_{{\overline{T_0}}^c}\left(i\right)\right|>\frac{\text{χ}}{t-1}\right\},$ (20)

和

${\text{W}}_2=\left\{i:\left|h_{{\overline{T_0}}^c}\left(i\right)\right|\le \frac{\text{χ}}{t-1}\right\},$ (21)

其中 $t=2$ 或 $t\ge 3$。然后 $h_{{\text{W}}_2}$ 能被表达为 $\left(t\left(r+s\right)-\left(r+s\right)-\left|{\text{W}}_1\right|\right)$ -稀疏向量 $u^{\left(i\right)}$ 的一个凸组合，即

$h_{{\text{W}}_2}={\displaystyle \underset{i=1}{\overset{N}{\sum }}{\lambda }_i{u}^{\left(i\right)}},$ (22)

其中N是一个正整数且对所有i， ${\lambda }_i$ 满足式(17)。且

${\displaystyle \underset{i=1}{\overset{N}{\sum }}{\lambda }_i{\Vert u^{\left(i\right)}\Vert }_2^2}\le \frac{{\left(1+\frac{\sqrt{2}}{2}\right)}^2\left(t\left(r+s\right)-\left(r+s\right)-\sqrt{t\left(r+s\right)-\left(r+s\right)}\right)+1}{{\left(t-1\right)}^2}{\text{χ}}^2.$ (23)

3. 主要结论

信号会被各种噪声污染，常见的噪声类型有：高斯噪声、脉冲噪声、均匀噪声等。人们在恢复信号时，需要消除噪声所带来的影响。 ${\Vert {{\rm A}}^{{\rm T}}e\Vert }_{\infty }$ 衡量噪声向量 $e={\rm A}x-b$ 和 ${\rm A}$ 的列之间的相关性，其中e可以是高斯、脉冲和均匀噪声。 ${\mathcal{l}}_2$ 范数 ${\Vert {\rm A}x-b\Vert }_2$ 仅对处理高斯噪声有效， ${\mathcal{l}}_1$ 范数 ${\Vert {\rm A}x-b\Vert }_1$ 仅对处理脉冲噪声有效， ${\mathcal{l}}_{\infty }$ 范数 ${\Vert {\rm A}x-b\Vert }_{\infty }$ 仅对处理均匀噪声有效。假设信号x不是稀疏向量，现考虑以下三种噪声情形：

① $B^{{\mathcal{l}}_2}\left(\epsilon \right)=\left\{e:{\Vert e\Vert }_2\le {\epsilon }_1\right\};$ (24)

② $B^{{\mathcal{l}}_1}\left(\epsilon \right)=\left\{e:{\Vert e\Vert }_1\le {\epsilon }_1\right\};$ (25)

③ $B^{DS}\left(\epsilon \right)=\left\{e:{\Vert {{\rm A}}^{{\rm T}}e\Vert }_{\infty }\le {\epsilon }_1\right\}.$ (26)

定理1 考虑 $y={\rm A}x+e$，其中 ${\Vert e\Vert }_2\le {\epsilon }_2$ ( ${\epsilon }_2\le {\epsilon }_1$ )。假设信号x的部分已知支撑是T ( $\left|T\right|=r$ )，对于 $t\ge 3$ 、 $s\ge 2$，若矩阵 ${\rm A}$ 满足：

${\delta }_{t\left(r+s\right)}<\frac{1}{\sqrt{1+\frac{{\left(\sqrt{r+s}+\alpha \right)}^2\left({\left(1+\frac{\sqrt{2}}{2}\right)}^2\left(t\left(r+s\right)-\left(r+s\right)-\sqrt{t\left(r+s\right)-\left(r+s\right)}\right)+1\right)}{\left(r+s\right){\left(t-1\right)}^2{\left(\sqrt{r+s}-1\right)}^2}}},$ (27)

则式(4)的解 ${\hat{x}}^{{\mathcal{l}}_2}$ 满足：

$\begin{array}{c}{\Vert {\hat{x}}^{{\mathcal{l}}_2}-x\Vert }_2\le \left(1+\sqrt{\frac{{\alpha }^2}{4\left(r+s\right)}+\frac{\alpha +\sqrt{r+s}}{\sqrt{r+s}}}+\frac{\alpha +\sqrt{2}}{2\sqrt{r+s}}\right)\frac{\left(1-\mu \right)\mu \sqrt{1+{\delta }_{t\left(r+s\right)}}}{\mu -{\mu }^2-{\left(\mu -1\right)}^2{\delta }_{t\left(r+s\right)}}\left({\epsilon }_1+{\epsilon }_2\right)\\ +(\left(\sqrt{r+s}+\sqrt{\frac{{\alpha }^2}{4}+\alpha \sqrt{r+s}+\left(r+s\right)}+\frac{\alpha +\sqrt{2}}{2}\right)(\frac{2{\delta }_{t\left(r+s\right)}\left(1-2\mu \right)}{\left(\mu -{\mu }^2-{\left(\mu -1\right)}^2{\delta }_{t\left(r+s\right)}\right)\left(\sqrt{r+s}+\alpha \right)}\\ +\sqrt{\frac{2\left(1-2\mu \right){\delta }_{t\left(r+s\right)}}{\left(\mu -{\mu }^2-{\left(\mu -1\right)}^2{\delta }_{t\left(r+s\right)}\right){\left(\sqrt{r+s}+\alpha \right)}^2}})+\frac{\sqrt{2\left(r+s\right)}}{2})\frac{{\Vert x_{{\overline{T_0}}^c}\Vert }_1}{\sqrt{r+s}},\end{array}$ (28)

其中 $\mu =\frac{1}{\sqrt{1+\frac{{\left(\sqrt{r+s}+\alpha \right)}^2\left({\left(1+\frac{\sqrt{2}}{2}\right)}^2\left(t\left(r+s\right)-\left(r+s\right)-\sqrt{t\left(r+s\right)-\left(r+s\right)}\right)+1\right)}{\left(r+s\right){\left(t-1\right)}^2{\left(\sqrt{r+s}-1\right)}^2}}+1}$。

证明证明受文献 [14] 启发。定义 $h={\hat{x}}^{{\mathcal{l}}_2}-x$，其中 ${\hat{x}}^{{\mathcal{l}}_2}$ 是满足式(24)的式(4)的最小值，这意味着 ${\Vert y-{\rm A}{\hat{x}}^{{\mathcal{l}}_2}\Vert }_2\le {\epsilon }_1$，又 ${\Vert y-{\rm A}x\Vert }_2\le {\epsilon }_2$，得到

${\Vert {\rm A}h\Vert }_2\le {\Vert {\rm A}{\hat{x}}^{{\mathcal{l}}_2}-y\Vert }_2+{\Vert y-{\rm A}x\Vert }_2\le {\epsilon }_1+{\epsilon }_2.$ (29)

利用 ${\Vert {\hat{x}}^{{\mathcal{l}}_2}\Vert }_{\alpha ,1-2}\le {\Vert x\Vert }_{\alpha ,1-2}$ 和引理5，得到

$h_{w_2}={\displaystyle \underset{i=1}{\overset{N}{\sum }}{\lambda }_i{u}^{\left(i\right)}},$ (30)

和

${\displaystyle \underset{i=1}{\overset{N}{\sum }}{\lambda }_i{\Vert u^{\left(i\right)}\Vert }_2^2}\le \frac{{\left(1+\frac{\sqrt{2}}{2}\right)}^2\left(t\left(r+s\right)-\left(r+s\right)-\sqrt{t\left(r+s\right)-\left(r+s\right)}\right)+1}{{\left(t-1\right)}^2}{\text{χ}}^2,$ (31)

其中 $0<{\lambda }_i\le 1$， ${\displaystyle \underset{i=1}{\overset{N}{\sum }}{\lambda }_i}=1$，对所有i， $u^{\left(i\right)}$ 是( $t\left(r+s\right)-\left(r+s\right)-\left|{\text{W}}_1\right|$ )-稀疏向量且 ${\text{W}}_{\text{1}}{\text{,W}}_2,\text{χ}$ 分别由式(20)，式(21)，式(19)定义。由式(19)中 $\text{χ}$ 的定义，可以推出

$\begin{array}{c}{\displaystyle \underset{i=1}{\overset{N}{\sum }}{\lambda }_i{\Vert u^{\left(i\right)}\Vert }_2^2}\le \frac{{\left(1+\frac{\sqrt{2}}{2}\right)}^2\left(t\left(r+s\right)-\left(r+s\right)-\sqrt{t\left(r+s\right)-\left(r+s\right)}\right)+1}{{\left(t-1\right)}^2}\\ \times \left(\frac{{\left(\sqrt{r+s}+\alpha \right)}^2}{\left(r+s\right){\left(\sqrt{r+s}-1\right)}^2}{\Vert h_{\overline{T_0}}\Vert }_2^2+\frac{4\left(\sqrt{r+s}+\alpha \right)}{\left(r+s\right){\left(\sqrt{r+s}-1\right)}^2}{\Vert h_{\overline{T_0}}\Vert }_2{\Vert x_{{\overline{T_0}}^c}\Vert }_1+\frac{4}{\left(r+s\right){\left(\sqrt{r+s}-1\right)}^2}{\Vert x_{{\overline{T_0}}^c}\Vert }_1^2\right)\\ =\frac{1-2\mu }{{\mu }^2}\left({\Vert h_{\overline{T_0}}\Vert }_2^2+\frac{4{\Vert h_{\overline{T_0}}\Vert }_2{\Vert x_{{\overline{T_0}}^c}\Vert }_1}{\sqrt{r+s}+\alpha }+\frac{4{\Vert x_{{\overline{T_0}}^c}\Vert }_1^2}{{\left(\sqrt{r+s}+\alpha \right)}^2}\right),\end{array}$ (32)

其中 $\mu =\frac{1}{\sqrt{1+\frac{{\left(\sqrt{r+s}+\alpha \right)}^2\left({\left(1+\frac{\sqrt{2}}{2}\right)}^2\left(t\left(r+s\right)-\left(r+s\right)-\sqrt{t\left(r+s\right)-\left(r+s\right)}\right)+1\right)}{\left(r+s\right){\left(t-1\right)}^2{\left(\sqrt{r+s}-1\right)}^2}}+1}.$ (33)

接下来，由下式来估计 ${\Vert h_{\overline{T_0}}+h_{{\text{W}}_1}\Vert }_2$ 的一个上界，

${\displaystyle \underset{i=1}{\overset{N}{\sum }}\frac{{\lambda }_i}{4}}{\Vert {\rm A}\left(h_{\overline{T_0}}+h_{{\text{W}}_1}+\mu u^{\left(i\right)}\right)\Vert }_2^2={\displaystyle \underset{i=1}{\overset{N}{\sum }}{\lambda }_i{\Vert {\rm A}\left(\left(\frac{1}{2}-\mu \right)\left(h_{\overline{T_0}}+h_{{\text{W}}_1}\right)-\frac{1}{2}\mu u^{\left(i\right)}+\mu h\right)\Vert }_2^2}.$ (34)

由于 $h_{\overline{T_0}}+h_{{\text{W}}_1}+\mu u^{\left(i\right)}$ 是 $t\left(r+s\right)$ -稀疏， ${\displaystyle \underset{i=1}{\overset{N}{\sum }}{\lambda }_i}=1$， $\mathrm{supp}\left(u^{\left(i\right)}\right)\subseteq \mathrm{supp}\left(h_{{\text{W}}_2}\right)\subseteq \mathrm{supp}\left(h_{\overline{T_0}}\right)$ 且 ${\text{W}}_{\text{1}}\cap {\text{W}}_2=\varnothing$，不难检验

$\begin{array}{c}{\displaystyle \underset{i=1}{\overset{N}{\sum }}\frac{{\lambda }_i}{4}}{\Vert {\rm A}\left(h_{\overline{T_0}}+h_{{\text{W}}_1}+\mu u^{\left(i\right)}\right)\Vert }_2^2\ge \left(1-{\delta }_{t\left(r+s\right)}\right){\displaystyle \underset{i=1}{\overset{N}{\sum }}\frac{{\lambda }_i}{4}}{\Vert h_{\overline{T_0}}+h_{{\text{W}}_1}+\mu u^{\left(i\right)}\Vert }_2^2\\ =\frac{1-{\delta }_{t\left(r+s\right)}}{4}\left({\Vert h_{\overline{T_0}}+h_{{\text{W}}_1}\Vert }_2^2+{\mu }^2{\displaystyle \underset{i=1}{\overset{N}{\sum }}{\lambda }_i{\Vert u^{\left(i\right)}\Vert }_2^2}\right),\end{array}$ (35)

从文献( [17]，引理6)的证明中可以得到 $\left|{\text{W}}_1\right|<\left(r+s\right)\left(t-1\right)$，因此 $\left|\mathrm{supp}\left(h_{\overline{T_0}}+h_{{\text{W}}_1}\right)\right|=\left(r+s\right)\text{+}\left|{\text{W}}_1\right|$，又 ${\displaystyle \underset{i=1}{\overset{N}{\sum }}{\lambda }_i{u}^{\left(i\right)}}=h_{{\text{W}}_2}=h-h_{\overline{T_0}}-h_{{\text{W}}_1}$， ${\displaystyle \underset{i=1}{\overset{N}{\sum }}{\lambda }_i}=1$， $\mathrm{supp}\left(u^{\left(i\right)}\right)\subseteq \mathrm{supp}\left(h_{{\text{W}}_2}\right)\subseteq \mathrm{supp}\left(h_{\overline{T_0}}\right)$， ${\text{W}}_{\text{1}}\cap {\text{W}}_2=\varnothing$，矩阵 ${\rm A}$ 满足 $t\left(r+s\right)$ 阶限制等距性， $\left(\frac{1}{2}-\mu \right)\left(h_{\overline{T_0}}+h_{{\text{W}}_1}\right)-\frac{1}{2}\mu u^{\left(i\right)}$ 是 $t\left(r+s\right)$ -稀疏。综上，推导出

$\begin{array}{l}{\displaystyle \underset{i=1}{\overset{N}{\sum }}{\lambda }_i{\Vert {\rm A}\left(\left(\frac{1}{2}-\mu \right)\left(h_{\overline{T_0}}+h_{{\text{W}}_1}\right)-\frac{1}{2}\mu u^{\left(i\right)}+\mu h\right)\Vert }_2^2}\\ ={\displaystyle \underset{i=1}{\overset{N}{\sum }}{\lambda }_i{\Vert {\rm A}\left(\left(\frac{1}{2}-\mu \right)\left(h_{\overline{T_0}}+h_{{\text{W}}_1}\right)-\frac{1}{2}\mu u^{\left(i\right)}\right)\Vert }_2^2}+2{\displaystyle \underset{i=1}{\overset{N}{\sum }}{\lambda }_i\langle {\rm A}\left(\left(\frac{1}{2}-\mu \right)\left(h_{\overline{T_0}}+h_{{\text{W}}_1}\right)-\frac{1}{2}\mu u^{\left(i\right)}\right),\mu {\rm A}h\rangle +{\mu }^2}{\Vert {\rm A}h\Vert }_2^2\\ ={\displaystyle \underset{i=1}{\overset{N}{\sum }}{\lambda }_i{\Vert {\rm A}\left(\left(\frac{1}{2}-\mu \right)\left(h_{\overline{T_0}}+h_{{\text{W}}_1}\right)-\frac{1}{2}\mu u^{\left(i\right)}\right)\Vert }_2^2}+\left(1-\mu \right)\mu \langle {\rm A}\left(h_{\overline{T_0}}+h_{{\text{W}}_1}\right),{\rm A}h\rangle \\ \le \left(1+{\delta }_{t\left(r+s\right)}\right){\displaystyle \underset{i=1}{\overset{N}{\sum }}{\lambda }_i{\Vert \left(\frac{1}{2}-\mu \right)\left(h_{\overline{T_0}}+h_{{\text{W}}_1}\right)-\frac{1}{2}\mu u^{\left(i\right)}\Vert }_2^2}+\left(1-\mu \right)\mu {\Vert {\rm A}\left(h_{\overline{T_0}}+h_{{\text{W}}_1}\right)\Vert }_2{\Vert {\rm A}h\Vert }_2\\ \le \left(1+{\delta }_{t\left(r+s\right)}\right)\left({\left(\frac{1}{2}-\mu \right)}^2{\Vert h_{\overline{T_0}}+h_{{\text{W}}_1}\Vert }_2^2+\frac{{\mu }^2}{4}{\displaystyle \underset{i=1}{\overset{N}{\sum }}{\lambda }_i{\Vert u^{\left(i\right)}\Vert }_2^2}\right)+\left(1-\mu \right)\mu \sqrt{1+{\delta }_{t\left(r+s\right)}}{\Vert h_{\overline{T_0}}+h_{{\text{W}}_1}\Vert }_2\left({\epsilon }_1+{\epsilon }_2\right).\end{array}$ (36)

应用式(34)，式(35)和式(36)，得到

$\begin{array}{l}\left(\left(1+{\delta }_{t\left(r+s\right)}\right){\left(\frac{1}{2}-\mu \right)}^2-\frac{1-{\delta }_{t\left(r+s\right)}}{4}\right){\Vert h_{\overline{T_0}}+h_{{\text{W}}_1}\Vert }_2^2+\frac{{\mu }^2{\delta }_{t\left(r+s\right)}}{2}{\displaystyle \underset{i=1}{\overset{N}{\sum }}{\lambda }_i{\Vert u^{\left(i\right)}\Vert }_2^2}\\ +\left(1-\mu \right)\mu \sqrt{1+{\delta }_{t\left(r+s\right)}}{\Vert h_{\overline{T_0}}+h_{{\text{W}}_1}\Vert }_2\left({\epsilon }_1+{\epsilon }_2\right)\ge 0.\end{array}$

将式(32)代入上式，且 ${\Vert h_{\overline{T_0}}\Vert }_2\le {\Vert h_{\overline{T_0}}+h_{{\text{W}}_1}\Vert }_2$，可以推导出

$\begin{array}{l}\left({\mu }^2-\mu +{\left(\mu -1\right)}^2{\delta }_{t\left(r+s\right)}\right){\Vert h_{\overline{T_0}}+h_{{\text{W}}_1}\Vert }_2^2+\left(\left(1-\mu \right)\mu \sqrt{1+{\delta }_{t\left(r+s\right)}}\left({\epsilon }_1+{\epsilon }_2\right)+\frac{2{\delta }_{t\left(r+s\right)}\left(1-2\mu \right)}{\sqrt{r+s}+\alpha }{\Vert x_{{\overline{T_0}}^c}\Vert }_1\right){\Vert h_{\overline{T_0}}+h_{{\text{W}}_1}\Vert }_2\\ +\frac{2\left(1-2\mu \right){\delta }_{t\left(r+s\right)}}{{\left(\sqrt{r+s}+\alpha \right)}^2}{\Vert x_{{\overline{T_0}}^c}\Vert }_1^2\ge 0.\end{array}$ (37)

要使上式中的 ${\Vert h_{\overline{T_0}}+h_{{\text{W}}_1}\Vert }_2$ 有解，只需要保证 ${\mu }^2-\mu +{\left(\mu -1\right)}^2{\delta }_{t\left(r+s\right)}<0$ 成立，即

${\delta }_{t\left(r+s\right)}<\frac{\mu }{1-\mu }=\frac{1}{\sqrt{1+\frac{{\left(\sqrt{r+s}+\alpha \right)}^2\left({\left(1+\frac{\sqrt{2}}{2}\right)}^2\left(t\left(r+s\right)-\left(r+s\right)-\sqrt{t\left(r+s\right)-\left(r+s\right)}\right)+1\right)}{\left(r+s\right){\left(t-1\right)}^2{\left(\sqrt{r+s}-1\right)}^2}}}.$

考虑 $z\le \frac{b+\sqrt{b^2+4ac}}{2a}\le \frac{b+\sqrt{ac}}{a}$ 满足二阶不等式 $a{z}^2-bz-c\le 0$，其中 $a,b,c>0$。现求解二阶不等式(37)，得到

$\begin{array}{l}{\Vert h_{\overline{T_0}}+h_{{\text{W}}_1}\Vert }_2\\ \le \frac{\left(1-\mu \right)\mu \sqrt{1+{\delta }_{t\left(r+s\right)}}\left({\epsilon }_1+{\epsilon }_2\right)+\left(\frac{2{\delta }_{t\left(r+s\right)}\left(1-2\mu \right)}{\sqrt{r+s}+\alpha }+\sqrt{\frac{2\left(1-2\mu \right){\delta }_{t\left(r+s\right)}}{{\left(\sqrt{r+s}+\alpha \right)}^2}\left(\mu -{\mu }^2-{\left(\mu -1\right)}^2{\delta }_{t\left(r+s\right)}\right)}\right){\Vert x_{{\overline{T_0}}^c}\Vert }_1}{\mu -{\mu }^2-{\left(\mu -1\right)}^2{\delta }_{t\left(r+s\right)}}.\end{array}$ (38)

由式(9)可以推导出 ${\Vert h_{{\overline{T_0}}^c}\Vert }_1-\alpha {\Vert h_{{\overline{T_0}}^c}\Vert }_2\le {\Vert h_{\overline{T_0}}\Vert }_1+2{\Vert x_{{\overline{T_0}}^c}\Vert }_1+\alpha {\Vert h_{\overline{T_0}}\Vert }_2\le \left(\sqrt{r+s}+\alpha \right){\Vert h_{\overline{T_0}}\Vert }_2+2{\Vert x_{{\overline{T_0}}^c}\Vert }_1$，且 ${\Vert h_{{\overline{T_0}}^c}\Vert }_{\infty }\le \frac{{\Vert h_{\overline{T_0}}\Vert }_1}{s+r}\le \frac{{\Vert h_{\overline{T_0}}\Vert }_2}{\sqrt{r+s}}$。因此，可以得到

$\begin{array}{c}{\Vert h_{{\overline{T_0}}^c}\Vert }_2^2\le {\Vert h_{{\overline{T_0}}^c}\Vert }_1{\Vert h_{{\overline{T_0}}^c}\Vert }_{\infty }\\ \le \left(\alpha {\Vert h_{{\overline{T_0}}^c}\Vert }_2+\left(\sqrt{r+s}+\alpha \right){\Vert h_{\overline{T_0}}\Vert }_2+2{\Vert x_{{\overline{T_0}}^c}\Vert }_1\right)\frac{{\Vert h_{\overline{T_0}}\Vert }_2}{\sqrt{r+s}}\\ =\frac{\alpha }{\sqrt{r+s}}{\Vert h_{\overline{T_0}}\Vert }_2{\Vert h_{{\overline{T_0}}^c}\Vert }_2+\frac{\sqrt{r+s}+\alpha }{\sqrt{r+s}}{\Vert h_{\overline{T_0}}\Vert }_2^2+\frac{2{\Vert x_{{\overline{T_0}}^c}\Vert }_1{\Vert h_{\overline{T_0}}\Vert }_2}{\sqrt{r+s}}.\end{array}$

进一步，

${\left({\Vert h_{{\overline{T_0}}^c}\Vert }_2-\frac{\alpha {\Vert h_{\overline{T_0}}\Vert }_2}{2\sqrt{r+s}}\right)}^2\le \left(\frac{{\alpha }^2}{4\left(r+s\right)}+\frac{\alpha +\sqrt{r+s}}{\sqrt{r+s}}\right){\Vert h_{\overline{T_0}}\Vert }_2^2+\frac{2{\Vert x_{{\overline{T_0}}^c}\Vert }_1{\Vert h_{\overline{T_0}}\Vert }_2}{\sqrt{r+s}}.$

由 $2\left|a\right|\left|b\right|\le \frac{{\left(\left|a\right|+\left|b\right|\right)}^2}{2}$，可以得到

$\begin{array}{c}{\Vert h_{{\overline{T_0}}^c}\Vert }_2\le \left(\sqrt{\frac{{\alpha }^2}{4\left(r+s\right)}+\frac{\alpha +\sqrt{r+s}}{\sqrt{r+s}}}+\frac{\alpha }{2\sqrt{r+s}}\right){\Vert h_{\overline{T_0}}\Vert }_2+\sqrt{\frac{2{\Vert x_{{\overline{T_0}}^c}\Vert }_1{\Vert h_{\overline{T_0}}\Vert }_2}{\sqrt{r+s}}}\\ \le \left(\sqrt{\frac{{\alpha }^2}{4\left(r+s\right)}+\frac{\alpha +\sqrt{r+s}}{\sqrt{r+s}}}+\frac{\alpha +\sqrt{2}}{2\sqrt{r+s}}\right){\Vert h_{\overline{T_0}}\Vert }_2+\frac{\sqrt{2}}{2}{\Vert x_{{\overline{T_0}}^c}\Vert }_1.\end{array}$ (39)

综上，利用 ${\Vert h\Vert }_2=\sqrt{{\Vert h_{\overline{T_0}}\Vert }_2^2+{\Vert h_{{\overline{T_0}}^c}\Vert }_2^2}\le {\Vert h_{\overline{T_0}}\Vert }_2+{\Vert h_{{\overline{T_0}}^c}\Vert }_2$ 和 ${\Vert h_{\overline{T_0}}\Vert }_2\le {\Vert h_{\overline{T_0}}+h_{{\text{W}}_1}\Vert }_2$，得到

$\begin{array}{c}{\Vert h\Vert }_2\le \left(1+\sqrt{\frac{{\alpha }^2}{4\left(r+s\right)}+\frac{\alpha +\sqrt{r+s}}{\sqrt{r+s}}}+\frac{\alpha +\sqrt{2}}{2\sqrt{r+s}}\right){\Vert h_{\overline{T_0}}\Vert }_2+\frac{\sqrt{2}}{2}{\Vert x_{{\overline{T_0}}^c}\Vert }_1\\ \le \left(1+\sqrt{\frac{{\alpha }^2}{4\left(r+s\right)}+\frac{\alpha +\sqrt{r+s}}{\sqrt{r+s}}}+\frac{\alpha +\sqrt{2}}{2\sqrt{r+s}}\right)\frac{\left(1-\mu \right)\mu \sqrt{1+{\delta }_{t\left(r+s\right)}}}{\mu -{\mu }^2-{\left(\mu -1\right)}^2{\delta }_{t\left(r+s\right)}}\left({\epsilon }_1+{\epsilon }_2\right)\\ +(\left(\sqrt{r+s}+\sqrt{\frac{{\alpha }^2}{4}+\alpha \sqrt{r+s}+\left(r+s\right)}+\frac{\alpha +\sqrt{2}}{2}\right)(\frac{2{\delta }_{t\left(r+s\right)}\left(1-2\mu \right)}{\left(\mu -{\mu }^2-{\left(\mu -1\right)}^2{\delta }_{t\left(r+s\right)}\right)\left(\sqrt{r+s}+\alpha \right)}\\ +\sqrt{\frac{2\left(1-2\mu \right){\delta }_{t\left(r+s\right)}}{\left(\mu -{\mu }^2-{\left(\mu -1\right)}^2{\delta }_{t\left(r+s\right)}\right){\left(\sqrt{r+s}+\alpha \right)}^2}})+\frac{\sqrt{2\left(r+s\right)}}{2})\frac{{\Vert x_{{\overline{T_0}}^c}\Vert }_1}{\sqrt{r+s}},\end{array}$

这就完成了证明。

注1 若x是精确 $r+s$ -稀疏，即 $x_{{\overline{T_0}}^c}=0$，由定理1得

${\Vert {\hat{x}}^{{\mathcal{l}}_2}-x\Vert }_2\le \left(1+\sqrt{\frac{{\alpha }^2}{4\left(r+s\right)}+\frac{\alpha +\sqrt{r+s}}{\sqrt{r+s}}}+\frac{\alpha +\sqrt{2}}{2\sqrt{r+s}}\right)\frac{\left(1-\mu \right)\mu \sqrt{1+{\delta }_{t\left(r+s\right)}}}{\mu -{\mu }^2-{\left(\mu -1\right)}^2{\delta }_{t\left(r+s\right)}}\left({\epsilon }_1+{\epsilon }_2\right),$

特别地，在无噪声情形下， ${\hat{x}}^{{\mathcal{l}}_2}=x$，其中 ${\hat{x}}^{{\mathcal{l}}_2}$ 是满足 $B=\left\{0\right\}$ 的式(4)的最小值。

定理2 考虑 $y={\rm A}x+e$，其中 ${\Vert e\Vert }_1\le {\epsilon }_2$ ( ${\epsilon }_2\le {\epsilon }_1$ )。假设信号x的部分已知支撑是T ( $\left|T\right|=r$ )，对于 $t\ge 3$ 、 $s\ge 2$，若矩阵 ${\rm A}$ 满足：

${\delta }_{t\left(r+s\right)}^{ub}+a\left(r+s,k;\alpha \right){\delta }_{r+s+k}^{lb}<a\left(r+s,k;\alpha \right)-1$ (40)

则式(4)的解 ${\hat{x}}^{{\mathcal{l}}_1}$ 满足：

$\begin{array}{c}{\Vert x-\hat{x}\Vert }_2\le \frac{\left(2\sqrt{t}+1\right)\sqrt{r+s}}{2\sqrt{t\left(r+s\right)}-\alpha }\left(\frac{1}{{\rho }_{t\left(r+s\right)}}\left({\epsilon }_1+{\epsilon }_2\right)+\frac{2\left(1+{\delta }_{t\left(r+s\right)}^{ub}\right){\Vert x_{{\overline{T_0}}^c}\Vert }_1}{{\rho }_{t\left(r+s\right)}\left(\sqrt{t\left(r+s\right)}-\alpha \right)}\right)+\frac{2}{2\sqrt{t\left(r+s\right)}-\alpha }{\Vert x_{{\overline{T_0}}^c}\Vert }_1\\ =\frac{2}{2\sqrt{k}-\alpha }\left(1+\frac{\left(2\sqrt{t}+1\right)\left(1+{\delta }_{t\left(r+s\right)}^{ub}\right)\sqrt{r+s}}{{\rho }_{t\left(r+s\right)}\left(\sqrt{k}-\alpha \right)}\right){\Vert x_{{\overline{T_0}}^c}\Vert }_1+\frac{\left(2\sqrt{t}+1\right)\sqrt{r+s}}{\left(2\sqrt{k}-\alpha \right){\rho }_{t\left(r+s\right)}}\left({\epsilon }_1+{\epsilon }_2\right).\end{array}$ (41)

其中 ${\rho }_{t\left(r+s\right)}=1-{\delta }_{r+s+k}^{lb}-\frac{1+{\delta }_{t\left(r+s\right)}^{ub}}{a\left(r+s,k;\alpha \right)}$， $a\left(r+s,k;\alpha \right)=\frac{\sqrt{k}-\alpha }{\sqrt{r+s}+\alpha }$。

证明 令 $h={\hat{x}}^{{\mathcal{l}}_1}-x$。由于 ${\hat{x}}^{{\mathcal{l}}_1}$ 是满足式(25)的式(4)的最小值，则 ${\Vert b-{\rm A}{\hat{x}}^{{\mathcal{l}}_1}\Vert }_1\le {\epsilon }_1$ 且 ${\Vert {\hat{x}}^{{\mathcal{l}}_1}\Vert }_{\alpha ,1-2}\le {\Vert x\Vert }_{\alpha ,1-2}$。通过引理1中的式(8)，有

${\Vert h_{{\overline{T_0}}^c}\Vert }_1\le {\Vert h_{\overline{T_0}}\Vert }_1+2{\Vert x_{{\overline{T_0}}^c}\Vert }_1+\alpha {\Vert h\Vert }_2.$ (42)

由 ${\Vert e\Vert }_1={\Vert b-{\rm A}x\Vert }_1\le {\epsilon }_2$ 和 ${\Vert b-{\rm A}{\hat{x}}^{{\mathcal{l}}_1}\Vert }_1\le {\epsilon }_1$，可以得到

${\Vert {\rm A}h\Vert }_1={\Vert {\rm A}{\hat{x}}^{{\mathcal{l}}_1}-{\rm A}x\Vert }_1\le {\Vert {\rm A}{\hat{x}}^{{\mathcal{l}}_1}-b\Vert }_1+{\Vert b-{\rm A}x\Vert }_1\le {\epsilon }_1+{\epsilon }_2.$ (43)

令 $T_0$ 是h中 $s\in {\mathbb{Z}}_{+}$ 个最大绝对值项组成的指标集， $T_1$ 是 $h_{T_0{}^c}$ 中 $k=t\left(r+s\right)\in {\mathbb{Z}}_{+}$ 个最大绝对值项组成的指标集且 $T_{\overline{01}}=T\cup T_0\cup T_1$。然后，通过引理4的式(16)和式(43)，得到

$\left(1-{\delta }_{r+s+k}^{lb}-\frac{1+{\delta }_{t\left(r+s\right)}^{ub}}{a\left(r+s,k;\alpha \right)}\right){\Vert h_{\overline{T_{01}}}\Vert }_2-\left(1+{\delta }_{t\left(r+s\right)}^{ub}\right)\frac{2{\Vert x_{{\overline{T_0}}^c}\Vert }_1}{\sqrt{k}-\alpha }\le {\epsilon }_1+{\epsilon }_2,$ (44)

其中 $a\left(r+s,k;\alpha \right)=\frac{\sqrt{k}-\alpha }{\sqrt{r+s}+\alpha }>1$。进一步，条件式(40)意味着

${\rho }_{t\left(r+s\right)}=1-{\delta }_{r+s+k}^{lb}-\frac{1+{\delta }_{t\left(r+s\right)}^{ub}}{a\left(r+s,k;\alpha \right)}>0.$

那么，由式(44)可以得到

${\Vert h_{\overline{T_{01}}}\Vert }_2\le \frac{1}{{\rho }_{t\left(r+s\right)}}\left({\epsilon }_1+{\epsilon }_2\right)+\frac{\left(1+{\delta }_{t\left(r+s\right)}^{ub}\right)\sqrt{r+s}}{{\rho }_{t\left(r+s\right)}\left(\sqrt{k}-\alpha \right)}\frac{2{\Vert x_{{\overline{T_0}}^c}\Vert }_1}{\sqrt{r+s}}.$ (45)

因为 ${\Vert h\Vert }_2=\sqrt{{\Vert h_{\overline{T_{01}}}\Vert }_2^2+{\Vert h_{{\overline{T_{01}}}^c}\Vert }_2^2}$，所以现在需要估计 ${\Vert h_{{\overline{T_{01}}}^c}\Vert }_2$ 的一个上界。假设 $\left|h_1\right|\ge \cdots \ge \left|h_r\right|\ge \cdots \ge \left|h_s\right|\ge \cdots \ge \left|h_{s+k}\right|\ge \cdots \ge \left|h_n\right|$，其中 $k=t\left(r+s\right)\in {\mathbb{Z}}_{+}$。那么，

$\begin{array}{c}{\Vert h_{{\overline{T_{01}}}^c}\Vert }_2\le \sqrt{{\Vert h_{{\overline{T_{01}}}^c}\Vert }_1{\Vert h_{{\overline{T_{01}}}^c}\Vert }_{\infty }}\le \sqrt{\left({\Vert h_{{\overline{T_0}}^c}\Vert }_1-{\displaystyle \underset{j\in T_1}{\sum }\left|h_j\right|}\right)\left|h_{r+s+k}\right|}\\ \le \sqrt{\left({\Vert h_{{\overline{T_0}}^c}\Vert }_1-k\left|h_{r+s+k}\right|\right)\left|h_{r+s+k}\right|}=\sqrt{-k{\left(\left|h_{r+s+k}\right|-\frac{{\Vert h_{{\overline{T_0}}^c}\Vert }_1}{2k}\right)}^2+\frac{{\Vert h_{{\overline{T_0}}^c}\Vert }_1^2}{4k}}\le \frac{{\Vert h_{{\overline{T_0}}^c}\Vert }_1}{2\sqrt{k}}.\end{array}$ (46)

进一步，由式(42)以及 ${\Vert h_{\overline{T_0}}\Vert }_1\le \sqrt{r+s}{\Vert h_{\overline{T_0}}\Vert }_2$ ( $\overline{T_{01}}=T\cup T_0\cup T_1$ )得到

$\begin{array}{c}\frac{{\Vert h_{{\overline{T_0}}^c}\Vert }_1}{2\sqrt{k}}\le \frac{{\Vert h_{\overline{T_0}}\Vert }_1+2{\Vert x_{{\overline{T_0}}^c}\Vert }_1+\alpha {\Vert h\Vert }_2}{2\sqrt{k}}\\ \le \frac{1}{2}\sqrt{\frac{r+s}{k}}\left({\Vert h_{\overline{T_{01}}}\Vert }_2+\frac{2{\Vert x_{{\overline{T_0}}^c}\Vert }_1+\alpha {\Vert h\Vert }_2}{\sqrt{r+s}}\right)\\ =\frac{1}{2\sqrt{t}}\left({\Vert h_{\overline{T_{01}}}\Vert }_2+\frac{2{\Vert x_{{\overline{T_0}}^c}\Vert }_1+\alpha {\Vert h\Vert }_2}{\sqrt{r+s}}\right).\end{array}$ (47)

现将式(46)和式(47)代入 ${\Vert h\Vert }_2=\sqrt{{\Vert h_{\overline{T_{01}}}\Vert }_2^2+{\Vert h_{{\overline{T_{01}}}^c}\Vert }_2^2}$，得到

$\begin{array}{c}{\Vert h\Vert }_2\le \sqrt{{\Vert h_{\overline{T_{01}}}\Vert }_2^2+\frac{1}{4t}{\left({\Vert h_{\overline{T_{01}}}\Vert }_2+\frac{2{\Vert x_{{\overline{T_0}}^c}\Vert }_1+\alpha {\Vert h\Vert }_2}{\sqrt{r+s}}\right)}^2}\\ \le \left(1+\frac{1}{2\sqrt{t}}\right){\Vert h_{\overline{T_{01}}}\Vert }_2+\frac{1}{2\sqrt{t}}\frac{2{\Vert x_{{\overline{T_0}}^c}\Vert }_1}{\sqrt{r+s}}+\frac{1}{2\sqrt{t}}\frac{\alpha {\Vert h\Vert }_2}{\sqrt{r+s}},\end{array}$ (48)

由于 $0\le \alpha \le 1$， $1-\frac{\alpha }{2\sqrt{t\left(r+s\right)}}>0$，因此式(48)可化简为

${\Vert h\Vert }_2\le \frac{\left(2\sqrt{t}+1\right)\sqrt{r+s}}{2\sqrt{t\left(r+s\right)}-\alpha }{\Vert h_{\overline{T_{01}}}\Vert }_2+\frac{2}{2\sqrt{t\left(r+s\right)}-\alpha }{\Vert x_{{\overline{T_0}}^c}\Vert }_1.$ (49)

接下来，将式(45)代入式(49)得到

$\begin{array}{c}{\Vert h\Vert }_2\le \frac{\left(2\sqrt{t}+1\right)\sqrt{r+s}}{2\sqrt{t\left(r+s\right)}-\alpha }\left(\frac{1}{{\rho }_{t\left(r+s\right)}}\left({\epsilon }_1+{\epsilon }_2\right)+\frac{2\left(1+{\delta }_{t\left(r+s\right)}^{ub}\right){\Vert x_{{\overline{T_0}}^c}\Vert }_1}{{\rho }_{t\left(r+s\right)}\left(\sqrt{t\left(r+s\right)}-\alpha \right)}\right)+\frac{2}{2\sqrt{t\left(r+s\right)}-\alpha }{\Vert x_{{\overline{T_0}}^c}\Vert }_1\\ =\frac{2}{2\sqrt{t\left(r+s\right)}-\alpha }\left(1+\frac{\left(2\sqrt{t}+1\right)\left(1+{\delta }_{t\left(r+s\right)}^{ub}\right)\sqrt{r+s}}{{\rho }_{t\left(r+s\right)}\left(\sqrt{t\left(r+s\right)}-\alpha \right)}\right){\Vert x_{{\overline{T_0}}^c}\Vert }_1+\frac{\left(2\sqrt{t}+1\right)\sqrt{r+s}}{\left(2\sqrt{t\left(r+s\right)}-\alpha \right){\rho }_{t\left(r+s\right)}}\left({\epsilon }_1+{\epsilon }_2\right).\end{array}$

注2 若x是精确 $r+s$ -稀疏，即 $x_{{\overline{T_0}}^c}=0$，由定理2得

${\Vert {\hat{x}}^{{\mathcal{l}}_1}-x\Vert }_2\le \frac{\left(2\sqrt{t}+1\right)\sqrt{r+s}}{\left(2\sqrt{t\left(r+s\right)}-\alpha \right){\rho }_{t\left(r+s\right)}}\left({\epsilon }_1+{\epsilon }_2\right),$

特别地，在无噪声情形下， ${\hat{x}}^{{\mathcal{l}}_1}=x$，其中 ${\hat{x}}^{{\mathcal{l}}_1}$ 是满足 $B=\left\{0\right\}$ 的式(4)的最小值。

定理3考虑 $y={\rm A}x+e$，其中 ${\Vert {{\rm A}}^{{\rm T}}e\Vert }_{\infty }\le {\epsilon }_2$ ( ${\epsilon }_2\le {\epsilon }_1$ )。假设信号x的部分已知支撑是T ( $\left|T\right|=r$ )，对于 $t\ge 3$ 、 $s\ge 2$，若矩阵 ${\rm A}$ 满足：

${\delta }_{t\left(r+s\right)}<\frac{1}{\sqrt{1+\frac{{\left(\sqrt{r+s}+\alpha \right)}^2\left({\left(1+\frac{\sqrt{2}}{2}\right)}^2\left(t\left(r+s\right)-\left(r+s\right)-\sqrt{t\left(r+s\right)-\left(r+s\right)}\right)+1\right)}{\left(r+s\right){\left(t-1\right)}^2{\left(\sqrt{r+s}-1\right)}^2}}},$ (50)

则式(4)的解 ${\hat{x}}^{DS}$ 满足：

$\begin{array}{c}{\Vert {\hat{x}}^{DS}-x\Vert }_2\le \left(1+\sqrt{\frac{{\alpha }^2}{4\left(r+s\right)}+\frac{\alpha +\sqrt{r+s}}{\sqrt{r+s}}}+\frac{\alpha +\sqrt{2}}{2\sqrt{r+s}}\right)\frac{\left(1-\mu \right)\mu \sqrt{t\left(r+s\right)}}{\mu -{\mu }^2-{\left(\mu -1\right)}^2{\delta }_{t\left(r+s\right)}}\left({\epsilon }_1+{\epsilon }_2\right)\\ +(\left(\sqrt{r+s}+\sqrt{\frac{{\alpha }^2}{4}+\alpha \sqrt{r+s}+\left(r+s\right)}+\frac{\alpha +\sqrt{2}}{2}\right)(\frac{2{\delta }_{t\left(r+s\right)}\left(1-2\mu \right)}{\left(\mu -{\mu }^2-{\left(\mu -1\right)}^2{\delta }_{t\left(r+s\right)}\right)\left(\sqrt{r+s}+\alpha \right)}\\ +\sqrt{\frac{2\left(1-2\mu \right){\delta }_{t\left(r+s\right)}}{\left(\mu -{\mu }^2-{\left(\mu -1\right)}^2{\delta }_{t\left(r+s\right)}\right){\left(\sqrt{r+s}+\alpha \right)}^2}})+\frac{\sqrt{2\left(r+s\right)}}{2})\frac{{\Vert x_{{\overline{T_0}}^c}\Vert }_1}{\sqrt{r+s}}.\end{array}$ (51)

其中 $\mu =\frac{1}{\sqrt{1+\frac{{\left(\sqrt{r+s}+\alpha \right)}^2\left({\left(1+\frac{\sqrt{2}}{2}\right)}^2\left(t\left(r+s\right)-\left(r+s\right)-\sqrt{t\left(r+s\right)-\left(r+s\right)}\right)+1\right)}{\left(r+s\right){\left(t-1\right)}^2{\left(\sqrt{r+s}-1\right)}^2}}+1}$。

证明 定理3的证明和定理1的证明类似。定义 $h={\hat{x}}^{DS}-x$，其中 ${\hat{x}}^{DS}$ 是满足式(26)的式(4)的最小值，这意味着 ${\Vert {{\rm A}}^{{\rm T}}\left(y-{\rm A}{\hat{x}}^{DS}\right)\Vert }_{\infty }\le {\epsilon }_1$，又 ${\Vert {{\rm A}}^{{\rm T}}\left(y-{\rm A}x\right)\Vert }_{\infty }\le {\epsilon }_2$，得到

${\Vert {{\rm A}}^{{\rm T}}{\rm A}h\Vert }_{\infty }\le {\Vert {{\rm A}}^{{\rm T}}\left({\rm A}{\hat{x}}^{DS}-y\right)\Vert }_{\infty }+{\Vert {{\rm A}}^{{\rm T}}\left(y-{\rm A}x\right)\Vert }_{\infty }\le {\epsilon }_1+{\epsilon }_2$ (52)

来代替式(29)。因此，

$\langle {\rm A}\left(h_{\overline{T_0}}+h_{{\text{W}}_1}\right),{\rm A}h\rangle =\langle h_{\overline{T_0}}+h_{{\text{W}}_1},{{\rm A}}^{{\rm T}}{\rm A}h\rangle \le {\Vert h_{\overline{T_0}}+h_{{\text{W}}_1}\Vert }_1{\Vert {{\rm A}}^{{\rm T}}{\rm A}h\Vert }_{\infty }\le \sqrt{t\left(r+s\right)}{\Vert h_{\overline{T_0}}+h_{{\text{W}}_1}\Vert }_2\left({\epsilon }_1+{\epsilon }_2\right).$ (53)

将式(53)代入式(36)可以得到

$\begin{array}{l}{\displaystyle \underset{i=1}{\overset{N}{\sum }}{\lambda }_i{\Vert {\rm A}\left(\left(\frac{1}{2}-\mu \right)\left(h_{\overline{T_0}}+h_{{\text{W}}_1}\right)-\frac{1}{2}\mu u^{\left(i\right)}+\mu h\right)\Vert }_2^2}\\ \le \left(1+{\delta }_{t\left(r+s\right)}\right)\left({\left(\frac{1}{2}-\mu \right)}^2{\Vert h_{\overline{T_0}}+h_{{\text{W}}_1}\Vert }_2^2+\frac{{\mu }^2}{4}{\displaystyle \underset{i=1}{\overset{N}{\sum }}{\lambda }_i{\Vert u^{\left(i\right)}\Vert }_2^2}\right)+\left(1-\mu \right)\mu \sqrt{t\left(r+s\right)}{\Vert h_{\overline{T_0}}+h_{{\text{W}}_1}\Vert }_2\left({\epsilon }_1+{\epsilon }_2\right).\end{array}$

证明的其余步骤几乎和定理1的证明相同，这就得到结果

$\begin{array}{c}{\Vert h\Vert }_2\le \left(1+\sqrt{\frac{{\alpha }^2}{4\left(r+s\right)}+\frac{\alpha +\sqrt{r+s}}{\sqrt{r+s}}}+\frac{\alpha +\sqrt{2}}{2\sqrt{r+s}}\right)\frac{\left(1-\mu \right)\mu \sqrt{t\left(r+s\right)}}{\mu -{\mu }^2-{\left(\mu -1\right)}^2{\delta }_{t\left(r+s\right)}}\left({\epsilon }_1+{\epsilon }_2\right)\\ +(\left(\sqrt{r+s}+\sqrt{\frac{{\alpha }^2}{4}+\alpha \sqrt{r+s}+\left(r+s\right)}+\frac{\alpha +\sqrt{2}}{2}\right)(\frac{2{\delta }_{t\left(r+s\right)}\left(1-2\mu \right)}{\left(\mu -{\mu }^2-{\left(\mu -1\right)}^2{\delta }_{t\left(r+s\right)}\right)\left(\sqrt{r+s}+\alpha \right)}\\ +\sqrt{\frac{2\left(1-2\mu \right){\delta }_{t\left(r+s\right)}}{\left(\mu -{\mu }^2-{\left(\mu -1\right)}^2{\delta }_{t\left(r+s\right)}\right){\left(\sqrt{r+s}+\alpha \right)}^2}})+\frac{\sqrt{2\left(r+s\right)}}{2})\frac{{\Vert x_{{\overline{T_0}}^c}\Vert }_1}{\sqrt{r+s}}.\end{array}$

注3 若x是精确 $r+s$ -稀疏，即 $x_{{\overline{T_0}}^c}=0$，由定理3得

${\Vert {\hat{x}}^{DS}-x\Vert }_2\le \left(1+\sqrt{\frac{{\alpha }^2}{4\left(r+s\right)}+\frac{\alpha +\sqrt{r+s}}{\sqrt{r+s}}}+\frac{\alpha +\sqrt{2}}{2\sqrt{r+s}}\right)\frac{\left(1-\mu \right)\mu \sqrt{t\left(r+s\right)}}{\mu -{\mu }^2-{\left(\mu -1\right)}^2{\delta }_{t\left(r+s\right)}}\left({\epsilon }_1+{\epsilon }_2\right),$

特别地，在无噪声情形下， ${\hat{x}}^{DS}=x$，其中 ${\hat{x}}^{DS}$ 是满足 $B=\left\{0\right\}$ 的式(4)的最小值。

4. 结论

文章基于 ${\mathcal{l}}_1-\alpha {\mathcal{l}}_2$ $\left(0<\alpha \le 1\right)$ 最小化模型，使用分解向量的方法，得到了三种不同噪声(高斯噪声、脉冲噪声、均匀噪声)情形下部分支撑信息已知的信号恢复的充分条件。文章的创新之处在于：这些条件在推广了文献 [14] [17] 结果的同时，还讨论了高斯噪声下的结果，是目前第一篇在三种不同噪声情形下将分解向量方法和信号的先验支撑信息相结合的信号恢复的文章。文章的结果是对 ${\mathcal{l}}_1-\alpha {\mathcal{l}}_2$ $\left(0<\alpha \le 1\right)$ 最小化模型下信号恢复的相关理论知识的补充，使得研究者在信号恢复实践中有更多的选择。文章的不足之处在于仅围绕测量矩阵的限制等距性展开研究。未来的研究工作集中于利用 ${\mathcal{l}}_1-\alpha {\mathcal{l}}_2$ $\left(0<\alpha \le 1\right)$ 最小化模型得到基于测量矩阵相干性的信号恢复的充分条件。

NOTES

^*第一作者。

^#通讯作者。