基于lp-αl₁模型下的部分已知支集信号恢复的研究

Research on Partial Known Support Signal Recovery Based on lp-αl₁ Model

摘要: 压缩感知通过少量非自适应的线性测量有效地获取稀疏信号，是一种新型的采样方法。它突破了传统的香农采样定理的局限性，以远低于香农采样率的数据实现原始信号的精确恢复。本文在l₁，l_q(0＜q＜1），l₁-l₂，l₁-αl₂(0≤α≤1)等最小化模型基础下，考虑了新模型lp-αl₁(0＜p＜1,0＜α≤1)最小化，对部分已知支集的信号重建提出了一个新的条件，得到了信号在l₂有界噪声、DS噪声及高斯噪声情形下的误差逼近。

Abstract: Compressed sensing is a new sampling method which can obtain sparse signals effectively by a small number of non-adaptive linear measurements. It breaks the limitation of the traditional Xiangnong sampling theory and achieves the exact recovery of theoriginal signal with the data far below the Xiangnong sampling rate. In this paper, based on the l₁，l_q(0＜q＜1），l₁-l₂，l₁-αl₂(0≤α≤1) minimization models, a new model called lp-αl₁ minimization and a new condition for signal reconstruction with partial known support is proposed, and the error approximation of the signal in the case of l₂ bounded noise and DS noise is obtained.

1. 引言

压缩感知是由Candès，Donoho和Tao等提出的一种全新的基于稀疏信号的采样理论，被广泛应用于医学成像、光学成像、雷达探测等诸多领域，目的是从较少的测量 $y=Ax$ 中恢复一个较为稀疏的信号 $x\in R^n$ ，其中 $A\in R^{m\times n}\left(m\ll n\right)$ 是一个测量矩阵。实际应用中为了能够合理快速地重构信号，我们接触到的第一个方法是 $l_0$ 最小化方法 [1] ，即：

$\underset{x\in R^n}{\min }{\Vert x\Vert }_0,\text{s}\text{.t}.y=Ax$ (1)

然而这个方法是一个非确定多项式难度问题(NP-hard)，因为 $l_1$ 范数是一个凸函数，进而学者Candès等人想到用 $l_1$ 最小化法来对 $l_0$ 最小化进行凸松弛 [2] ，即：

$\underset{x\in R^n}{\min }{\Vert x\Vert }_1,\text{s}\text{.t}.y=Ax$ (2)

该模型灵活地将多个子问题的优化问题转化为凸优化问题，在理论研究的基础上，学者们得到了在测量矩阵满足限制等距性、相干性等特性的条件下，对稀疏信号进行稳定恢复和鲁棒恢复的充分条件。随后，Jacques等人提出了更加一般的 $l_p$ 范数模型，用于处理含噪信号的重构 [3] ；在此基础上，Ince等人对信号的部分已知支集已知进行研究 [4] ，提出了一种基于部分已知支集的稀疏重建方法，并给出了具有部分已知支撑的信号恢复条件，理论结果表明该最小化方法具有稳定性和鲁棒性。近年来，Yin等人提出了 $l_1-l_2$ 范数模型 [5] ，即：

$\underset{x\in R^n}{\min }{\Vert x\Vert }_1-{\Vert x\Vert }_2,\text{s}\text{.t}.y=Ax$ (3)

文章中Yin等人给出了该模型下精确和稳定恢复稀疏信号的条件，实质性地证明了该模型优于上述提到的几种模型。文章 [6] [7] [8] [9] 中主要利用限制等距性和限制正交性，为 $l_1-l_2$ 最小化建立了一个改进的充分条件，以保证鲁棒的信号恢复，事实证明，该条件都比之前的条件要好得多。文章 [10] [11] [12] [13] 提出了部分已知支集下的信号恢复条件，给出了最小化方法本身也是非自适应的，在实际示例中可以得出信号最大误差的估计，因此部分已知先验信息对于恢复信号是非常有用的。受到前人研究成果的启发，自然而然地得到在 $l_p-\alpha l_1$ 最小化下，讨论信号恢复是有意义的。文章利用 $l_p-\alpha l_1$ $\left(0<p<1,0<\alpha \le 1\right)$ 最小化方法对部分支集已知的信号进行恢复，形成了一个新的信号鲁棒恢复的条件，并考虑噪声下的已知部分支集的信号重建，得到误差估计的上界。

2. 预备知识

在给出文章的主要结论之前，首先介绍由Candès和Tao引入的两个概念 [2] ：限制等距性和限制正交性，以及两个重要的引理 [14] 。

定义1 [2] 对所有的s稀疏信号 $x\in R^n$ (即最多有s个非零项)，若存在一个最小的常数 ${\delta }_s\in \left(0,1\right)$ 使得：

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

成立，则称矩阵 $A\in R^{m\times n}$ 满足s阶的限制等距性， ${\delta }_s$ 是s阶的限制等距常数。

定义2 [2] 对每个s稀疏信号 $x\in R^n$ 和t稀疏信号 $y\in R^n$ ，若存在一个最小的常数 ${\theta }_{s,t}\ge 0$ 使得：

$\left|\langle Ax,Ay\rangle \right|\le {\theta }_{s,t}{\Vert x\Vert }_2{\Vert y\Vert }_2$

成立，则称矩阵 $A\in R^{m\times n}$ 满足 $\left(s,t\right)$ 阶的限制正交性， ${\theta }_{s,t}$ 是 $\left(s,t\right)$ 阶的限制正交常数。

引理1 [14] 令 $k_1\le \eta$ ， $k_2\le \eta$ ， $\eta \ge 0$ 假设 $x,y\in R^n$ 有不相交的支撑，且 ${\Vert x\Vert }_0\le k_1$ ， ${\Vert y\Vert }_1\le \eta k_2$ ， ${\Vert y\Vert }_{\infty }\le \eta$ ，则有：

$\left|\langle Ax,Ay\rangle \right|\le \sqrt{k_2}{\theta }_{k_1,k_2}\eta {\Vert x\Vert }_2$

引理2 [14] 假设 $l\le n$ ， $x_1\ge x_2\ge \cdots x_n\ge 0$ ， $\gamma \ge 0$ ， ${\displaystyle \underset{i=1}{\overset{l}{\sum }}{x}_i}+\gamma \ge {\displaystyle \underset{i=l+1}{\overset{n}{\sum }}{x}_i}$ ，则对所有 $p\ge 1$ 有：

${\displaystyle \underset{i=l+1}{\overset{n}{\sum }}{x}_i^p}\le l{\left(\sqrt[p]{\frac{{\displaystyle \underset{i=1}{\overset{l}{\sum }}{x}_i^p}}{l}}+\frac{\gamma }{l}\right)}^p$

3. 主要结论

3.1. 部分支集已知的信号重建

基于已知的几种模型的研究，我们在此基础上考虑以下无约束优化问题：

$\underset{x\in R^n}{\min }{\Vert x_{T^C}\Vert }_p-\alpha {\Vert x_{T^C}\Vert }_1,\text{s}\text{.t}.\hat{b}-Ax\in B$ (4)

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

$\underset{x\in R^n}{\min }{\Vert x_{T^C}\Vert }_p-\alpha {\Vert x_{T^C}\Vert }_1,\text{s}\text{.t}.\hat{b}=Ax$ (5)

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

下面我们讨论在噪声 $B^{l_2}\left(\epsilon \right)=\left\{e:{\Vert e\Vert }_2\le \epsilon \right\}$ 和噪声 $B^{DS}\left(\epsilon \right)=\left\{e:{\Vert A^{T}e\Vert }_{\infty }\le \epsilon \right\}$ 的情况下，研究关于已知部分支集的信号重建。

定理1 如果信号x的部分已知支撑是T，且 $\left|T\right|=s$ ，若矩阵A满足：

$k+s-\alpha \sqrt{k}>\left(k+s-\alpha \sqrt{k}\right){\delta }_{k+s}+\left(k+s+\alpha \left(\sqrt{2\left(k+s\right)}-\sqrt{k}\right)\right){\theta }_{k+s,k}$ (6)

则(4)式的解 $x^{*}\left(l_2\right)$ 和 $x^{*}\left(DS\right)$ 分别满足：

${\Vert x^{*}\left(l_2\right)-x\Vert }_2\le C_1\epsilon +D_1{\Vert r-r_{T0}\Vert }_p$ (7)

${\Vert x^{*}\left(DS\right)-x\Vert }_2\le C_2\epsilon +D_2{\Vert r-r_{T0}\Vert }_p$ (8)

其中 $T\cap T_0=\varnothing$ ， ${\Vert r-r_{T_0}\Vert }_p={\Vert x_{\overline{T_0^C}}\Vert }_p$ ，r是残差 $r=x-x_T$ ， $T_0$ 是r的绝对值中最大的k个项的指标构成的一个指标集，即 $r_{T_0}$ 是r的最佳k-项逼近，常数：

$C_1=\frac{2\sqrt{2\left(1+{\delta }_{k+s}\right)}\epsilon }{\left(k+s-\alpha \sqrt{k}\right)\left(1-{\delta }_{k+s}\right)-\left(k+s-\alpha \left(\sqrt{k}-\sqrt{2\left(k+s\right)}\right)\right){\theta }_{k+s,k}}$

$D_1=\frac{2\sqrt{\frac{2}{k}\left(k+s\right)}{\theta }_{k+s,k}+2\sqrt{k+s}\left(1-{\delta }_{k+s}-{\theta }_{k+s,k}\right)}{\left(k+s-\alpha \sqrt{k}\right)\left(1-{\delta }_{k+s}\right)-\left(k+s-\alpha \left(\sqrt{k}-\sqrt{2\left(k+s\right)}\right)\right){\theta }_{k+s,k}}$

$C_2=\frac{2\sqrt{2\left(k+s\right)}\left(k+s\right)}{\left(k+s-\alpha \sqrt{k}\right)\left(1-{\delta }_{k+s}\right)-\left(k+s-\alpha \left(\sqrt{k}-\sqrt{2\left(k+s\right)}\right)\right){\theta }_{k+s,k}}$

$D_2=\frac{2\sqrt{\frac{2}{k}}\left(k+s\right){\theta }_{k+s,k}+2\sqrt{k+s}\left(1-{\delta }_{k+s}-{\theta }_{k+s,k}\right)}{\left(k+s-\alpha \sqrt{k}\right)\left(1-{\delta }_{k+s}\right)-\left(k+s-\alpha \left(\sqrt{k}-\sqrt{2\left(k+s\right)}\right)\right){\theta }_{k+s,k}}$

证明 1) $B^{l_2}\left(\epsilon \right)=\left\{e:{\Vert e\Vert }_2\le \epsilon \right\}$ 。

现设定(4)式的解 $x^{*}=x+h$ ， $T_1$ 是 $h_{T^c}$ 的绝对值中最大的k个项的指标构成的一个指标集， $h_{T^c}$ 是保留h在 $T^c$ 中指标所指引的元素，而令在 $T^c$ 之外的指标所指引的元素取0的向量，现假设 $\overline{T_0}=T\cup T_0$ ， $\overline{T_1}=T\cup T_1$ ， $\overline{T_0^c}={\left(T\cup T_0\right)}^c$ ， $\overline{T_1^c}={\left(T\cup T_1\right)}^c$ 。

因为 $x^{*}$ 是(4)式的解，所以有：

${\Vert x_{T^c}^{\ast }\Vert }_p-\alpha {\Vert x_{T^c}^{\ast }\Vert }_1={\Vert {\left(x+h\right)}_{T^c}\Vert }_p-\alpha {\Vert {\left(x+h\right)}_{T^c}\Vert }_1\le {\Vert x_{T^c}\Vert }_p-\alpha {\Vert x_{T^c}\Vert }_1$ (9)

由于 $T^c=T_0^c\cup \overline{T_0^c}$ ，很容易得到：

$\begin{array}{c}{\Vert {\left(x+h\right)}_{T^c}\Vert }_p-\alpha {\Vert {\left(x+h\right)}_{T^c}\Vert }_1={\Vert {\left(x+h\right)}_{T_0}\Vert }_p+{\Vert {\left(x+h\right)}_{\overline{T_0^c}}\Vert }_p-\alpha {\Vert {\left(x+h\right)}_{T^c}\Vert }_1\\ \ge {\Vert x_{T_0}\Vert }_p-{\Vert h_{T_0}\Vert }_p+{\Vert x_{\overline{T_0^c}}\Vert }_p-{\Vert h_{\overline{T_0^c}}\Vert }_p-\alpha {\Vert {\left(x+h\right)}_{T^c}\Vert }_1\end{array}$ (10)

结合式(9)和式(10)整理可得：

${\Vert h_{\overline{T_0^c}}\Vert }_p\le {\Vert h_{T_0}\Vert }_p+2{\Vert x_{\overline{T_0^c}}\Vert }_p+\alpha {\Vert h_{T^c}\Vert }_1$ (11)

由于 ${\Vert h_{\overline{T_1^c}}\Vert }_p\le {\Vert h_{\overline{T_0^c}}\Vert }_p$ ， ${\Vert h_{T_0}\Vert }_p\le {\Vert h_{T_1}\Vert }_p$ ， ${\Vert h_{T_c}\Vert }_1\le \sqrt{\frac{k}{k+s}}{\Vert h\Vert }_1$ ，式(11)可变为：

${\Vert h_{\overline{T_1^c}}\Vert }_p\le {\Vert h_{T_1}\Vert }_p+2{\Vert x_{\overline{T_0^c}}\Vert }_p+\alpha \sqrt{\frac{k}{k+s}}{\Vert h\Vert }_1$ (12)

因为 ${\Vert h_{\overline{T_1}}\Vert }_0\le k+s,{\Vert h_{\overline{T_1^c}}\Vert }_{\infty }\le \frac{{\Vert h_{T_1}\Vert }_1}{k}\le \frac{{\Vert h_{\overline{T_1}}\Vert }_p}{\sqrt{k}}+\frac{2{\Vert x_{\overline{T_0^c}}\Vert }_p+\alpha \sqrt{\frac{k}{k+s}}{\Vert h\Vert }_1}{k}$ ，

故 ${\Vert h_{T_1^c}\Vert }_1\le k{\Vert h_{\overline{T_1^c}}\Vert }_{\infty }\le k\left(\frac{{\Vert h_{\overline{T_1}}\Vert }_p}{\sqrt{k}}+\frac{2{\Vert x_{\overline{T_0^c}}\Vert }_p+\alpha \sqrt{\frac{k}{k+s}}{\Vert h\Vert }_1}{k}\right)$ 。

再利用引理1：令 $k_1=k+s$ ， $k_2=k$ ， $\eta =\frac{{\Vert h_{\overline{T_1}}\Vert }_p}{\sqrt{k}}+\frac{2{\Vert x_{\overline{T_0^c}}\Vert }_p+\alpha \sqrt{\frac{k}{k+s}}{\Vert h\Vert }_1}{k}$ ，则有：

$\left|\langle A{h}_{\overline{T_1}},A{h}_{\overline{T_1^c}}\rangle \right|\le {\theta }_{k+s,k}\sqrt{k}{\Vert h_{\overline{T_1}}\Vert }_p\left(\frac{{\Vert h_{\overline{T_1}}\Vert }_p}{\sqrt{k}}+\frac{2{\Vert x_{\overline{T_0^c}}\Vert }_p+\alpha \sqrt{\frac{k}{k+s}}{\Vert h\Vert }_1}{k}\right)$ .

进而可以得到：

$\begin{array}{c}\left|\langle A{h}_{\overline{T_1}},Ah\rangle \right|\ge {\Vert A{h}_{\overline{T_1}}\Vert }_2^2-\left|\langle A{h}_{\overline{T_1}},A{h}_{\overline{T_1^c}}\rangle \right|\\ \ge {\Vert A{h}_{\overline{T_1}}\Vert }_2^2-{\theta }_{k+s,k}{\Vert h_{\overline{T_1}}\Vert }_p\left({\Vert h_{\overline{T_1}}\Vert }_p+\frac{2{\Vert x_{\overline{T_0^c}}\Vert }_p+\alpha \sqrt{\frac{k}{k+s}}{\Vert h\Vert }_1}{\sqrt{k}}\right)\\ \ge \left(1-{\delta }_{k+s}\right){\Vert h_{\overline{T_1}}\Vert }_2^2-{\theta }_{k+s,k}{\Vert h_{\overline{T_1}}\Vert }_p\left({\Vert h_{\overline{T_1}}\Vert }_p+\frac{2{\Vert x_{\overline{T_0^c}}\Vert }_p+\alpha \sqrt{\frac{k}{k+s}}{\Vert h\Vert }_1}{\sqrt{k}}\right)\end{array}$ (13)

由于

$\begin{array}{c}{\Vert Ah\Vert }_2\cdot \left|\langle A{h}_{\overline{T_1}},Ah\rangle \right|\le {\Vert A{h}_{\overline{T_1}}\Vert }_2{\Vert Ah\Vert }_2\\ \le \sqrt{1+{\delta }_{k+s}}{\Vert h_{\overline{T_1}}\Vert }_2\left({\Vert A{x}^{*}-\hat{b}\Vert }_2+{\Vert Ax-\hat{b}\Vert }_2\right)\\ \le 2\epsilon \sqrt{1+{\delta }_{k+s}}{\Vert h_{\overline{T_1}}\Vert }_2\end{array}$ (14)

结合式(13)和式(14)，整理可得：

$\begin{array}{c}2\epsilon \sqrt{1+{\delta }_{k+s}}{\Vert h_{\overline{T_1}}\Vert }_2\ge \left(1-{\delta }_{k+s}\right){\Vert h_{\overline{T_1}}\Vert }_2^2-{\theta }_{k+s,k}{\Vert h_{\overline{T_1}}\Vert }_p\left({\Vert h_{\overline{T_1}}\Vert }_p+\frac{2{\Vert x_{\overline{T_0^c}}\Vert }_p+\alpha \sqrt{\frac{k}{k+s}}{\Vert h\Vert }_1}{\sqrt{k}}\right)\\ \ge \left(1-{\delta }_{k+s}\right){\Vert h_{\overline{T_1}}\Vert }_2^2-{\theta }_{k+s,k}{\Vert h_{\overline{T_1}}\Vert }_2\left({\Vert h_{\overline{T_1}}\Vert }_2+\frac{2{\Vert x_{\overline{T_0^c}}\Vert }_p+\alpha \sqrt{\frac{k}{k+s}}{\Vert h\Vert }_1}{\sqrt{k}}\right)\end{array}$

两边同时处以 ${\Vert h_{\overline{T_1}}\Vert }_2$ 可得： $2\epsilon \sqrt{1+{\delta }_{k+s}}+\frac{{\theta }_{k+s,k}\left(2{\Vert x_{\overline{T_0^c}}\Vert }_p+\alpha \sqrt{\frac{k}{k+s}}{\Vert h\Vert }_1\right)}{\sqrt{k}}\ge \left(1-{\delta }_{k+s}-{\theta }_{k+s,k}\right){\Vert h_{\overline{T_1}}\Vert }_2$ 。

由于条件中的式(6)保证 $1-{\delta }_{k+s}-{\theta }_{k+s,k}>0$ ，所以：

${\Vert h_{\overline{T_1}}\Vert }_2\le \frac{2\epsilon \sqrt{1+{\delta }_{k+s}}}{1-{\delta }_{k+s}-{\theta }_{k+s,k}}+\frac{{\theta }_{k+s,k}\left(2{\Vert x_{\overline{T_0^c}}\Vert }_p+\alpha \sqrt{\frac{k}{k+s}}{\Vert h\Vert }_1\right)}{\sqrt{k}\left(1-{\delta }_{k+s}-{\theta }_{k+s,k}\right)}$

因为 ${\Vert h_{T_1}\Vert }_p\le {\Vert h_{\overline{T_1}}\Vert }_p$ ，则从式(12)可以得到：

${\Vert h_{\overline{T_1^c}}\Vert }_p\le {\Vert h_{\overline{T_1}}\Vert }_p+2{\Vert x_{\overline{T_0^c}}\Vert }_p+\alpha \sqrt{\frac{k}{k+s}}{\Vert h\Vert }_1$ (15)

引用引理2，其中令 $l=k+s$ ， $\gamma =2{\Vert x_{\overline{T_0^c}}\Vert }_p+\alpha \sqrt{\frac{k}{k+s}}{\Vert h\Vert }_1$ ，进一步可以得到：

${\Vert h_{\overline{T_1^c}}\Vert }_2\le {\Vert h_{\overline{T_1}}\Vert }_p+\frac{2{\Vert x_{\overline{T_0^c}}\Vert }_p+\alpha \sqrt{\frac{k}{k+s}}{\Vert h\Vert }_1}{\sqrt{k+s}}$ .

因此：

$\begin{array}{c}{\Vert h\Vert }_2\le \sqrt{{\Vert h_{\overline{T_1}}\Vert }_2^2+{\Vert h_{\overline{T_1^c}}\Vert }_2^2}\le \sqrt{{\Vert h_{\overline{T_1}}\Vert }_2^2+{\left({\Vert h_{\overline{T_1}}\Vert }_p+\frac{2{\Vert x_{\overline{T_0^c}}\Vert }_p+\alpha \sqrt{\frac{k}{k+s}}{\Vert h\Vert }_1}{\sqrt{k+s}}\right)}^2}\\ \le \sqrt{2}{\Vert h_{\overline{T_1}}\Vert }_2+\frac{2{\Vert x_{\overline{T_0^c}}\Vert }_p+\alpha \sqrt{\frac{k}{k+s}}{\Vert h\Vert }_1}{\sqrt{k+s}}\end{array}$ (16)

整理后得：

$\begin{array}{c}{\Vert h\Vert }_2\le \frac{2\sqrt{2\left(1+{\delta }_{k+s}\right)}\epsilon }{\left(k+s-\alpha \sqrt{k}\right)\left(1-{\delta }_{k+s}\right)-\left(k+s-\alpha \left(\sqrt{k}-\sqrt{2\left(k+s\right)}\right)\right){\theta }_{k+s,k}}\\ +\frac{2\sqrt{2\left(1+\frac{s}{k}\right)}{\theta }_{k+s,k}+2\sqrt{k+s}\left(1-{\delta }_{k+s}-{\theta }_{k+s,k}\right)}{\left(k+s-\alpha \sqrt{k}\right)\left(1-{\delta }_{k+s}\right)-\left(k+s-\alpha \left(\sqrt{k}-\sqrt{2\left(k+s\right)}\right)\right){\theta }_{k+s,k}}{\Vert x_{\overline{T_0^c}}\Vert }_p\end{array}$

特别地，在无噪声情形下有：

${\Vert h\Vert }_2\le \frac{2\sqrt{2\left(1+\frac{s}{k}\right)}{\theta }_{k+s,k}+2\sqrt{k+s}\left(1-{\delta }_{k+s}-{\theta }_{k+s,k}\right)}{\left(k+s-\alpha \sqrt{k}\right)\left(1-{\delta }_{k+s}\right)-\left(k+s-\alpha \left(\sqrt{k}-\sqrt{2\left(k+s\right)}\right)\right){\theta }_{k+s,k}}{\Vert x_{\overline{T_0^c}}\Vert }_p$

$B^{DS}\left(\epsilon \right)=\left\{e:{\Vert A^{T}e\Vert }_{\infty }\le \epsilon \right\}$ 。类似1)的证明：

$\begin{array}{c}\left|\langle A{h}_{\overline{T_1}},Ah\rangle \right|=\left|\langle A_{\overline{T_1}}{h}_{\overline{T_1}},A\left(x^{*}-x\right)\rangle \right|\\ =\left|\langle A_{\overline{T_1}}{h}_{\overline{T_1}},A{x}^{*}-\hat{b}+e\rangle \right|\\ =\left|\langle h_{\overline{T_1}},A_{\overline{T_1}}\left(A{x}^{*}-\hat{b}+e\right)\rangle \right|\end{array}$

$\begin{array}{c}\le {\Vert h_{\overline{T_1}}\Vert }_1{\Vert A_{\overline{T_1}}\left(A{x}^{*}-\hat{b}+e\right)\Vert }_{\infty }\\ \le 2\epsilon \sqrt{\left(k+s\right)}{\Vert h_{\overline{T_1}}\Vert }_2\end{array}$ (17)

结合式(13)和式(16)可得：

$\begin{array}{c}2\epsilon \sqrt{k+s}{\Vert h_{\overline{T_1}}\Vert }_2\ge \left(1-{\delta }_{k+s}\right){\Vert h_{\overline{T_1}}\Vert }_2^2-{\theta }_{k+s,k}{\Vert h_{\overline{T_1}}\Vert }_p\left({\Vert h_{\overline{T_1}}\Vert }_p+\frac{2{\Vert x_{\overline{T_0^c}}\Vert }_p+\alpha \sqrt{\frac{k}{k+s}}{\Vert h\Vert }_1}{\sqrt{k}}\right)\\ \ge \left(1-{\delta }_{k+s}\right){\Vert h_{\overline{T_1}}\Vert }_2^2-{\theta }_{k+s,k}{\Vert h_{\overline{T_1}}\Vert }_2\left({\Vert h_{\overline{T_1}}\Vert }_2+\frac{2{\Vert x_{\overline{T_0^c}}\Vert }_p+\alpha \sqrt{\frac{k}{k+s}}{\Vert h\Vert }_1}{\sqrt{k}}\right)\end{array}$

整理后有：

${\Vert h_{\overline{T_1}}\Vert }_2\le \frac{2\sqrt{k+s}\epsilon }{1-{\delta }_{k+s}-{\theta }_{k+s,k}}+\frac{{\theta }_{k+s,k}\left(2{\Vert x_{\overline{T_0^c}}\Vert }_p+\alpha \sqrt{\frac{k}{k+s}}{\Vert h\Vert }_1\right)}{\sqrt{k}\left(1-{\delta }_{k+s}-{\theta }_{k+s,k}\right)}$ (18)

式(16)和式(18)整理后可得：

$\begin{array}{c}{\Vert h\Vert }_2\le \frac{2\sqrt{2\left(k+s\right)}\left(k+s\right)\epsilon }{\left(k+s-\alpha \sqrt{k}\right)\left(1-{\delta }_{k+s}\right)-\left(k+s-\alpha \left(\sqrt{k}-\sqrt{2\left(k+s\right)}\right)\right){\theta }_{k+s,k}}\\ +\frac{2\sqrt{\frac{2}{k}}\left(k+s\right){\theta }_{k+s,k}+2\sqrt{k+s}\left(1-{\delta }_{k+s}-{\theta }_{k+s,k}\right)}{\left(k+s-\alpha \sqrt{k}\right)\left(1-{\delta }_{k+s}\right)-\left(k+s-\alpha \left(\sqrt{k}-\sqrt{2\left(k+s\right)}\right)\right){\theta }_{k+s,k}}{\Vert x_{\overline{T_0^c}}\Vert }_p\end{array}$

特别地，在无噪声情形下有：

${\Vert h\Vert }_2\le \frac{2\sqrt{\frac{2}{k}}\left(k+s\right){\theta }_{k+s,k}+2\sqrt{k+s}\left(1-{\delta }_{k+s}-{\theta }_{k+s,k}\right)}{\left(k+s-\alpha \sqrt{k}\right)\left(1-{\delta }_{k+s}\right)-\left(k+s-\alpha \left(\sqrt{k}-\sqrt{2\left(k+s\right)}\right)\right){\theta }_{k+s,k}}{\Vert x_{\overline{T_0^c}}\Vert }_p$

定理1得证。

3.2. 高斯噪声

高斯噪声是众多噪声中一种较为特殊的噪声，其观察模型为：

$y=Ax+e,e\sim N\left(0,{\sigma }^2{I}_n\right)$ .

假定 $\sigma$ 是已知的，矩阵A中的列向量均为单位向量，则定义以下两种噪声类型：

$B_1=\left\{e:{\Vert e\Vert }_2\le \sigma \sqrt{n+2\sqrt{nInn}}\right\}$ ； $B_2=\left\{e:{\Vert A^{T}e\Vert }_{\infty }\le \sigma \sqrt{2Inp}\right\}$ .

分别对应有 [15] ： $P\left(e\in B_1\right)\ge 1-\frac{1}{n}$ ； $P\left(e\in B_2\right)\ge 1-\frac{1}{2\sqrt{\pi Inp}}$ 。

可以看出高斯变量e高概率地位于集合 $B_1$ 和 $B_2$ 中，根据定理1以下定理显然成立。

定理2 若测量矩阵 $A\in R^{m\times n}$ 满足：

$k+s-\alpha \sqrt{k}>\left(k+s-\alpha \sqrt{k}\right){\delta }_{k+s}+\left(k+s+\alpha \left(\sqrt{2\left(k+s\right)}-\sqrt{k}\right)\right){\theta }_{k+s,k}$ ，

对于无约束优化问题(4)有如下结论 [15] ：

1) $x^{*}\left(l_2\right)$ 至少以 $P\left(e\in B_1\right)\ge 1-\frac{1}{n}$ 的概率满足：

$\begin{array}{c}{\Vert x^{*}\left(l_2\right)-x\Vert }_2\le \frac{2\sqrt{2\left(1+{\delta }_{k+s}\right)\left(n+2\sqrt{nInn}\right)}\sigma }{\left(k+s-\alpha \sqrt{k}\right)\left(1-{\delta }_{k+s}\right)-\left(k+s-\alpha \left(\sqrt{k}-\sqrt{2\left(k+s\right)}\right)\right){\theta }_{k+s,k}}\\ +\frac{2\sqrt{2\left(1+\frac{s}{k}\right)}{\theta }_{k+s,k}+2\sqrt{k+s}\left(1-{\delta }_{k+s}-{\theta }_{k+s,k}\right)}{\left(k+s-\alpha \sqrt{k}\right)\left(1-{\delta }_{k+s}\right)-\left(k+s-\alpha \left(\sqrt{k}-\sqrt{2\left(k+s\right)}\right)\right){\theta }_{k+s,k}}{\Vert r-r_{T_0}\Vert }_p\end{array}$ (19)

2) $x^{*}\left(DS\right)$ 至少以 $P\left(e\in B_2\right)\ge 1-\frac{1}{2\sqrt{\pi Inp}}$ 的概率满足：

$\begin{array}{c}{\Vert x^{*}\left(DS\right)-x\Vert }_2\le \frac{4\sqrt{Inp}{\left(k+s\right)}^{\frac{3}{2}}\sigma }{\left(k+s-\alpha \sqrt{k}\right)\left(1-{\delta }_{k+s}\right)-\left(k+s-\alpha \left(\sqrt{k}-\sqrt{2\left(k+s\right)}\right)\right){\theta }_{k+s,k}}\\ +\frac{2\sqrt{\frac{2}{k}}\left(k+s\right){\theta }_{k+s,k}+2\sqrt{k+s}\left(1-{\delta }_{k+s}-{\theta }_{k+s,k}\right)}{\left(k+s-\alpha \sqrt{k}\right)\left(1-{\delta }_{k+s}\right)-\left(k+s-\alpha \left(\sqrt{k}-\sqrt{2\left(k+s\right)}\right)\right){\theta }_{k+s,k}}{\Vert r-r_{T_0}\Vert }_p\end{array}$ . (20)

4. 小结

文章通过 $l_p-\alpha l_1\left(0<p<1,0<\alpha \le 1\right)$ 最小化的方法，将其与信号的部分已知支集结合起来，得到了该模型下信号恢复的一个更精确的条件，并且具体地给出了有界噪声、DS噪声及高斯噪声下的误差估计，对我们以后研究有关 $l_p-\alpha l_1$ 最小化模型下测量矩阵的性质非常有意义。目前关于该模型的下测量矩阵的其他性质研究较少，有待学者们进一步研究。

NOTES

^*通讯作者。