基于中心矩阵Frobenius误差界的二次型迹的误差界推导

嘿，这个问题其实是矩阵分析里处理协方差估计误差时很常见的场景，我来一步步给你拆解清楚～

首先，我们先把目标表达式做个简化：
$$\text{Tr}(Z^T \boldsymbol{M} Z) - \text{Tr}(Z^T \tilde{\boldsymbol{M}} Z) = \text{Tr}(Z^T (\boldsymbol{M} - \tilde{\boldsymbol{M}}) Z)$$
记误差矩阵 $\boldsymbol{D} = \boldsymbol{M} - \tilde{\boldsymbol{M}}$，已知 $|\boldsymbol{D}|_F = \tilde{O}(f(n,d))$，我们的目标就是给 $|\text{Tr}(Z^T \boldsymbol{D} Z)|$ 找合适的界。

一、直接的基础误差界 #

最直观的推导可以用迹的基本不等式和Frobenius范数的乘积性质：

1. 首先，迹的绝对值满足 $|\text{Tr}(\boldsymbol{A})| \leq |\boldsymbol{A}|_F$（因为迹是对角线元素之和，绝对值不超过所有元素平方和的平方根）；
2. 然后，矩阵乘积的Frobenius范数满足 $|\boldsymbol{A}\boldsymbol{B}\boldsymbol{C}|_F \leq |\boldsymbol{A}|_F |\boldsymbol{B}|_F |\boldsymbol{C}|_F$；
3. 代入 $\boldsymbol{A}=Z^T$，$\boldsymbol{B}=\boldsymbol{D}$，$\boldsymbol{C}=Z$，注意到 $|Z^T|_F = |Z|_F$，所以：
   $$|\text{Tr}(Z^T \boldsymbol{D} Z)| \leq |Z^T \boldsymbol{D} Z|_F \leq |Z|_F^2 |\boldsymbol{D}|_F = \tilde{O}\left(f(n,d) \cdot |Z|_F^2\right)$$

这个界的优点是简单直接，不需要额外假设，但缺点是可能偏松，因为它没有利用误差矩阵 $\boldsymbol{D}$ 或变换矩阵 $Z$ 的结构信息。

二、更紧的误差界 #

如果我们愿意引入更多矩阵的结构性质，可以得到更紧凑的界，这里分享两种常用的思路：

思路1：利用谱范数与迹的结合 #

注意到 $Z^T Z$ 是半正定矩阵，我们可以把目标表达式改写为 $\text{Tr}(\boldsymbol{D} Z Z^T)$（迹的循环性质：$\text{Tr}(\boldsymbol{AB})=\text{Tr}(\boldsymbol{BA})$）。对于半正定矩阵 $\boldsymbol{C}=Z Z^T$，有一个更紧的迹不等式：
$$|\text{Tr}(\boldsymbol{D} \boldsymbol{C})| \leq |\boldsymbol{D}|_2 \cdot \text{Tr}(\boldsymbol{C})$$
其中 $|\boldsymbol{D}|_2$ 是 $\boldsymbol{D}$ 的谱范数（最大奇异值），而 $\text{Tr}(\boldsymbol{C}) = \text{Tr}(Z Z^T) = \text{Tr}(Z^T Z) = |Z|_F^2$。

因为谱范数总是小于等于Frobenius范数（$|\boldsymbol{D}|_2 \leq |\boldsymbol{D}|_F$），当 $\boldsymbol{D}$ 的谱范数远小于其Frobenius范数时（比如误差矩阵是低秩的，或者特征值分布比较集中），这个界会比基础界更紧。代入已知的Frobenius误差，我们可以得到：
$$|\text{Tr}(Z^T \boldsymbol{D} Z)| \leq |\boldsymbol{D}|_2 \cdot |Z|_F^2 \leq \tilde{O}\left(f(n,d) \cdot |Z|_F^2\right)$$
看起来和基础界形式类似，但实际数值上更优，因为 $|\boldsymbol{D}|_2$ 是更小的系数。

思路2：利用奇异值的Cauchy-Schwarz不等式 #

我们可以从奇异值分解的角度来推导。设 $Z$ 的奇异值为 $\sigma_1 \geq \sigma_2 \geq \dots \geq \sigma_k$，$\boldsymbol{D}$ 的特征值为 $\lambda_1, \lambda_2, \dots, \lambda_d$，那么：
$$\text{Tr}(Z^T \boldsymbol{D} Z) = \sum_{i=1}^k \sigma_i^2 \lambda_i'$$
其中 $\lambda_i'$ 是 $\boldsymbol{D}$ 对应于 $Z$ 列空间的特征值（或者说，是 $\boldsymbol{D}$ 在 $Z$ 的列空间上的限制的特征值）。

根据Cauchy-Schwarz不等式：
$$\left|\sum_{i=1}^k \sigma_i^2 \lambda_i'\right| \leq \left(\sum_{i=1}^k \sigma_i^4\right){1/2} \cdot \left(\sum_{i=1}^k (\lambda_i')^2\right){1/2}$$
而 $\sum_{i=1}^k \sigma_i^4 = \text{Tr}((Z Z^T)2) = |Z Z^T|_F2$，$\sum_{i=1}^k (\lambda_i')^2 \leq \sum_{i=1}^d \lambda_i^2 = |\boldsymbol{D}|_F^2$，所以最终得到：
$$|\text{Tr}(Z^T \boldsymbol{D} Z)| \leq |Z Z^T|_F \cdot |\boldsymbol{D}|_F = \tilde{O}\left(f(n,d) \cdot |Z Z^T|_F\right)$$
因为 $|Z Z^T|_F \leq |Z|_F^2$（由Frobenius范数的乘积性质），所以这个界也比基础界更紧，尤其是当 $Z$ 的列之间相关性很高时，$|Z Z^T|_F$ 会远小于 $|Z|_F^2$。

总结一下：

• 基础界：$\tilde{O}\left(f(n,d) \cdot |Z|_F^2\right)$，简单通用；
• 更紧的界：可以根据 $\boldsymbol{D}$ 和 $Z$ 的结构选择 $\tilde{O}\left(f(n,d) \cdot \frac{|\boldsymbol{D}|_2}{|\boldsymbol{D}|_F} \cdot |Z|_F^2\right)$ 或者 $\tilde{O}\left(f(n,d) \cdot |Z Z^T|_F\right)$，前者依赖误差矩阵的谱特性，后者依赖变换矩阵的列相关性。

备注：内容来源于stack exchange，提问作者hearse