Sharp bounds for non-adaptive randomized approximation of high-dimensional noisy vectors

技术摘要：高维噪声向量非自适应随机逼近的紧确界限

问题陈述
本文研究了使用非自适应随机算法来逼近嵌入 $\ell_p^m \hookrightarrow \ell_q^m$（其中 $2 \le p < q \le \infty$）的复杂度。该设定涉及一个有限维向量空间 $\mathbb{R}^m$，其中维度 $m$ 显著大于可用线性泛函的数量 $n$（即 $n \ll m$）。目标是从 $\ell_p^m$ 单位球中恢复向量 $x$，通过 $n$ 个任意线性测量，使 $\ell_q$ 范数下的最坏情况期望误差最小化。

作者关注 $p \ge 2$ 的情形，将 $\ell_p^m$ 单位球中的向量表征为“噪声向量”。在这种背景下，随机算法旨在恢复 $x$ 的最大分量，而较小的分量则作为随 $\ell_2$ 范数缩放的噪声。对于 $p > 2$，单位 $\ell_p$ 向量的 $\ell_2$ 范数可以高达 $m^{1/2 - 1/p}$，这为逼近带来了显著挑战。

方法论
本文采用 Bakhvalov 技巧（也称为 Yao 原理）来建立下界。该技术涉及将随机设定转换为确定性算法的平均情况设定。核心方法步骤包括：

1. 构建截断高斯混合分布： 作者定义了一个支撑在 $\ell_p$ 单位球上的特定概率测度 $\mu$。该测度被构造为以特定稀疏向量 $u_I$ 为中心的高斯分布的混合。

   • 中心 $u_I$ 源自一个由具有 $\{-1, 0, 1\}$ 分量的 $k$-稀疏向量组成的集合 $W$。
   • 随机索引 $I$ 选择一个中心，并添加高斯噪声 $\sigma Z_m$。
   • 该测度经过截断以确保其支撑集在 $\ell_p$ 单位球内，且当 $m \to \infty$ 时，截断概率趋于零。

2. 归约为填充问题： 下界证明将逼近问题归约为从带噪声的线性观测中识别正确中心 $u_I$ 的任务。

   • 线性信息映射由矩阵 $N$ 表示。
   • 观测值 $Y = N(X)$ 变为以 $v_I = N u_I$ 为中心并带有加性高斯噪声的高斯混合。
   • 证明利用编码理论结果（具体为 Gilbert-Varshamov 界限）来构造一组具有足够 $\ell_p$ 分离度的中心，从而确保中心数量 $M$ 相对于“填充数” $K$（即可以在 $\epsilon$-球内被混淆的最大中心数）足够大。

3. 超水平集的几何分析： 作者通过检查高斯混合密度函数的超水平集来分析大重构误差的概率。他们证明，如果测量次数 $n$ 相对于 $m$ 和稀疏度 $k$ 过小，重构映射将以高概率无法区分这些中心，从而导致对平均误差的下界估计。

主要贡献与结果
本文的主要贡献是证明了非自适应随机逼近误差的匹配下界，从而为该问题建立了紧确界限。

• 误差率： 对于 $2 \le p < q \le \infty$，第 $n$ 个最小随机误差满足：
  $$e_{n}^{\text{ran, nonada}}(n, \ell_p^m \to \ell_q^m) \asymp \min \left\{ 1, \left( \frac{m^{1-2/p} \cdot \log m}{n} \right)^{\frac{1}{2}(1 - p/q)} \right\}$$
  该结果与通过去噪线性随机算法（来自 [6, Thm 4.4]）得到的已知上界相匹配。

• 复杂度： 推导出的 $\epsilon$-复杂度（实现误差 $\epsilon$ 所需的测量次数）为：
  $$n^{\text{ran, nonada}}(\epsilon, \ell_p^m \to \ell_q^m) \asymp \epsilon^{-2p/(1/p - 1/q)} \cdot m^{1-2/p} \cdot \log m$$

• 对维度的依赖性： 结果强调了对于 $p > 2$，对维度 $m$ 的多项式依赖关系（具体为 $m^{1-2/p}$）。这与 $p \in [1, 2]$ 的情形形成对比，在后者中，对 $m$ 的依赖仅为对数级。论文指出，由于高维空间中稀疏向量的 $\ell_2$ 范数固有的“噪声”，对于非自适应算法而言，$m^{1-2/p}$ 这一因子是不可避免的。

意义与范围
本文声称解决了针对特定参数范围 $2 \le p < q \le \infty$ 的非自适应随机逼近的复杂度问题，证明了已知的上界是渐近最优的。

• 与前人工作的比较： 先前的下界（例如 Heinrich 的工作）与 $m$ 无关，且适用于整个 $1 \le p < q \le \infty$ 范围，但在 $p > 2$ 的高维情形下并不紧确。本文提供了第一个具有正确 $n$ 和 $m$ 联合依赖关系的 $p \ge 2$ 情况下的下界。
• 局限性： 作者明确指出，这些下界仅限于非自适应算法以及 $p \ge 2$ 的范围。
  • 对于 $p < 2$，合适的平均情况设定似乎更难分析。
  • 对于自适应算法，其复杂度已知较低（涉及 $\log \log m$ 而非 $\log m$），但证明自适应设置下的下界仍然是一个开放性挑战，特别是对于 $p < 2$ 的情况。
• 未来方向： 作者建议，此处使用的 Gaussian 混合技术可能可以通过信息论技术扩展到 $p \ge 2$ 的自适应随机方法。他们还提出，可能需要一种涉及随机投影的更复杂的高斯测度来处理 $1 \le p < 2$ 的情况。

综上所述，本文为使用非自适应随机测量在 $p \ge 2$ 时逼近 $\ell_p$ 空间中的高维向量的难度提供了严密的理论基础，确认了逼近成本随维度呈多项式级增长。