Statistically and Computationally Optimal Estimation and Inference of Common Subspaces

技术摘要：公共子空间统计与计算最优估计与推断

问题表述
本文研究了从一组观测对称矩阵 $\{A^{(l)}\}_{l=1}^L$ 中估计公共子空间 $U \in \mathbb{R}^{n \times r}$ 的统计与计算极限。数据遵循公共子空间独立边（COSIE）模型：
$$A^{(l)} = S^{(l)} + N^{(l)}, \quad S^{(l)} = U R^{(l)} U^\top,$$
其中 $S^{(l)}$ 是共享公共子空间 $U$ 的低秩信号矩阵，$R^{(l)} \in \mathbb{R}^{r \times r}$ 是每一层特有的对称满秩矩阵，$N^{(l)}$ 是具有独立亚高斯项（具体建模为方差为 $\sigma^2$ 的 Wigner 或高斯正交系矩阵）的对称噪声矩阵。目标是恢复 $U$（在正交变换意义下）并对估计误差 $\|\sin \Theta(\hat{U}, U)\|_F^2$ 进行统计推断。

方法论
作者提出了一种两阶段程序进行估计：

1. 基于平方和的谱初始化：为了初始化算法，他们计算观测矩阵平方和的谱分解：$\hat{U}_0 = \text{SVDr}(\sum_{l=1}^L (A^{(l)})^2)$。这种初始化至关重要，因为简单的 $A^{(l)}$ 平均可能会导致信号抵消，因为 $R^{(l)}$ 可能具有混合符号或变化的结构。对矩阵进行平方处理可以确保信号在领先特征空间中实现建设性的累积。
2. 投影梯度下降 (PGD)：从 $\hat{U}_0$ 开始，作者使用投影梯度下降法优化损失函数 $h(\hat{U}; \{\hat{R}^{(l)}\}) = \frac{1}{4L} \sum_{l=1}^L \|A^{(l)} - \hat{U}\hat{R}^{(l)}\hat{U}^\top\|_F^2$。在每次迭代中，梯度步之后会进行向 Stiefel 流形的投影（通过 SVD），以保持正交性。$\hat{R}^{(l)}$ 项通过闭式解进行更新，即 $\hat{R}^{(l)}_t = \hat{U}_t^\top A^{(l)} \hat{U}_t$。

对于统计推断，作者在高信噪比（SNR）机制下导出了平方 Frobenius 误差 $\|\sin \Theta(\hat{U}, U)\|_F^2$ 的渐近正态性结果。基于该极限定理，他们构建了无需预先了解信号强度的插件式（plug-in）置信区间。

核心贡献与结果

1. 最优估计速率：
   本文确立了所提出的 PGD 算法在经过对数级次数的迭代后，可以达到极小极大（minimax）最优误差率，前提是信噪比（$\lambda/\sigma$，其中 $\lambda$ 表征信号强度）满足“强估计 SNR”条件：$\lambda/\sigma \gtrsim \sqrt{n}/L^{1/4}$。

   • 弱估计 SNR ($\lambda/\sigma \ll \sqrt{n/L}$)：估计在信息论上是不可能的。
   • 中等估计 SNR ($\sqrt{n/L} \lesssim \lambda/\sigma \ll \sqrt{n}/L^{1/4}$)：不存在基于低度似然比检验的多项式时间估计器，表明存在计算障碍。
   • 强估计 SNR：所提算法在统计和计算上都是最优的。

2. 统计推断与自适应性：
   作者的一个新颖贡献是对自适应统计推断的分析。作者表明，虽然估计在多项式时间内可能是可行的，但自适应推断（在不知道 SNR 的情况下构建置信区间）面临着更高的阈值。

   • 弱推断 SNR ($\sqrt{n}/L^{1/4} \ll \lambda/\sigma \ll n/\sqrt{L}$)：自适应推断在信息论上是不可能的。
   • 强推断 SNR ($\lambda/\sigma \gg n/\sqrt{L}$)：所提置信区间是自适应极小极大最优的。
   • 渐近正态性：本文证明了在强推断机制下，$\|\sin \Theta(\hat{U}, U)\|_F^2$ 是渐近高斯的，从而允许构建有效的置信区间。

3. 计算与统计差距：
   结果揭示了一种新颖的现象：“计算-统计”推断差距。估计的计算阈值 ($\lambda/\sigma \sim \sqrt{n}/L^{1/4}$) 严格低于自适应推断的统计阈值 ($\lambda/\sigma \sim n/\sqrt{L}$)。因此，存在这样一个机制：最优估计在计算上是可行的，但自适应统计推断在信息论上仍然是不可能的。这与许多现有模型（例如张量数据分析）形成了对比，在那些模型中，一旦估计在计算上可行，推断通常是“免费”的。

意义
本文全面刻画了公共子空间模型的相变。它通过证明自适应推断的要求显著严于估计的要求，弥合了估计与推断之间的鸿沟。这项工作将公共子空间分析的应用范围从网络数据（此前在该领域应用）扩展到了具有同方差噪声的一般对称低秩矩阵。研究表明，所提算法在不需要全局优化或额外的去偏步骤（这些步骤在异方差设定中通常是必要的）的情况下，依然具有鲁棒性和最优性。研究结果强调，在高维设置且拥有多个数据源的情况下，能够自适应地量化不确定性是一个比点估计更独特且更具挑战性的统计问题。