Near-optimal Rank Adaptive Inference of High Dimensional Matrices

问题陈述
本文探讨从线性测量 $(x_i, y_i)$ 中估计高维矩阵 $A \in \mathbb{R}^{d_y \times d_x}$ 的问题，其中 $y_i = A x_i + \eta_i$。该设定为高维情形，即矩阵元素的数量与可用样本数 $n$ 相当或超过样本数。在此类情形下，统计上的合理性要求利用结构特性，具体而言是低秩性。作者专注于设计秩自适应算法，这些算法无需预先知晓矩阵的秩。相反，这些算法通过估计奇异值及对应的奇异向量（直至一个“有效秩”）来推断矩阵，而该有效秩是根据数据自适应确定的。主要目标是构建一个估计量 $\hat{A}_n$，以高概率最小化 Frobenius 误差 $\|\hat{A}_n - A\|_F$。本文研究了两个具体应用：多元回归（其中协变量独立同分布）和线性系统辨识（其中协变量为线性时不变动态系统的状态）。

方法论
作者的方法分为两个主要部分：基本界限的理论分析以及特定算法的提出。

1. 实例特定的下界：作者推导了秩自适应算法样本复杂度的首个实例特定下界。与刻画某类中最坏情况性能的传统极小极大界不同，这些界限显式地依赖于目标矩阵 $A$ 的谱特性（奇异值）以及协变量的协方差结构。推导过程涉及微妙的权衡：平衡对部分奇异值估计的精度与对剩余奇异值近似的代价。证明技术结合了测度变换论证（以捕捉对 $A$ 和协变量的依赖）与 Stiefel 流形上的打包论证（以捕捉维度依赖）。

2. 阈值最小二乘估计量（T-LSE）：所提出的算法将标准最小二乘估计量（LSE）与通用奇异值阈值化过程相结合。

   • 首先，计算原始 LSE $\bar{A}$。
   • 其次，对 $\bar{A}$ 执行奇异值分解（SVD）。
   • 第三，对 $\bar{A}$ 的奇异值应用通用阈值 $\xi$。低于 $\xi$ 的奇异值被设为零，而高于 $\xi$ 的奇异值则被保留。
   • 阈值 $\xi$ 的选择基于 LSE 估计误差算子范数的集中性结果。

主要贡献

1. 基本界限：本文确立了秩自适应算法样本复杂度的实例特定下界。这些界限揭示了最优有效秩取决于矩阵 $A$、样本量 $n$ 以及噪声水平。具体而言，界限展示了估计方差（随有效秩和噪声缩放）与偏差（截断小奇异值带来的近似误差）之间的权衡。
2. 近优算法：作者提出了 T-LSE 并提供了有限样本误差界。他们证明，T-LSE 通过实现更紧的误差界，优于现有的秩自适应算法（如秩约束选择法和核范数正则化估计量）。
3. 改进的矩阵去噪：一个关键的理论组成部分是对奇异值阈值化的改进分析。作者证明，对现有估计量应用通用阈值化通常能增强其性能保证，提供比先前结果（例如 Chatterjee, 2015）更紧的误差界，且不依赖于目标矩阵的核范数。
4. 实证验证：在多元回归和线性系统辨识设定下的数值实验证实，T-LSE 优于现有方法，特别是在设计矩阵与目标矩阵的奇异子空间存在错位的情形，以及在自适应至关重要的噪声水平较高的情形中。

结果

• 理论方面：T-LSE 的误差界被证明几乎与推导出的基本界限相匹配。对于多元回归，Frobenius 误差的缩放比例为：
  $$\min_k \left( \frac{k \sigma^2 \bar{d} + \log(1/\delta)}{n \lambda_{\min}(\Sigma)} + \sum_{i>k} s_i^2(A) \right)$$
  其中 $k$ 是有效秩，$\sigma$ 是噪声水平，$\lambda_{\min}(\Sigma)$ 与协变量协方差相关。本文指出，虽然 T-LSE 的上界与下界之间仍存在微小差距（具体涉及经验协方差矩阵谱的依赖性），但对于良态矩阵，这些界限是紧的。
• 实验方面：在 $d=50$ 且秩可变（$r=10$ 和 $r=45$）的模拟中，T-LSE 表现出比秩约束选择（RSC）算法更强的鲁棒性，特别是在设计矩阵与目标矩阵的奇异子空间错位时。此外，随着噪声水平的增加，T-LSE 成功自适应到更低的有效秩，优于非自适应的秩约束估计量。

意义
本文声称在理解秩自适应矩阵估计的性能界限方面提供了前所未有的精度。通过超越极小极大界而转向实例特定界，这项工作阐明了算法如何真正适应待估计的具体矩阵。作者断言，他们是首个推导出依赖于目标矩阵和设计矩阵谱特性的如此精确的下界的人。所提出的 T-LSE 算法提供了一种接近这些基本界限的实用解决方案，在理论保证和实证性能方面均对现有方法提供了显著改进。这项工作强调，在噪声较高或维度较高且真实秩未知或实际上低于环境维度的情形中，自适应性是至关重要的。