Reliable one-bit quantization of bandlimited graph data via single-shot noise shaping

技术摘要：通过单次噪声整形实现带限图数据的可靠单比特量化

问题陈述
本文解决了将图结构带限数据量化为每个条目低比特数，同时在低通滤波下保留信息这一挑战。在许多机器学习和自然科学应用（例如传感器网络、社交网络）中，数据存在于图上。虽然图信号处理（GSP）已通过图傅里叶变换（GFT）建立了处理此类数据的工具，但将这些信号量化为少量比特会引入误差。现有的无需子采样的鲁棒量化方法（如 Krahmer 等人 [2023, 2026] 提出的方法）依赖于迭代噪声整形。然而，这些方法存在局限性：它们仅限于特定的比特级（具体为每个条目 $\log \log N$ 比特），并利用增广字母表，从而阻碍了真正的单比特量化。作者旨在开发一种方法，允许可靠地量化到任意比特级，包括每个系数极端情况下的单比特，并提供严格的误差界。

方法论：单次噪声整形（SSNS）
所提出的方法——单次噪声整形（SSNS）——灵感来源于 Maly 和 Saab [2023] 关于神经网络量化的近期工作。与在量化过程中自适应整形噪声的迭代方法不同，SSNS 在应用标准无记忆标量量化器（MSQ）之前执行“单次”预处理步骤。

1. 预处理（算法 1）：
   该方法的核心是一个预处理算法，将原始带限信号 $f$ 转换为替代表示 $\tilde{f}$。该算法通过添加图谱投影矩阵（$X_r^T$）核中的元素，迭代地修改信号。

   • 目标是将信号的条目推向 $\ell_\infty$-球的边界（即 $\pm 1$），同时保留低频信息（$X_r^T \tilde{f} = X_r^T f$）。
   • 当信号中最多有 $r$ 个条目未饱和（不等于 $\pm 1$）时，算法终止。
   • 此过程与 Gram-Schmidt 行走和“整数化”定理相关。

2. 量化：
   一旦获得 $\tilde{f}$，便对每个条目应用具有中升字母表的标准 MSQ。由于 $\tilde{f}$ 中最多有 $r$ 个条目不在量化字母表的边界上（对于 1 比特量化，具体为 $\pm 1$），量化误差被限制在这些少数条目中。

3. 重构：
   最终的量化代表是通过对量化向量 $q$ 应用低通图滤波器（具体为砖墙滤波器 $L_r = X_r X_r^T$）获得的。

主要贡献

• 任意比特级量化： 主要贡献是利用图非相干性将 Maly 和 Saab [2023] 的线性量化框架推广到图域。这消除了先前图量化工作中可实现的比特级的限制，实现了可靠地量化至每个数据系数单比特。
• 理论保证： 本文提供了在低通滤波下，原始信号与量化表示之间 $\ell_2$-距离的严格误差界。定理 3.1 确立相对误差的缩放比例为 $O(2^{-B} \cdot \mu(X_r) \cdot \sqrt{r/N})$，其中 $B$ 是比特深度，$\mu(X_r)$ 是图非相干性。
• 改进的界： 在与 Krahmer 等人 [2023, 2026] 的迭代噪声整形方法在等效总比特预算下进行比较时，SSNS 方法提供了改进的理论最坏情况保证。具体而言，误差界线性依赖于非相干性 $\mu(X_r)$ 而非其平方，并避免了 $\log \log N$ 比特的限制。
• 简化的策略： 与现有的迭代方法相比，证明策略被描述为高度简化。

实验结果
在多种图拓扑（网格、兔子、环形、瑞士卷、传感器和明尼苏达图）上进行了数值实验，带宽和比特预算（$B=1, 2, 4$）各不相同。

• 性能与带宽： 随着比特预算的增加，该方法一致地降低了相对误差。较低的带宽通常导致较低的量化误差，尽管某些不规则图（例如兔子、传感器）在非常小的带宽下显示出相反的趋势，作者指出这尚未被理论完全解释。
• 与 SSS-R 的比较： 将 SSNS 方法与逐步服务替换（SSS-R）方法进行了比较。对于小到中等带宽，SSNS 始终实现了更低或相当的平均相对误差。虽然 SSS-R 在较大带宽下显示出更稳定性，但它需要显著更多的计算资源，且无法执行真正的 1 比特量化。
• 理论与实证： SSNS 的实证性能显著超越了理论最坏情况界，表明这些界可能是保守的。然而，观察到了关于带宽 $r$ 的理论缩放关系。
• 误差分布： 兔子图上的可视化表明，量化误差倾向于在图的“高曲率”区域累积。

意义与主张
作者声称，SSNS 提供了一种简单、有效的方法，用于量化低带宽图信号，并具有可预测的缩放行为。虽然该方法在高带宽下由于预处理步骤而在计算上比 SSS-R 更昂贵，但它提供了独特的优势：

1. 灵活性： 它允许灵活调整比特级，包括 1 比特量化的极端情况，这是迭代方法的增广字母表无法实现的。
2. 鲁棒性： 它展示了在不同图拓扑和信号结构下对量化效应的鲁棒性。
3. 理论严谨性： 它提供了第一种图量化方法，允许单比特量化，同时在低通滤波下的量化误差（QEL）度量中带有严格的误差保证。

本文承认了局限性，指出分析专注于砖墙滤波器，并未完全表征近似带限数据的鲁棒性，也未解释强带限信号在复杂图上的特定误差累积模式。