基于部分高斯循环矩阵的带噪1-Bit分布式压缩感知

Noisy 1-Bit Distributed Compressed Sensing with Partial Gaussian Circulant Matrices

摘要: 在过去大多数的研究中，带噪1-bit分布式压缩感知局限于使用高斯随机测量矩阵进行信号的重构。但是，这类矩阵内存消耗大，计算速度慢，阻碍了实际应用的发展。因此，作为改进，本文考虑将结构化的部分高斯循环矩阵应用于带噪1-bit分布式压缩感知当中。部分高斯循环矩阵可以通过快速傅里叶变换显著降低计算复杂度，提高恢复效率。为此，我们提出了新的鲁棒1-bit分布式压缩感知恢复算法。该算法通过计算符号不一致的数量，可以自适应地检测到符号翻转的位置，并进行修正。数值实验表明，在存在测量噪声和传输噪声的情况下，部分高斯循环矩阵和高斯随机矩阵的恢复性能相当。在此基础上，部分高斯循环矩阵的恢复时间更短，重构效率更高。

Abstract: In most previous studies, noisy 1-bit distributed compressed sensing has been limited to the use of Gaussian random measurement matrices for signal reconstruction. However, such matrices consume significant memory and have slow computational speeds, which hinder the development of their practical application. Therefore, as an improvement, this paper considers the application of structured partial Gaussian circulant matrices to noisy 1-bit distributed compressed sensing. Partial Gaussian circulant matrices can significantly reduce computational complexity and improve recovery efficiency through fast Fourier transform. To this end, we propose a new robust 1-bit distributed compressed sensing recovery algorithm. This algorithm can adaptively detect and correct sign flip positions by calculating the number of sign inconsistencies. Numerical experiments demonstrate that, in the presence of measurement noise and transmission noise, the recovery performance of partial Gaussian circulant matrices is comparable to that of Gaussian random matrices. Furthermore, the recovery time of partial Gaussian circulant matrices is shorter, and the reconstruction efficiency is higher.

1. 引言

压缩感知(Compressed Sensing, CS) [1]是一种高效的信号采集与恢复技术，它克服了传统奈奎斯特采样定理[2]的限制。目前，CS技术已经广泛应用于雷达成像[3]、磁共振成像[4]、遥感[5]等领域。在CS中，目标是从线性测量值中恢复一个未知的s-稀疏信号$x\in R^N$ ，即信号x具有s个非零元素，测量值由以下公式给出：

$y=Ax$ ，

其中，$A\in R^{m\times N}$ 为测量矩阵且$m\ll N$ 。常用的测量矩阵为高斯随机矩阵，因其满足限制性等距性质，可确保信号的重构精度较高。但是，高斯随机矩阵占用的内存大，计算复杂度较高，特别是在大规模问题中，这往往不利于实际的应用。因此，研究者对结构化的测量矩阵展开了探索，该类矩阵可以与向量进行高效的元素乘积，显著提高恢复效率，比如托普利兹结构矩阵[6]、部分循环矩阵[7]。

大多数的实际信号传输过程中，往往是多个信号同时到达处理器，比如分布式网络[8]、联合稀疏模式恢复[9]。所以，Baron等首次提出分布式压缩感知(Distributed Compressed sensing, DCS) [10]，即每个信号先独立地通过测量矩阵采样与压缩，然后在解码端进行联合重构。假设$x_1,\cdots ,x_L$ 是一组L个N维稀疏信号且有着共同支撑。$A^{\left(1\right)},\cdots ,A^{\left(L\right)}$ 为L个不同的测量矩阵。那么，DCS的数学模型为：

$vec\left(Y\right)=Avec\left(X\right)$ ，

其中，$X\in R^{N\times L}$ 和$Y\in R^{m\times L}$ 分别表示信号和相应的测量值通过按列排列的方式组成的矩阵，$A\in R^{mL\times NL}$ 是一个由不同的块$A^{\left(1\right)},\cdots ,A^{\left(L\right)}$ 组成块对角矩阵，$vec(\cdot )$ 表示矩阵的向量化。在实际应用过程中，容易发生符号翻转。Sundman等[11]基于联合信号的稀疏性提出了联合正交匹配追踪算法和联合子空间追踪算法针对分布式压缩感知进行鲁棒恢复。但这两个算法假设信号的稀疏性是已知的，而一般情况下稀疏性不能作为先验信息，所以Wang等[12]在保证算法的恢复精度下，提出的分布式压缩感知稀疏自适应匹配追踪算法适用于稀疏性未知的情况。在这些算法当中，使用的测量矩阵为高斯矩阵。

在实际的信号处理过程中，考虑到存储大小和计算效率的重要性，需要对收集到的测量值进行量化，也就是将连续值转换为在某个范围内的离散值。具体来说，我们需要从量化后的测量值$Q\left(Ax\right)$ ，其中$Q(\cdot )$ 是一个把N维的向量映射到有限位数集合的量化器。测量值的转换增强了储存和运输的适用性，并提高了实施的便利性和操作的快捷性。特别地，Boufounos等首次在压缩感知中结合了一种极端的粗糙量化，提出了1-bit压缩感知(1-bit Compressed Sensing, 1-bit CS) [13]，即只捕捉信号的符号信息，而忽略了尺度信息，从而大大减少了比特数，显著提高了量化速度。1-bit CS的数学模型为：

$y=sign\left(Ax\right)$ ，

其中，$sign(\cdot )$ 为符号算子，即如果$\langle a_i,x\rangle \ge 0$ ，$y_i=1$ ；反之，$y_i=-1$ ，其中$a_i$ 为测量矩阵A的第i行。然而，在噪声干扰下，一些符号测量值可能会发生翻转，这会严重影响恢复算法的重构精度。基于此，Yan等[14]提出了自适应离群追踪算法，不需要考虑信号的稀疏性，通过设置停止条件检测到符号翻转的位置。Movahed等[15]在重归一化定点迭代算法中嵌入了类似的检测技术，以提高噪声环境下的信号恢复精度。但是这两类算法都需要提前设置好符号翻转的个数，而这在实际过程中很难获得。所以，Fu等[16]提出了鲁棒二进制迭代硬阈值(Robust Binary Iterative Hard Dhresholding, RBIHT)算法，不需要噪声水平作为先验条件。除此之外，该作者应用的异常检测技术是通过计算不一致的数量找到符号翻转的位置。在这些算法中，测量矩阵仍然是考虑高斯矩阵。但是，由于在1-bit CS中需要进行过采样，高斯随机矩阵存在的计算速度较慢和存储较大等问题比在CS中更加明显。一些学者积极地探索和讨论在存在噪声时的其他测量算子。Dirksen和Mendelson [17]使用部分循环矩阵，基于相关性的算法和L2-规范正则化，提出了带噪1-bit CS恢复信号时的最佳采样复杂度估计。Liu等[18]将鲁棒1-bit CS和深度学习中的生成先验结合起来，在理论上证明了部分循环高斯矩阵下的鲁棒1-bit CS重构所需的测量数与高斯矩阵相当，并通过实验证明了部分高斯循环矩阵可以显著地降低计算复杂度，提高恢复效率。

在本文中，我们考虑1-bit分布式压缩感知(1-bit Distributed Compressed Sensing, 1-bit DCS)，也就是将1-bit量化应用到传统的DCS中。在无线感知网络[19]、联邦学习[20]和分布式MIMO系统[21]等领域，1-bit DCS已得到广泛应用。而在实际情况中，往往会存在噪声干扰。所以，Zayyani等[22]提出了稀疏一位扩散阶梯下降算法，通过优化成本函数恢复信号，且该算法在带噪1-bit DCS中有着较好的鲁棒性，并且对信号有着显著的恢复效果。Yang等[23]提出了M-AOP-e算法，该算法巧妙地设计了停止准则，可以有效地进行信号重构。与前面一样，这些算法依旧考虑使用高斯矩阵。然而现有的高斯矩阵过于单一，妨碍了实际应用，因此有必要扩展新的测量矩阵。

基于以上讨论，我们将在本文中探讨部分高斯循环矩阵在带噪1-bit DCS中的应用。部分高斯循环矩阵因其结构的独特性，在与向量进行乘积时，可以通过快速傅里叶变换高效计算，大大降低计算复杂度，具有更重要的实际意义。受到[16]的启发，我们提出了一种新的重构算法——D-RBIHT，该算法不需要将符号翻转的数量作为前提条件。实验结果表明，在相同的噪声环境和测量条件下，部分高斯循环矩阵和高斯矩阵有着不相上下的重构性能。更进一步地，部分高斯循环矩阵的恢复时间明显短于高斯矩阵，说明部分高斯循环矩阵在计算速度上要优于高斯矩阵，具有更高的重构效率，能更好地减少恢复成本。

2. 模型及恢复算法

在本节中，我们介绍需要恢复的噪声模型和展示重构算法的详细步骤。

在存在噪声干扰时，我们关注两种噪声。第一种是测量噪声，即在测量过程中可能会导致一些相反的结果；第二种是传输噪声，指的是信号在通过传输通道时，某些位置可能会发生符号翻转。经过一系列信号的处理过程，我们得到已被污染的测量值：

$y=sign\left(sign\left(Ax+e\right)+n\right)$ ，(1.1)

其中，$e\in R^{mL}$ 、$n\in R^{mL}$ 分别是测量噪声和传输噪声。模型中，$x=vec\left(X\right)={\left(x_1,\cdots ,x_L\right)}^{\text{T}}$ ， $y=vec\left(Y\right)={\left(y_1,\cdots ,y_L\right)}^{\text{T}}$ 和$A\in R^{mL\times NL}$ 为块对角部分高斯循环矩阵即所有的块$A^{\left(1\right)},\cdots ,A^{\left(L\right)}$ 为部分高斯循环矩阵。除此之外，我们需要定义可应用的信号集，

$V_{\left(s,L\right)}=\left\{v=vec\left(V\right):V=\left(v_1,\cdots ,v_L\right)\in R^{m\times L},\left|supp\left(V\right)\right|\le s,{\Vert v_l\Vert }_2={\Vert v\Vert }_{2,1}/L\right\}$ ，

其中，$supp\left(V\right)$ 表示信号集$V_{s,L}$ 的支撑，即非零行的个数。在本文中，我们将通过设计合理的恢复算法从带噪1-bit DCS模型(1.1)中重构原始信号，并与高斯测量的结果进行对比，突出部分高斯循环矩阵在计算效率上的显著差别。接下来，我们将介绍本文的算法——D-RBIHT。该算法是在原有的RBIHT上经过适当且可广泛应用的拓展后，用在联合恢复信号的问题上。在D-RBIHT中，我们利用与RBIHT一样的异常检测技术，记录在多次迭代过程中出现不一致的位置。$reshape\left(\cdot ,N,L\right)$ 是指将一个向量$x\in R^{NL}$ 转换为一个$N\times L$ 的矩阵，梯度下降步长$\mu >0$ 且需根据算法的实际情况进行选择。$\eta (\cdot )$ 是硬阈值算子，在该算法的设置中，用于保留一个矩阵前s行中2-范数最大的行，并将剩下的行置于零。$\delta$ 为比例因子。如果测量值中的某个位置不一致的次数超过了由$\delta$ 计算的给定阈值，那么我们将认为该位置发生了符号翻转。算法1展示了更多的细节。

Algorithm 1. D-RBIHT algorithm

算法1. D-RBIHT算法

输入：测量矩阵$A\in R^{mL\times NL}$ ，1-bit量化值$y\in R^{mL}$ ，步长$\mu >0$ ，稀疏值s，信号个数L，比例因子$\delta >0$ ，外循环次数$n_1$ ，内循环次数$n_2$ 。 外循环：$p=1,\cdots ,n_1$ 。 初始化：$x^0=\frac{A^{\text{T}}x}{{\Vert A^{\text{T}}x\Vert }_2}$ ，$c=0^{mL}$ 。 内循环：$q=0,\cdots ,n_2$ ； $v^{q+1}=\mu A^{\text{T}}\left(sign\left(A{x}^q\right)-y\right)$ ； $a^{q+1}=x^q-reshape\left(v^{q+1},N,L\right)$ ； $x^{q+1}=\eta \left(a^{q+1}\right)$ ； $I:=\left\{i\in \left\{1,\cdots ,ML\right\}:y\times \left(Avec\left(x^{q+1}\right)\right)<0\right\}$ ； $c_I=c_I+1$ ； 如果$x^{q+1}$ 一致性，算法结束； 找到符号翻转的位置并纠正： $W:=\left\{i\in \left\{1,\cdots ,ML\right\},c_i>\delta \times n_2\right\}$ ； $P:=\left\{i\in \left\{1,\cdots ,ML\right\},c_i=\max \left(c_i\right)\right\}$ ； 如果$W\ne 0$ $y_W=-y_W$ 否则 $y_P=-y_P$ 输出：${\widehat{x}}_l=\frac{{\widehat{x}}_l}{{\Vert {\widehat{x}}_l\Vert }_2}$ ，$l=1,\cdots ,L$ 。

3. 数值模拟实验

在本节中，我们将在测量噪声和传输噪声两种噪声干扰情况下，去比较高斯矩阵和部分高斯循环矩阵的重构性能和重构时间。进行比较时，将从测量速率m/N、稀疏性s、信号集大小L三个维度。在所有的数值实验中，信号集$X\in R^{N\times L}$ ，$\left|supp\left(X\right)\right|\le s$ ，是通过均匀随机地选择某个支持集$I\subset \left[N\right]$ ，然后将所选项填充为均值为0、方差为1的i.i.d的高斯随机变量。除此之外，如果在某个实验中参数没有被指定，我们默认N = 200和s = 3。特别地，在实验部分，我们记GM为高斯矩阵，PGCM为部分高斯循环矩阵。最后，通过重构信号与噪声比(Reconstruction Signal to Noise Ratio, RSNR)来衡量实验效果，RSNR在分贝(dB)单位下定义为：

$\text{RSNR}=10\lg \frac{E\left(\widehat{x}\right)}{E\left(x-\widehat{x}\right)}$，

其中，$\widehat{x}$ 为重构信号。RSNR越高，表示信号的重构精度越高。重构时间是记录算法从开始执行到结束的时间，单位为秒(s)。时间越短，说明算法的重构效率越高。

3.1. 测量噪声

我们规定测量噪声$e\in R^{mL}$ 中的每一个元素都服从正态分布$N\left(0,{\sigma }_e^2\right)$ 。所以，以分贝(dB)为单位的输入(Input Signal to Noise Ratio, ISNR)定义为：

$\text{ISNR}=10\lg \frac{E\left({\Vert Ax\Vert }^2\right)}{E\left({\Vert e\Vert }^2\right)}$ ，

其中，$E\left({\Vert e\Vert }^2\right)=N{\sigma }_e^2$ 。ISNR越大，代表噪声的干扰能力越弱。在第一个实验中，固定M = N = 200，s = 5，L = 3。在不同的ISNR下，我们比较GM和PCGM的重构质量。ISNR的范围为5 dB到25 dB。对于每一个ISNR，我们做500次的实验，然后记录平均RSNR。实验结果展示在图1中。从总体情况来看，不管测量矩阵是PGCM还是GM，信号的重构精度都随着ISNR的增大而提高。除此之外，PGCM和GM下的信号重构精度在不同的ISNR值中都差距不大，PGCM有着微弱的优势。基于此，说明两者的重构能力在不同程度的测量噪声的影响下，有着近似的恢复效果。

Figure 1. Reconstruction performance of GM and PGCM with different ISNRs

图1. GM和PGCM在不同ISNR下的重构性能

在第二个实验以及后面的实验中，固定ISNR = 25，然后从测量速率m/N、稀疏度s、信号集大小L三个维度对GM和PGCM的重构性能进行观察与比较。实验结果由图2展示。从图中可以看出，PGCM和GM在测量速率m/N和稀疏度s两个维度下，具有相似的重构性能。在信号集大小L这个维度下，PGCM和GM的信号重构精度都随着信号集大小L的增大而降低。但是，PGCM的降低幅度更小，信号重构精度比GM的更高，这说明PGCM受信号集大小L变化的影响更小。

Figure 2. Reconstruction performance of measurement rate m/N, sparsity s, signal set size L, GM and PGCM in algorithm D-RBIHT affected by measurement noise in three different dimensions

图2. 在三个不同维度下，测量速率m/N、稀疏度s、信号集大小L、GM和PGCM受测量噪声影响时在算法D-RBIHT中的重构性能

在第三个实验中，将对PGCM和GM所需的重构时间进行对比。实验结果由图3展示。从图中可以看出，PGCM所需的重构时间不管是在测量速率m/N、稀疏度s还是信号集大小L的影响下，都比GM的所需时间更短。详细地来说，在测量速率m/N、信号集大小L不断增大时，刚开始两者的恢复时间差距较小，后面差距逐渐增大，PGCM的时间优势逐渐变得明显。对稀疏度s来说，随着稀疏性逐渐变弱，PGCM和GM时间差距逐渐缩小。在稀疏性较强时，两者的重构时间差距突出。总的来说，在三个维度的变化下，PGCM所需的重构时间都要短于GM，说明PGCM在与向量进行乘积时，可以通过快速傅里叶变换显著降低复杂度，提高恢复效率。

Figure 3. Reconstruction time of measurement rate m/N, sparsity s, signal set size L, GM and PGCM in algorithm D-RBIHT affected by measurement noise in three different dimensions

图3. 在三个不同维度下，测量速率m/N、稀疏度s、信号集大小L、GM和PGCM受测量噪声影响时在算法D-RBIHT中的重构时间

3.2. 传输噪声

在传输噪声情况下，符号翻转的概率被定义为符号翻转的个数与测量数之比。在实验中，我们将随机选择一些测量值翻转其符号。

在第一个实验中，我们将在1%至20%的范围内考虑20种不同的符号翻转概率，去比较GM和PGCM的重构效果。实验情况展示在图4中，可以看到，随着符号翻转的不断升高，由PGCM和GM恢复的信号的精度都在不断下降。除此之外，还可以看到PGCM和GM在不同的符号翻转中的信号重构精度不相上下，说明两者的重构性能相当。

Figure 4. Reconstruction performance of GM and PGCM with different symbol flip probabilities

图4. GM和PGCM在不同符号翻转概率下的重构性能

在第二个实验中，为5%，同样从三个维度，测量速率m/N、稀疏度s、信号集大小L，对PGCM和GM的信号重构精度进行对比。实验结果由图5展示。从图中反映的情况可知，PGCM和GM在测量速率m/N、稀疏性s、信号集大小L三个维度中，表现出来的重构性能相当。

Figure 5. Reconstruction performance of measurement rate m/N, sparsity s, signal set size L, GM and PGCM in algorithm D-RBIHT affected by transmission noise in three different dimensions

图5. 在三个不同维度下，测量速率m/N、稀疏度s、信号集大小L、GM和PGCM受传输噪声影响时在算法D-RBIHT中的重构性能

在第三个实验中，保持与第二个实验相同的设置，比较GM和PGCM所需的恢复时间。实验结果由图6展示。从图中可以看出，在测量速率m/N和信号集大小L两个维度下，呈现出来的实验结果与之前在测量噪声中的表现情况一致。在稀疏度s下，PGCM所需的恢复时间都短于GM，有着十分明显的时间优势。总的来说，PGCM比GM的计算速度更快。

最后，我们简单比较一下GM和PGCM的检测精度情况。固定M = N = 200，s = 5，L = 3，在每个符号翻转率下进行500次试验。实验结果由图7展示。在图中，我们可以看到在不同的符号翻转概率下，PGCM和GM的正确检测概率都比较高且几乎没有差距，更进一步说明了，PGCM和GM有着相当的重构性能。

Figure 6. Reconstruction time of measurement rate m/N, sparsity s, signal set size L, GM and PGCM in algorithm D-RBIHT affected by transmission noise in three different dimensions

图6. 在三个不同维度下，测量速率m/N、稀疏度s、信号集大小L、GM和PGCM受传输噪声影响时在算法D-RBIHT中的重构时间

Figure 7. Correct detection accuracy of GM and PGCM with different symbol flip probabilities

图7. GM和PGCM在不同符号翻转概率下的正确检测精度

4. 总结与展望

在本篇文章中，我们通过提出的带噪1-bit DCS的恢复算法，证明了在存在测量噪声和传输噪声的情况下，部分高斯循环矩阵和高斯矩阵有着相似的恢复效果。更进一步说明了，部分高斯循环矩阵在利用快速傅里叶变换与向量进行乘积时，可以显著地降低计算复杂度，缩短计算时间，更具有实际意义。在未来的工作中，可以考虑引入自适应策略，在不知道信号的稀疏水平时，进行动态调整，以提高重构精度。此外，还可以设计更加高效、复杂的1-bit分布式压缩感知鲁棒算法，用来处理更大规模的问题。