基于Landsberg-Vedral熵的噪声二值压缩感知恢复算法

Noisy 1-Bit Compressed Sensing Recovery Algorithm with Landsberg-Vedral Entropy

摘要: 在信号、图像及视频恢复领域，二值压缩感知(1-bit compressed sensing, 1BCS)近年来由于其采样和硬件实现上的优势而广受关注。然而，1BCS在应对符号翻转噪声或稀疏度/噪声水平先验信息难以获取等问题上依然具有挑战性。本文提出了基于Landsberg-Vedral熵的鲁棒广义不动点延拓算法(robust generalized fix point continuation, RGFPC)。一方面，RGFPC将不动点延拓(fix point continuation, FPC)系统与探测符号翻转位点的技术结合起来，进而使原始信号可以在没有稀疏度/噪声水平先验时由更新后的测量值被自适应地恢复。另一方面，我们从理论上证明了LV熵在稀疏增强和能量集中上的有效性，并将LV熵引入至我们的框架中，以此提升FPC系统的恢复性能。最后，我们测试了基于LV熵的RGFPC算法在虚拟信号和CT图像恢复上的有效性和优越性。

Abstract: In the field of signal, image, and video reconstruction, 1-bit compressed sensing (1BCS) has garnered significant attention in recent years due to its advantages in sampling and hardware implementation. However, 1BCS still faces challenges when dealing with issues such as sign-flip noise or difficulty in obtaining prior information on sparsity/noise levels. This paper proposes a robust generalized fixed-point continuation algorithm (RGFPC) based on Landsberg-Vedral entropy. On the one hand, RGFPC integrates the fix point continuation (FPC) system with a technique for detecting sign-flip positions, enabling the original signal to be adaptively recovered from the refined and updated measurements without prior knowledge of sparsity/noise levels. On the other hand, we theoretically demonstrate the effectiveness of LV entropy in sparse enhancement and energy concentration, and introduce LV entropy into our framework to improve the performance of the FPC system. Finally, we test the effectiveness and superiority of the RGFPC algorithm based on LV entropy in virtual signal and CT image reconstruction.

1. 引言

为满足复杂信息传输和重构方面日益增长的需求，一种强大的方法——压缩感知(compressed sensing, CS) [1]-[4]被提出并广泛应用于电子工程[5] [6]、地质勘探[7] [8]和医学成像[9] [10]等领域。CS首先透过精细采样并获得信号的线性测量，而后求解一个优化问题以从该测量值重建原始信号。然而，现有CS算法仍存在局限，如难以应对关键先验信息不可用等问题，本文将在此基础上进行讨论并给出一种解决方案。

数学上，压缩感知可求解欠定系统$y=\text{Φ}x\left(\text{Φ}\in {ℝ}^{M\times N},x\in {ℝ}^N,M\ll N\right)$ ，这里$x$ 是稀疏的，即$x$ 有很少的非零分量。在这个系统中，我们假定测量值可以遍布实数域上的任意一点，但受限于硬件和采样率，测量值必须被量化至有限集中的几个离散值。因此，在分布式计算和并行操作中，低水平量化甚至是二值量化(1-bit quantization)成为了一种流行的方法。受此启发，二值压缩感知(1-bit compressed sensing, 1BCS)在2008年提出[11]，并迅速引发研究热潮[12]-[15]。与传统CS不同，1BCS将测量值二值化，仅保留信号各分量的符号而忽略幅度信息，这种可以丢失信息的操作提升了采样率且降低了硬件需求。1BCS的无噪测量值可以表示为：

$y_{\text{noiseless}}=\text{sign}\left(\text{Φ}x\right),$

其中，“$\text{sign}$ ”表示作用于分量的符号函数，即当$x\ge 0$ 时$\text{sign}\left(x\right)$ 取值为1，否则取值为−1。在二值量化和传输过程中，受传感器故障、传输错误、数据缺省等影响，符号翻转噪声总是不可避免地产生。因此，受到噪声$\epsilon \in {ℝ}^N$ 影响的二值测量可等价表示为：

$y=\text{sign}\left(\text{Φ}x+\epsilon \right).$

本文将翻转噪声水平定义为${\left|y_{\text{noiseless}}-y\right|}_0/M$ ，其中${\left|\cdot \right|}_0$ 为零范数，表示向量中非零分量数，可描述稀疏度水平，而符号翻转水平描述了无噪测量和噪声测量间各位点发生不一致的概率。在不致引起误解时，本文所述噪声均为符号翻转噪声。

鲁棒二元迭代硬阈值(robust binary iterative hard thresholding, RBIHT) [16]和广义不动点延拓(generalized fix point continuation, GFPC) [17]因其算法设计的新颖性而受到我们的关注。RBIHT可以自适应地探测发生符号翻转的位点，因此信号可以在无噪声水平先验的情况下由修正的测量值进行恢复。然而，由于RBIHT使用了硬阈值算子，信号的稀疏度先验仍不可或缺。事实上，绝大多数恢复算法都需要稀疏度先验作为关键输入，而这在实际应用中常常难以获得。文献[18] [19]中证实了恰当方式加权的稀疏促进项比起未加权的版本有更优越的恢复性能，基于此想法，文献[17] [20]在理论和实际应用上对无需稀疏度先验的算法进行了有效的探索：提出了不动点延拓的推广版本——GFPC。该算法可以解决加权${\ell }_1$ 范数最小化问题，其中权重可正可负。具体而言，GFPC将负权重赋给信号的大幅分量以期增大，而给小幅分量分配正权重以期减小。比起在此前的工作中仅讨论了的正权重情形，可正可负的权重选择具有更好的稀疏增强性质。数学上，GFPC可解决如下${\ell }_1$ 范数最小化问题：

$\underset{x\in {ℝ}^N}{\text{min}}\lambda \psi \left(x\right)+\langle w,\left|x\right|\rangle ,$ (1)

其中，$\psi$ 为数据保真项，常选用单边${\ell }_1$ 范数$\psi \left(x\right)={{\displaystyle \sum }}_{i=1}^M\max \left\{0,-{\left[y\Phi x\right]}_i\right\}$ [21]；$w$ 表示各循环内的权重，它在文献[17]中由Shannon熵关于$\left|x\right|$ 的梯度进行更新。最小化Shannon熵被指出可以增强稀疏性，且恰好可以转化为形如(1)式的等价问题。这使得透过Shannon熵进行稀疏增强自然转化为可被GFPC解决的问题。显然，GFPC表现出对无需稀疏度先验的适应性。然而，当涉及符号翻转噪声，GFPC的性能不再令人满意。因此，本文将提出一种噪声自适应算法，并尝试使用更一般的Landsberg-Vedral熵(LV熵)来增强稀疏性。

1BCS中最早的鲁棒恢复算法是基于FPC [11]提出的RFPI，它使用单侧${\ell }_1$ 范数作为数据保真项来确保一致性。自此，1BCS恢复算法如雨后春笋般涌现。一种流行且成功的方法是BIHT [22] [23]。经验证，使用${\ell }_2$ 范数代替${\ell }_1$ 范数可以更好地抵抗噪声[22]，这让BIHT一度成为1BCS中最先进的算法。为更好地处理噪声，BIHT的衍生算法如AOP [24]、PIHT [25]和RBIHT [16]等，依次被提出并在不同程度上提高了BIHT的性能。但由于使用了硬阈值算子，它们对稀疏度先验的依赖仍无法解决，有些甚至需要噪声水平先验(见表1)，故在实际场景中难以应用。而我们的工作继承了GFPC与RBIHT在噪声场景中无需这些先验信息的优势，并取得了良好的恢复效果。

Table 1. Key prior information needed of the algorithms involved in this paper

表1. 本文涉及算法所需的关键先验信息

算法名称	稀疏度先验	噪声水平先验
BIHT-${\ell }_2$	需要	不需要
AOP	需要	需要
RBIHT	需要	不需要
PIHT	需要	-
PIHT-AOP	需要	不需要
GFPC	不需要	-
本文提出算法RGFPC	不需要	不需要

本文贡献如下：首先，我们证明了LV熵的稀疏增强和能量集中性质，以说明将LV熵引入GFPC模型的动机。另外，受文献[16]的启发，我们将一种无需噪声水平先验且能自适应探测符号翻转现象的机制纳入我们的算法中，称为鲁棒广义不动点迭代(robust generalized fix point continuation, RGFPC)。RGFPC继承了GFPC和RBIHT的优点，即不需要稀疏度和噪声水平先验，这是大多数噪声算法所不具备的(见表1)。最后，数值结果表明基于LV熵的RGFPC算法在实际性能上的优越性。我们将引理和命题的证明放在附录中。

2. LV熵模型建立及LV熵的性质

Landsberg-Vedral熵由Landsberg和Vedral在1998年共同提出[26]。由向量p-范数定义的离散情形的LV熵如下：

${\mathscr{H}}_{\text{LV}}\left(x|p,q\right):=\frac{1}{q-1}\left[\frac{1}{{{\displaystyle \sum }}_{i=1}^N{\left({\left|x_i\right|}^p/{\Vert x\Vert }_p^p\right)}^q}-1\right],$

其中，$x_i\ne 0,p>0$ ，非广延参数$q>0$ 且$q\ne 1$ 。事实上，当$q\to 1$ ，LV熵退化为Shannon熵：

${\mathscr{H}}_{\text{SE}}\left(x|p\right)=-{{\displaystyle \sum }}_{i=1}^N\frac{{\left|x_i\right|}^p}{{\Vert x\Vert }_p^p}\log \frac{{\left|x_i\right|}^p}{{\Vert x\Vert }_p^p}\left(x_i\ne 0\right).$

于是，LV熵可视为Shannon熵的推广。由于LV熵出色的稀疏增强和能量集中特性，本文考虑将最小化LV熵引入1BCS的模型中，这将有效提升重构性能(与Shannon熵相比)。我们的目标问题是最小化LV熵惩罚下的单边${\ell }_1$ 范数，即：

$\underset{x}{\min }\lambda {\displaystyle \sum _{i=1}^M\max \left\{0,-{\left[y\text{Φ}x\right]}_i\right\}}+{\mathscr{H}}_{\text{LV}}\left(x\right).$ (2)

下面，我们将介绍LV熵的两个特性：稀疏增强和能量集中，并讨论将其引入至模型(2)中的合理性和优越性。

2.1. 稀疏增强性

模型(2)中的LV熵可以视为稀疏性正则化器，这归功于其稀疏增强特性。下面对其无噪和噪声场景进行讨论。本节的关键结论是，对任意点$z^{*}\in {ℝ}^N$ 所在象限${\mathbb{O}}_{*}$ ，LV熵最小化问题的解仅落在该象限的边界上。

无噪情形：解决无噪1BCS问题，可以考虑求解

$\underset{x}{\min }{\mathscr{H}}_{LV}\left(x\right)\text{ s}\text{.t}\text{. }y=\text{sign}\left(\Phi x\right),y\ne 0.$ (3)

现对任意$z^{*}\in {ℝ}^N$ ，令$\mathcal{X}=\left\{x_1,x_2,\cdots \right\}$ 为$y=\text{sign}\left(\text{Φ}x\right)$ 在象限${\mathbb{O}}_{*}$ 中一部分解的解集，使得对任意 $x_i\ne x_j,x_i=\eta x_j$ 对某$\eta >0$ 成立。注意到对给定稀疏向量$x_0\in {ℝ}^N$ 及其二值无噪测量$y_0=\text{sign}\left(\text{Φ}{x}_0\right)$ ，所有满足$y_0=\text{sign}\left(\text{Φ}x\right)$ 的解分布在一个以零点为顶点、以$x_0$ 所在坐标轴为高的锥形内，故所有集合$\mathcal{X}$ 都落在该锥形限制在象限${\mathbb{O}}_{*}$ 中的区域。此外，由定义，相同一$\mathcal{X}$ 内的点拥有相等的LV熵函数值。下面给出的引理说明了从每个$\mathcal{X}$ 中可以挑选出唯一代表解与$\mathcal{X}$ 一一对应。

引理2.1. 给定某象限内任意$x_i\in \mathcal{X}$ ，总存在$\mathcal{X}$ 与${\tilde{x}}_i=x_i/{\Vert x_i\Vert }_p=\text{sign}\left(x_i\right)\frac{\left|x_i\right|}{{\Vert x_i\Vert }_p}$间的双射。

引理2.1所述的二维情形$\left(p=1\right)$ 示意图见图1(a)。其中集合$\mathcal{X}$ 中的所有点$x_i$ 的标准化都是${\tilde{x}}_i$ 。特别地，令$\mathcal{X}={\mathcal{X}}_1\cup {\mathcal{X}}_2$ 以及${\mathcal{X}}_1\cap {\mathcal{X}}_2=\varnothing$ ，其中${\mathcal{X}}_1$ 包含所有位于${\mathbb{O}}_{*}$ 边界上的解，而${\mathcal{X}}_2$ 包含其余解。显然${\mathcal{X}}_1$ 中点的稀疏性要高于${\mathcal{X}}_2$ 。由引理2.1，$\mathcal{X}$ 中的所有解都可映射到$\tilde{\mathcal{X}}=\widetilde{{\mathcal{X}}_1}\cup \widetilde{{\mathcal{X}}_2}$ 而$\widetilde{{\mathcal{X}}_1}\cap \widetilde{{\mathcal{X}}_2}=\varnothing$ 。下面的定理中，我们将证明象限${\mathbb{O}}_{*}$ 中对LV熵进行最小化都会得到$\widetilde{{\mathcal{X}}_1}$ 中的稀疏解。

定理2.1. 无噪1BCS中，对每个${\mathcal{X}}_2$ 中的解$x$ ，可以找到${\mathcal{X}}_1$ 中的解$x^{*}$ 使得${\mathscr{H}}_{\text{LV}}\left(x^{*}\right)<{\mathscr{H}}_{\text{LV}}\left(x\right)$ 。

证明. LV熵可被重新写成关于$\tilde{x}$ 的函数：

${\mathscr{H}}_{LV}\left(x\right)={\tilde{\mathscr{H}}}_{LV}\left(\tilde{x}\right):=\frac{1}{q-1}\left[\frac{1}{{{\displaystyle \sum }}_{i=1}^N{\tilde{x}}^{pq}}-1\right].$ (4)

(a) (b)

Figure 1. Schematic diagram of biunique of noiseless and noisy scenarios: Noiseless scenario; (b) Noisy scenario

图1. 无噪声和有噪声情况的双射示意图：(a) 无噪声情形；(b) 噪声情形

由文献[26]的定理9，$q>0$ 时，LV熵为Schur凹。因此，由于${\Vert \tilde{x}\Vert }_p=1$ 上在象限${\mathbb{O}}_{*}$ 边界上的点被其内部的点多数化(majorization)，且边界上的点必不是内部的点的置换(permutation)。故此时LV熵函数是严格Schur凹的，于是问题(3)的解一定会且只会落在象限${\mathbb{O}}_{*}$ 的边界上。因此，对任意$\tilde{x}\in {\tilde{\mathcal{X}}}_2$ ，我们总能找到${\tilde{x}}^{*}\in {\tilde{\mathcal{X}}}_1$ ，使得${\tilde{\mathscr{H}}}_{\text{LV}}\left({\tilde{x}}^{*}\right)<{\tilde{\mathscr{H}}}_{\text{LV}}\left(\tilde{x}\right)$。

又由引理2.1，既然可以建立$\mathcal{X}$ 与$\tilde{x}$ 间的双射，于是对每个$x\in {\mathcal{X}}_2$ ，总存在$x^{*}\in {\mathcal{X}}_1$ ，使得 ${\mathscr{H}}_{\text{LV}}\left(x^{*}\right)={\tilde{\mathscr{H}}}_{\text{LV}}\left({\tilde{x}}^{*}\right)<{\tilde{\mathscr{H}}}_{\text{LV}}\left(\tilde{x}\right)={\mathscr{H}}_{\text{LV}}\left(x\right)$。□

噪声情形：类似地，本部分中，我们考虑问题

$\underset{x}{\min }{\mathscr{H}}_{\text{LV}}\left(x\right)\text{s}\text{.t}\text{.}{d}_H\left(y,\text{sign}\left(\text{Φ}x\right)\right)<ϵ$ (5)

来解决带有符号翻转噪声的1BCS问题，其中$d_H\left(\cdot ,\cdot \right)$ 表示两向量间的标准Hamming距离。下面记 ${\mathcal{X}}^{ϵ}=\left\{x_1,x_2,\cdots \right\}$ 为问题(5)的解，且满足对任意$x_i\ne x_j,x_i=\eta x_j$ 对某个$\eta >0$ 成立。对给定向量及其带噪二值测量，问题(5)的所有可能解也分布在象限${\mathbb{O}}_{*}$ 中的一个锥形区域内，如图1(b)所示。该锥形区域比起无噪情形多出了黄色的部分，这包含了由符号翻转造成的有偏解。下面，我们将建立噪声情形下类似引理2.1的双射。

引理2.2. 给定任意$x_i\in {\mathcal{X}}^{ϵ}$ ，总可以建立集合${\mathcal{X}}^{ϵ}$ 与${\tilde{x}}_i=x_i/{\Vert x_i\Vert }_p$ 间的双射。

下面的定理描述了存在符号翻转噪声时，${\mathbb{O}}_{*}$ 内最小化LV熵也将得到${\mathcal{X}}_1^{ϵ}$ 内的稀疏解，其中，${\mathcal{X}}_1^{ϵ}$ 和${\mathcal{X}}_2^{ϵ}$ 的定义类似无噪情形。

定理2.2. 对任意${\mathcal{X}}_2^{ϵ}$ 中问题(5)的解$x$ ，总能在${\tilde{\mathcal{X}}}_1^{ϵ}$ 中找到解$x^{*}$ 使得${\mathscr{H}}_{\text{LV}}\left(x^{*}\right)<{\mathscr{H}}_{\text{LV}}\left(x\right)$ 。

引理2.2和定理2.2的证明与引理2.1和定理2.1类似，故略去。最后，我们以定理的形式给出象限${\mathbb{O}}_{*}$ 中LV熵函数最小值的位置情况。

定理2.3. 问题(3)和问题(5)的局部极小值只能出现在${ℝ}^N$ 中每个象限的边界上。

证明. 令$x^{\#}\in {ℝ}^N$ 为问题(3)和问题(5)在某象限${\mathbb{O}}_{*}$ 内部(非边界)的局部极小值。那么对任意$x^{\#}$ 的充分

小邻域$U\left(x^{\#}\right)$ 中的点$x$ ，其中邻域内的距离由$d_S\left(x,z\right):=\frac{1}{\text{π}}\arg \cos \langle x,z\rangle$ 定义，我们有${\mathscr{H}}_{\text{LV}}\left(x\right)\ge {\mathscr{H}}_{\text{LV}}\left(x^{\#}\right)$ 。由引理2.1和引理2.2，在无噪和噪声情形下，我们有

$x^{\#}\leftrightarrow {\tilde{x}}^{\#},U\left(x^{\#}\right)\leftrightarrow U\left({\tilde{x}}^{\#}\right)$

在某象限${\mathbb{O}}_{*}$ 内部成立，于是对于任意$\tilde{x}\in U\left({\tilde{x}}^{\#}\right)$ ，${\tilde{\mathscr{H}}}_{\text{LV}}\left(\tilde{x}\right)\ge {\tilde{\mathscr{H}}}_{\text{LV}}\left({\tilde{x}}^{\#}\right)$，即${\tilde{x}}^{\#}$ 是${\Vert \tilde{x}\Vert }_p=1$ 上且在${\mathbb{O}}_{*}$ 内部的局部极小值点(见图2)。然而，${\tilde{\mathscr{H}}}_{\text{LV}}\left(\tilde{x}\right)$在${\Vert \tilde{x}\Vert }_p=1$ 上关于$\tilde{x}$ 严格凹(参考定理2.1证明中的论述)，即上述的${\tilde{x}}^{\#}$ 并不存在。

于是，可以得出问题(3)和(5)的局部极小值只能出现在${ℝ}^N$ 中每个象限的边界上，或者说象限${\mathbb{O}}_{*}$ 中最小化LV熵函数的局部极小值只能出现在其边界上。□

Figure 2. 双射$x^{\#}\leftrightarrow {\tilde{x}}^{\#}$ 和$U\left(x^{\#}\right)\leftrightarrow U\left({\tilde{x}}^{\#}\right)$

图2. Biunique $x^{\#}\leftrightarrow {\tilde{x}}^{\#}$ and $U\left(x^{\#}\right)\leftrightarrow U\left({\tilde{x}}^{\#}\right)$

总而言之，我们证明了在无噪和噪声1BCS背景下，象限${\mathbb{O}}_{*}$ 中LV熵函数的局部极小值只会出现在边界上。因此，包含LV熵惩罚项的模型(2)的解也相应具有天然的稀疏性。

2.2. 能量集中性

接下来，我们将介绍LV的能量集中特性，这是其他熵函数通常不具备的，并表明最小化LV熵函数将导致能量集中到一些重要分量中。

我们考虑使用梯度下降求解${\mathbb{O}}_{*}$ 中的LV熵最小化问题。于是更新方程可写为：

$x\leftarrow x-\gamma \cdot \text{sign}\left(x\right)\cdot \nabla {\mathscr{H}}_{\text{LV}}\left(\left|x\right|\right),$ (6)

其中，$\gamma$ 为步长，$\nabla {\mathscr{H}}_{\text{LV}}\left(\left|x\right|\right)$ 表示LV熵函数关于$\left|x\right|$ 的梯度。通过下面的命题，我们将介绍LV熵函数的能量集中性质。

命题2.1. 1) 对于在象限${\mathbb{O}}_{*}$ 中的LV熵函数，有：

$\frac{\partial {\mathscr{H}}_{\text{LV}}\left(\left|x\right|\right)}{\partial \left|x_i\right|}\{\begin{array}{c}\begin{array}{cc}<0,& \left|x_i\right|>\kappa ,\end{array}\\ \begin{array}{cc}=0,& \left|x_i\right|=\kappa ,\end{array}\\ \begin{array}{ll}>0,\hfill & \left|x_i\right|<\kappa ,\hfill \end{array}\end{array}$

其中，$\kappa =\text{exp}\left[\frac{1}{q\left(p-1\right)}\log \frac{{\Vert x\Vert }_{pq}^{pq}}{{\Vert x\Vert }_p^p}\right]$ 。

2) $\langle \left|x\right|,\nabla {\mathscr{H}}_{\text{LV}}\left(\left|x\right|\right)\rangle =0$ 。

由命题2.1-1)，在梯度下降方程(6)中，LV熵的梯度将负能量分配给幅值较大的分量，反之则将正能量分配给幅值较小的分量。由命题2.1-2)，下降过程将在精确收敛时停止。因此，能量通过LV熵集中在重要分量中，而其他一些正则化器通常不具备这种能量集中特性。

3. 基于LV熵的鲁棒广义不动点延拓算法

在上节中给出了本文的重建模型(2)，由于它是非凸的，我们将LV熵稀疏惩罚项变形如下：

$\begin{array}{c}\nabla {\mathscr{H}}_{LV}\left(\left|x\right|\right)\le {\mathscr{H}}_{LV}\left(\left|x_{\left(k\right)}\right|\right)+\left|x\right|-\langle \left|x_{\left(k\right)}\right|,\nabla {\mathscr{H}}_{LV}\left(\left|x_{\left(k\right)}\right|\right)\rangle \\ ={\mathscr{H}}_{LV}\left(\left|x_{\left(k\right)}\right|\right)-\langle \left|x_{\left(k\right)}\right|,\nabla {\mathscr{H}}_{LV}\left(\left|x_{\left(k\right)}\right|\right)\rangle +\langle \left|x\right|,\nabla {\mathscr{H}}_{LV}\left(\left|x_{\left(k\right)}\right|\right)\rangle ,\end{array}$

其中，$x_{\left(k\right)}$ 是任意点，$\left|x\right|,\nabla {\mathscr{H}}_{LV}\left(\left|x_{\left(k\right)}\right|\right)$ 为LV熵稀疏惩罚项的等价替代。于是，我们的模型转化为：

$\underset{x}{\min }\lambda {\displaystyle \sum _{i=1}^M\max \left\{0,-{\left[y\text{Φ}x\right]}_i\right\}}+\langle \left|x\right|,\nabla {\mathscr{H}}_{\text{LV}}\left(\left|x_k\right|\right)\rangle ,$

其中，单边${\ell }_1$ 范数为数据保真项，它的梯度计算为$g\left(x\right)={\text{Φ}}^{\text{T}}\left(\text{sign}\left(\text{Φ}x\right)-y\right)$ 。

下面使用本文提出的鲁棒广义不定点延拓(RGFPC)算法求解以上模型。RGFPC算法可分为两部分。1) 内循环：固定$\text{Λ}$ ，使用GFPC方法求解以下问题中的$x$ ：

$\widehat{x}=\underset{x}{\text{argmin}}\lambda {\displaystyle \sum }_{i=1}^M\max \left\{0,-\left(y\odot \text{Λ}\right)\text{Φ}x\right\}+\langle \nabla {\mathscr{H}}_{\text{LV}}\left(x\right),\left|x\right|\rangle .$

2) 外循环：通过(7)式更新梯度权重，并通过

${\text{Λ}}_i=\{\begin{array}{ll}-1,\hfill & c_i>\delta r,\hfill \\ 1,\hfill & c_i\le \delta r,\hfill \end{array}$

更新$\text{Λ}$ ，其中$r$ 为当前内循环的迭代数，$\delta$ 是控制内循环中不一致数量的比例阈值，此外，考虑到算法收敛性，我们令${\text{Λ}}_i=-1$ 如果$c_i=\max \left\{c_i:i\in \left[M\right]\right\}\le \delta r$ 。

在处理符号翻转噪声时，优先关注的是翻转发生的位点，这正是上述外循环中执行的任务。然而在噪声环境中，我们考虑直接丢弃被翻转的测量以优化算法。该策略显著降低了计算和存储需求，随着迭代的进行，测量所携带的有用信息量自然会减少，但这种减少通常不会显著影响整体恢复性能，这点在后续实验中得到了验证。

综上，本文提出的基于LV熵的RGFPC可视作一个内–外循环嵌套的恢复算法，具体结构见算法1。

Algorithm 1. RGFPC-LV algorithm

算法1. RGFPC-LV算法

输入：带噪测量$y\in {\left\{-1,1\right\}}^M$ ；比例阈值$\delta$ ；测量矩阵$\text{Φ}$ 。 初始化：计数$k\leftarrow 0$ ；下降步长$\tau$ ；松弛参数$\lambda$ 。 重复： 计数：$r\leftarrow 0$ ；$k\leftarrow k+1$ ； 初始种子：$x_{\left(k=0\right)}$ ； 梯度下降：$h^{\left(r=0\right)}\leftarrow x_{\left(k-1\right)}-\tau g\left(x_{\left(k-1\right)}\right)$ ； 新问题建立：$x_{\left(k\right)}^{\left(r=0\right)}\leftarrow h^{\left(r=0\right)}$ ；$w_k\leftarrow \nabla {\mathscr{H}}_{\text{LV}}\left(\left|x_{\left(k\right)}^{\left(r=0\right)}\right|\right)$ ； 翻转记录：$c\leftarrow 0_M$ ； 重复： 计数：$r\leftarrow r+1$ ； 计算：$\{\begin{array}{l}{t}_0^{\left(r-1\right)}=\text{max}\left\{\text{sign}\left(w_k\right),W\left(x_{\left(k\right)}^{\left(r\right)}\right)\right\};\\ t_1^{\left(r-1\right)}=\text{sign}\left(x_{\left(k\right)}^{\left(r\right)}\odot \text{sign}\left(x_{\left(k\right)}^{\left(r\right)}-\tau g\left(x_{\left(k\right)}^{\left(r\right)}\right)\right)\right);\\ t_t^{\left(r-1\right)}=\text{max}\left\{t_1^{\left(r-1\right)},\text{sign}\left(w_k\right)\right\};\end{array}$ 收缩：$u_{\left(k\right)}^{\left(r\right)}\leftarrow t_t^{\left(r-1\right)}\odot \text{sign}\left(h^{\left(r-1\right)}\right)\odot \text{max}\left[\min \left[t_0,t_t\right]\odot \left|h^{\left(r-1\right)}\right|-\frac{\tau }{\lambda }{w}_k,0\right]$ ； 翻转记录：$ℐ\leftarrow \left\{i\in \left[M\right]:y_i\odot {\left(\text{Φ}{u}_{\left(k\right)}^{\left(r\right)}\right)}_i<0\right\}$ ；$c_{ℐ}\leftarrow c_{ℐ}+1$ ； 正则化：$u_{\left(k\right)}^{\left(r\right)}\leftarrow u_{\left(k\right)}^{\left(r\right)}/{\Vert u_{\left(k\right)}^{\left(r\right)}\Vert }_2$ ； 梯度下降：$h^r\leftarrow x_{\left(k\right)}^{\left(r\right)}-\tau g\left(x_{\left(k\right)}^{\left(r\right)}\right)$ ； 直至 停止条件满足。 锁定翻转符号位点：$\mathcal{S}\leftarrow \left\{i\in \left[M\right]:c_i>\delta r\right\}$ ；$ℳ\leftarrow \left\{i\in \left[M\right]:c_i=\left\{\max c_j:j\in \left[M\right]\right\}\right\}$ ； 丢弃翻转测量： 若$\mathcal{S}\ne \varnothing$ ，则$y\leftarrow y_{\left[M\right]\backslash \mathcal{S}},M\leftarrow \left|\left[M\right]\backslash \mathcal{S}\right|,\text{Φ}\leftarrow \text{Φ}\left[\left[M\right]\backslash \mathcal{S}:\cdot \right]$ ； 否则$y\leftarrow y_{\left[M\right]\backslash ℳ},M\leftarrow \left|\left[M\right]\backslash ℳ\right|,\text{Φ}\leftarrow \text{Φ}\left[\left[M\right]\backslash ℳ:\cdot \right]$ ； 直至 停止条件满足。 输出：$\widehat{x}\leftarrow u_{\left(k\right)}^{\left(r\right)}$ 。

4. 数值模拟实验

为了直观体现所提出算法的优势，本节将RGFPC-LV算法应用于多倍体染色体图像及灰度图像的噪声恢复中，并与BIHT [22]、AOP [24]、RBIHT [16]、PIHT和PIHT-AOP [25]算法进行对比。我们主要考虑两个统计指标：峰值信噪比(PSNR)和结构相似性(SSIM)，定义为：

$\text{PSNR}=10\log \frac{{255}^{2}mn}{{{\displaystyle \sum }}_{i=0}^{m-1}{{\displaystyle \sum }}_{j=0}^{n-1}\left(P\left(i,j\right)-Q\left(i,j\right)\right)},\text{SSIM}=\frac{\left(2{\mu }_P{\mu }_Q+a\right)\left(2{\sigma }_{PQ}+b\right)}{\left({\mu }_P^2+{\mu }_Q^2+a\right)\left({\mu }_P^2+{\mu }_Q^2+b\right)},$

其中，$P$ 和$Q$ 均为$m\times n$ 维单通道图像，${\mu }_P,{\mu }_Q,{\mu }_P^2,{\mu }_Q^2$ 分别表示其均值及方差，${\sigma }_{PQ}$ 表示$P$ 和$Q$ 的协方差，$a$ 、$b$ 为稳定性常数。由定义可知，PSNR和SSIM值越高，图像恢复质量越好。此外。我们将实验过程中的部分参数设定如下：

• 初始种子$x_{\left(k=0\right)}$ 为Moore-Penrose伪逆${\text{Φ}}^{\text{T}}{\left({\text{ΦΦ}}^{\text{T}}\right)}^{†}y$ 。

• 对于松弛参数$\lambda$ ，以较小的$\lambda$ 开启算法，当迭代趋于收敛，再以${\lambda }_{r+1}=c{\lambda }_r\left(c>1\right)$ 更新$\lambda$ 。

• 对于LV熵中参数$p,q$ ，我们选取四组值进行实验：1) $p=q=1$ ；2) $p=1,q=2$ ；3) $p=2,q=1$ ；4) $p=q=2$ 。注意$q=1$ 时LV熵退化为Shannon熵。

• 采样比和噪声水平分别设置为10%和8%。

染色体图像：本实验中的图像来自10张显微镜下秋水仙素处理后的多倍体大蒜根尖染色体，我们变更其尺寸为256 × 256。我们对其施以8%、14%和20%三个水平的符号翻转噪声，9种方法重构的10张图像的平均PSNR及平均SSIM值见表2。可以看出，我们的方法在不同噪声水平下比起其他方法均达到了最佳数值结果，具体而言，PSNR和SSIM值比起PIHT-AOP有至少3 dB和0.03的提升。从图像恢复细节上看(见图3，施以8%翻转噪声)，RGFPC-LV方法恢复的图像在细节上更清晰，雪花更少，恢复性能更优，这有助于科研人员对染色体加倍情况作出准确判断。

Figure 3. Chromosome images of polyploid garlic root tip cells reconstructed by 9 methods

图3. 9种方法恢复的多倍体大蒜根尖细胞染色体图像

Table 2. Values of PSNR and SSIM of reconstructions by 9 algorithms under different noisy conditions

表2. 9种算法在不同噪声水平下的PSNR及SSIM值

图像	算法	噪声水平：8%		噪声水平：14%		噪声水平：20%
		PSNR	SSIM	PSNR	SSIM	PSNR	SSIM
染色体 图像	BIHT-${\ell }_2$	30.9156	0.7895	29.6128	0.7697	27.3162	0.7440
	PIHT	30.6374	0.7963	28.3192	0.7983	26.9317	0.7816
	AOP	31.3095	0.8676	30.0011	0.8596	28.3643	0.8342
	RBIHT	34.7710	0.9179	33.4676	0.8926	31.0169	0.8830
	PIHT-AOP	33.1903	0.9263	32.8241	0.8836	30.9261	0.8953
	Shannon (p = 1)	33.0027	0.9192	32.7663	0.9030	30.9782	0.8847
	Shannon (p = 2)	34.4923	0.9241	32.8702	0.9079	31.3179	0.8962
	LV (p = 1, q = 2)	36.1645	0.9496	35.2902	0.9383	33.1642	0.9208
	LV (p = 2, q = 2)	37.6152	0.9533	36.6154	0.9526	35.7745	0.9503

续表

灰度 图像	BIHT-${\ell }_2$	24.0061	0.6915	23.1362	0.6822	21.8631	0.6623
	PIHT	23.8138	0.7405	22.5392	0.7201	22.1844	0.7164
	AOP	27.6517	0.7611	25.1852	0.7425	24.2528	0.7336
	RBIHT	30.1526	0.8165	28.1665	0.7852	27.1981	0.7721
	PIHT-AOP	31.9158	0.8792	29.1582	0.8320	27.1682	0.7923
	Shannon (p = 1)	32.2610	0.8903	29.3762	0.9347	29.0085	0.8165
	Shannon (p = 2)	33.9508	0.9061	31.3672	0.8763	30.2691	0.8652
	LV (p = 1, q = 2)	34.1365	0.9158	32.1461	0.8820	30.8596	0.8755
	LV (p = 2, q = 2)	34.9373	0.9318	33.6121	0.9123	31.1857	0.8972

灰度图像：本实验使用现实中摄制的10张灰度图像作为恢复对象，同样变更其尺寸为256 × 256并施以8%、14%和20%的噪声，并将其被9种方法重建的平均PSNR及平均SSIM值记录在表2中，将视觉展示呈现在图4中。现实图像包含复杂的纹理信息，但RGFPC-LV算法仍然拥有优于其他方法至少3 dB和0.05的PSNR和SSIM优势。从图像细节上看，在噪点、亮度和纹理细节方面，RGFPC-LV恢复的灰度图像与原始图像更加贴合。

Figure 4. Real scene greyscale images reconstructed by 9 methods

图4. 9种方法恢复的真实场景灰度图像

综上，在噪声图像恢复方面，RGFPC-LV的恢复性能更佳，在数值评估和视觉呈现上比起其他方法均展示出明显优势。

5. 总结与展望

本文给出了LV熵在无噪和噪声条件下稀疏增强和能量集中特性的理论保证，并将LV熵惩罚问题引入至1BCS中。我们提出了单边${\ell }_1$ 范数限制下的LV熵最小化模型，并采用已有的GFPC方法进行求解。进一步，考虑到二值测量过程中可能受符号翻转噪声的影响，我们提出了RGFPC算法。该算法可以自适应探测受噪声影响的测量，且无需稀疏度和噪声水平先验。在噪声图像恢复中，我们的方法表现出优秀的性能。未来工作中，我们将考察更多可能的熵函数来增强稀疏性，并试图找到重构的理论误差界等。

附 录

A.1. 引理2.1的证明

证明：首先，对任意$x_j\in \mathcal{X}\backslash x_i$ ，${\tilde{x}}_i=\frac{x_i}{{\Vert x_i\Vert }_p}=\frac{\eta x_j}{{\Vert \eta x_j\Vert }_p}=\frac{x_j}{{\Vert x_j\Vert }_p}={\tilde{x}}_j$ 。因此，$x_j\to {\tilde{x}}_i$ ，于是得到$\mathcal{X}\to {\tilde{x}}_i$ 。下面假设两不同集合${\mathcal{X}}_{\left[1\right]}$ 和${\mathcal{X}}_{\left[2\right]}$ 可被映射至同一点${\tilde{x}}_i$ 。不失一般性，设$x_1\in {\mathcal{X}}_{\left[1\right]}$ ，以及$x_2\in {\mathcal{X}}_{\left[2\right]}$ 。于是对于某${\eta }_1,{\eta }_2,{\eta }_3>0$ ，

$\frac{x_1}{{\Vert x_1\Vert }_p}=\frac{{\eta }_1{x}_1}{{\Vert {\eta }_1{x}_1\Vert }_p}={\tilde{x}}_i=\frac{{\eta }_2{x}_2}{{\Vert {\eta }_2{x}_2\Vert }_p}=\frac{x_2}{{\Vert x_2\Vert }_p}$

成立，于是有$x_1=\frac{{\Vert x_1\Vert }_p}{{\Vert x_2\Vert }_p}{x}_2:={\eta }_3{x}_2$ 。故$x_1$ 与$x_2$ 同属一个集合，即${\mathcal{X}}_{\left[1\right]}={\mathcal{X}}_{\left[2\right]}$ ，得到${\tilde{x}}_i\to \mathcal{X}$ 。(证毕)

A.2. 命题2.1的证明

证明：1) 首先，LV熵关于$\left|x\right|$ 的梯度计算如下：

$\begin{array}{c}\frac{\partial {\mathscr{H}}_{\text{LV}}\left(\left|x\right|\right)}{\partial \left|x_i\right|}=\frac{pq}{1-q}\frac{\partial }{\partial \left|x_i\right|}\left(\frac{{\Vert x\Vert }_p^{pq}}{{\Vert x\Vert }_{pq}^{pq}}-1\right)\\ =\frac{pq}{1-q}\frac{{\left|x_i\right|}^{p-1}{\Vert x\Vert }_p^{p\left(q-1\right)}}{{\Vert x\Vert }_{pq}^{pq}}-\frac{{\left|x_i\right|}^{pq-1}{\Vert x\Vert }_p^{pq}}{{\Vert x\Vert }_{pq}^{2pq}}\\ =\frac{pq}{1-q}\frac{{\left|x_i\right|}^{pq-1}{\Vert x\Vert }_p^p-{\left|x_i\right|}^{p-1}{\Vert x\Vert }_{pq}^{pq}}{{\Vert x\Vert }_p^{2pq}}.\end{array}$ (7)

注意$p>0$ ，于是当$0<q<1$ (或$q>1$ )时，由上式，

$\begin{array}{l}\frac{\partial {\mathscr{H}}_{\text{LV}}\left(\left|x\right|\right)}{\partial \left|x_i\right|}\le 0\\ \iff \frac{{\left|x_i\right|}^{pq-1}{\Vert x\Vert }_p^p-{\left|x_i\right|}^{p-1}{\Vert x\Vert }_{pq}^{pq}}{1-q}\le 0\\ \iff {\left|x_i\right|}^{p\left(q-1\right)}\le (\ge ){\Vert x\Vert }_{pq}^{pq}/{\Vert x\Vert }_p^p\\ \iff p\left(q-1\right)\log \left|x_i\right|\le (\ge )\log \left({\Vert x\Vert }_{pq}^{pq}/{\Vert x\Vert }_p^p\right)\\ \iff \left|x_i\right|\ge \exp \left[\frac{1}{p\left(q-1\right)}\log \frac{{\Vert x\Vert }_{pq}^{pq}}{{\Vert x\Vert }_p^p}\right]\text{:}=\kappa .\end{array}$

2) 由(7)式，

$\begin{array}{c}\langle \left|x\right|,\nabla {\mathscr{H}}_{\text{LV}}\left(\left|x\right|\right)\rangle =\frac{pq}{1-q}{\displaystyle \sum _{i=1}^N\frac{{\left|x_i\right|}^{pq}{\Vert x\Vert }_p^p-{\left|x_i\right|}^p{\Vert x\Vert }_{pq}^{pq}}{{\Vert x\Vert }_p^{2pq}}}\\ =\frac{pq}{1-q}\frac{{\Vert x\Vert }_{pq}^{pq}{\Vert x\Vert }_p^p-{\Vert x\Vert }_p^p{\Vert x\Vert }_{pq}^{pq}}{{\Vert x\Vert }_p^{2pq}}\\ =0,\end{array}$

这样我们便完成了证明。(证毕)

NOTES

^*通讯作者。