技术摘要：随机广义采样

1. 问题陈述

本文解决了在可分希尔伯特空间 $\mathcal{H}$ 中，从有限组测量值重构无限维信号 $f$ 的根本挑战。虽然 Adcock 和 Hansen 提出的广义采样（GS）框架为从任意框架或里斯基（Riesz basis）中恢复元素提供了一种稳健的确定性方法，但它存在严重的依赖于基的维度约束。

在确定性 GS 中，保证稳定恢复所需的测量次数 $m$ 通常随重构维度 $n$ 呈二次方增长（即 $m \gtrsim n^2$）。这种“二次瓶颈”源于采样系统（例如傅里叶测量）与重构系统（例如勒让德多项式）之间的几何失配，导致数值不稳定和病态问题。本文旨在通过从确定性采样过渡到完全随机框架来克服这一障碍。

2. 方法论

作者提出了一种随机采样策略，其中测量索引是根据自然数上的特定概率分布 $p = (p_j)_{j \in \mathbb{N}}$ 独立抽取的，而不是确定性前 $m$ 个索引。

核心组件：

• 加权最小二乘法：重构 $\tilde{f}$ 通过求解加权最小二乘问题获得。给定随机索引 $\Omega = \{i_1, \dots, i_m\}$，该方法最小化：
  $$\sum_{t=1}^m \frac{1}{p_{i_t}} |\langle W \iota_n x, s_{i_t} \rangle - \langle f, s_{i_t} \rangle|^2$$
  其中 $\{s_k\}$ 是采样框架，$\{w_k\}$ 是重构里斯基（或框架），$\iota_n$ 将 $\mathbb{C}^n$ 嵌入到 $\ell^2$ 中。
• 杠杆得分采样：为了优化采样率，作者利用由 $p_j \propto \|v_j\|^2$ 定义的杠杆得分分布，其中 $v_j = \iota_n^* U^* e_j$ 表示采样系统与重构系统之间的相互作用。该分布最小化了控制样本复杂度的相干参数 $R$。
• 算子理论分析：分析依赖于控制两个关键随机算子：
  1. 经验 Gram 矩阵 $\hat{\Sigma}_\Omega$，用于估计真实 Gram 矩阵 $\Sigma$。
  2. 经验交叉项算子 $\hat{C}_\Omega$，它控制由重构子空间之外的信号分量（$P_{W_n}^\perp f$）引起的混叠误差。

理论创新：

一个关键的方法论贡献是推导了作用于不同无限维希尔伯特空间之间的随机矩形算子的新型矩阵 Bernstein 不等式。这一扩展使作者能够严格界定交叉项算子 $\hat{C}_\Omega$ 的集中性，这对于在无限维设置中控制混叠误差至关重要。

3. 主要贡献与结果

A. 普适的近线性采样率

主要理论结果表明，通过采用杠杆得分采样，稳定采样率变得普适且近线性：
$$m \gtrsim n \log(2n/\delta)$$
其中 $\delta$ 是失败概率。

• 普适性：与确定性 GS 不同，该速率独立于采样和重构基的具体选择，前提是重构空间嵌入到采样空间中（$W \subseteq S$）。
• 克服二次障碍：这一结果打破了确定性方法在不兼容基（例如傅里叶 - 勒让德对）中固有的 $m \gtrsim n^2$ 障碍。

B. 误差界与准最优性

本文证明，以高概率（$1-\delta$），重构误差满足：
$$\|f - \tilde{f}\| \leq \mu_{n,\Omega} \|P_{W_n}^\perp f\|$$
其中 $\|P_{W_n}^\perp f\|$ 是最优理论近似误差（子空间外的信号尾部）。

• 稳定性：放大因子 $\mu_{n,\Omega}$ 以高概率有界。
• 准最优性：在正交基的情况下，作者证明交叉项因子 $K_{n,\Omega}$ 随着 $m \to \infty$ 依概率收敛于 0。因此，重构误差渐近逼近理论下界，实现了准最优性。

C. 扩展到框架

该框架被推广到重构系统为任意框架（而不仅仅是里斯基）的情况。在这种设置下，极限 Gram 矩阵 $\Sigma$ 可能是奇异的。作者采用Moore-Penrose 伪逆来定义重构，并证明经验 Gram 矩阵以高概率与 $\Sigma$ 具有相同的值域，从而确保即使在冗余框架下也能稳定恢复。

D. 与 Christoffel 采样的联系

本文严格地将离散杠杆得分分布与加权最小二乘近似中使用的连续Christoffel 采样策略联系起来。它表明，在正交基设置中，杠杆得分参数 $R$ 恰好是 Christoffel 参数 $\kappa_w(P)$，从而将离散算子框架与既定的连续近似理论统一起来。

4. 应用：傅里叶 - 勒让德恢复

为了展示实际有效性，作者将该框架应用于经典问题：使用勒让德多项式进行重构，从连续傅里叶测量中恢复解析函数。

• 确定性局限：先前的确定性研究表明，该基对需要 $m \gtrsim n^2$ 才能保持稳定，将收敛速度限制为根指数速率 $O(\rho^{-\sqrt{m}})$。
• 随机结果：通过根据推导出的杠杆得分分布（使用球贝塞尔函数显式计算）对频率进行采样，该方法实现了重构维度 $n \sim m/\log m$。
• 收敛性：这产生了 $O(\rho^{-m/\log m})$ 的近指数收敛速率，相比确定性根指数速率有了巨大改进。

5. 意义与主张

本文声称建立了第一个严格的随机广义采样框架，该框架能够容纳任意框架，并提供关于样本复杂度的显式、非渐近界。

• 理论影响：推导无限维空间之间随机矩形算子的 Bernstein 不等式被视为具有独立意义的贡献，使得控制无限维逆问题中的混叠误差成为可能。
• 实际影响：该框架提供了一种“几何感知”的随机化方法，能够稳定病态反演过程（如傅里叶 - 勒让德恢复），而无需确定性 GS 的严格假设。
• 局限性与范围：作者谦逊地指出，$n \log n$ 速率依赖于几何包含关系 $W \subseteq S$。他们承认，要实现严格的线性速率（$m \gtrsim n$）需要偏离独立同分布采样（例如使用贪婪方法或行列式点过程），这会引入更高的计算成本或结构约束（如再生核希尔伯特空间 RKHS），而当前的抽象框架刻意避免了这些。此外，他们澄清杠杆得分采样解决了基失配和冗余问题，但无法治愈底层物理问题的内在病态性。

总之，这项工作表明，由最优杠杆得分引导的随机采样可以普遍克服确定性广义采样的二次维度约束，从而实现具有近线性样本复杂度的无限维信号的稳定、高精度重构。