技术摘要：极小极大最优子矩阵检测：精确的非渐近速率

问题表述

本工作解决了在高维高斯矩阵中检测隐藏子矩阵这一基本统计问题。观测数据被建模为矩阵 $Y \in \mathbb{R}^{d_1 \times d_2}$，由 $Y = X + E$ 生成，其中 $E$ 包含服从 $N(0, 1)$ 分布的独立同分布条目。目标是检验原假设 $H_0$（$X$ 为零矩阵）与备择假设 $H_1(\mu)$，后者假设存在一个未知的 $s_1 \times s_2$ 大小子矩阵，其条目服从 $N(\mu, 1)$ 分布（$\mu > 0$ 为信号强度），而所有其他条目仍为 $N(0, 1)$。

作者旨在刻画极小极大分离速率 $\mu^*$，定义为确保存在一个检验，其第一类错误和第二类错误均被固定常数 $\eta \in (0, 1)$ 所界定的最小信号强度。与以往文献常依赖特定渐近机制或平衡性假设不同，本文旨在推导适用于任意维度配置 $d_1, d_2$ 和稀疏度水平 $s_1, s_2$ 的 $\mu^*$ 的精确非渐近上下界。

方法论

下界构造

为了确立检测的基本极限，作者精确应用了二阶矩方法（LeCam, 1973）。证明策略包括：

1. 定义一个缩减参数空间，其中信号条目恰好为 $\mu$。
2. 通过对所有可能的子矩阵位置施加均匀先验，构造混合分布 $P_\pi$。
3. 通过简单假设检验（原假设 $P_0$ 对混合假设 $P_\pi$）的贝叶斯风险，对极小极大风险进行下界估计。
4. 利用奈曼 - 皮尔逊引理并控制似然比统计量的二阶矩 $E_0[L_\pi^2]$。
5. 对两个二项随机变量（代表行和列支撑集的重叠）乘积的矩生成函数进行精确分析。该分析不同于以往截断二阶矩策略，无需限制性假设即可处理 $(s_1, s_2, d_1, d_2)$ 的所有可能机制。

上界构造（检验程序）

作者提出了一种新颖的检验程序，实现了推导出的下界。最优检验 $\Delta^*$ 是四个组成检验的精心组合，通过并集聚合（若任一组件拒绝则拒绝 $H_0$）：

1. 线性检验：基于求和的标准统计量（$\sum Y_{ij}$）及其经过邦弗罗尼校正的版本，用于扫描行或列的子集。
2. 截断 $\chi^2$ 检验：形式为 $\sum ((\bar{Y}_j)^2 - \nu_\tau) \mathbb{1}(|\bar{Y}_j| > \tau)$ 的统计量，在信号微弱但支撑集较小的稀疏机制中是最优的。
3. 邦弗罗尼校正的截断 $\chi^2$ 检验：涉及扫描所有可能的行（或列）子集，并对聚合后的列（或行）和应用截断 $\chi^2$ 统计量。这是将截断 $\chi^2$ 方法扩展到矩阵设置的新颖延伸，旨在保留两个维度上的稀疏结构。

具体选择的检验取决于极小极大速率表达式中哪一项占主导地位，从而使该程序能够适应稠密、稀疏和高度不平衡的机制。

自适应扩展

认识到在实际应用中 $s_1$ 和 $s_2$ 通常是未知的，作者构造了一个自适应检验 $\Delta^*_{ada}$。该程序对可能的稀疏度水平 $(s_1, s_2)$ 进行二分划分扫描，并聚合每个候选对的最优检验。作者证明，只要真实的稀疏度水平满足关于矩阵维度的温和条件，该自适应程序即可在常数范围内达到极小极大速率。

主要贡献与结果

1. 精确的非渐近极小极大速率

主要贡献是推导出了精确的非渐近极小极大速率 $\mu^*$。作者证明：
$$(\mu^*)^2 \asymp \left[ (\psi_{12} + \psi_{21}) \wedge \phi_{12} \wedge \phi_{21} \right]$$
其中各项定义为：

• $\psi_{12} = \frac{1}{s_1} \log\left(1 + \frac{d_2}{s_2^2} \log\left(e \frac{d_1}{s_1}\right)\right)$
• $\phi_{12} = \frac{d_1}{s_1^2} \log\left(1 + \frac{d_2}{s_2^2}\right)$
• （以及对称项 $\psi_{21}, \phi_{21}$）。

该结果推广了向量情况下的先前发现（Collier et al., 2017），并在常数范围内恢复了 Butucea 和 Ingster (2013) 的开创性结果，但关键在于无需他们那些限制性平衡假设（例如 $s_1 \log(d_1/s_1) \asymp s_2 \log(d_2/s_2)$）。

2. 新相变的发现

本文识别出了此前被渐近假设所掩盖的检测边界上的新相变。具体而言，作者刻画了矩阵高度不平衡（例如 $s_1 \ll s_2$ 或 $d_1 \ll d_2$）的机制。在这些机制中，最优检测速率与“平衡”机制显著不同，揭示了统计难度以复杂方式取决于观测矩阵与植入子矩阵的相对形状。

3. 先前最先进方法的次优性

作者证明，Butucea 和 Ingster (2013) 及后续工作确立的检测速率在某些不平衡机制中是严格次优的。通过去除平衡性假设，他们表明，在 $s_1^2 \gg d_1 s_2 \log(d_2)$ 的情况下，真实的极小极大速率可能显著低于（即更容易检测）先前的认知。

4. 新颖的检验程序

本文首次提出了用于子矩阵检测的截断 $\chi^2$ 方法的多维扩展。所提出的检验以邦弗罗尼校正的方式将线性统计量与截断 $\chi^2$ 统计量相结合，以处理搜索空间的组合复杂性，同时保持统计最优性。

意义与主张

作者声称已“完全解决”了同方差高斯噪声下子矩阵检测的非渐近极小极大速率。本工作的重要性在于：

• 完整性：提供了所有可能机制的全面图景，包括先前文献中缺失的高度不平衡设置。
• 通用性：建立了适用于 $d_1, d_2, s_1, s_2$ 任意配置的匹配界，而非依赖特定的渐近缩放律。
• 方法创新：提供了一种新的检验统计量组合（线性和截断 $\chi^2$），可在所有机制中实现最优性，这表明标准扫描检验并非总是必要的，且可被更高效的程序取代。

论文结论指出，虽然统计极限现已完全刻画，但计算方面（特别是在不平衡机制中是否存在能达到这些速率的多项式时间算法）仍是一个未解决的问题，因为所提出的最优检验在某些稀疏设置中可能需要指数时间。