Structured covariance estimation via tensor-train decomposition

基本信息

• 论文ID: 2510.08174
• 标题: Structured covariance estimation via tensor-train decomposition
• 作者: Artsiom Patarusau, Nikita Puchkin, Maxim Rakhuba, Fedor Noskov (HSE University)
• 分类: math.ST (Statistics Theory)
• 发表时间: 2025年10月15日
• 论文链接: https://arxiv.org/abs/2510.08174v2

摘要

本文研究从独立同分布的高维随机向量样本中估计协方差矩阵的问题。为避免维数诅咒，作者对协方差矩阵Σ的结构施加额外假设，具体研究Σ可以用张量训练(TT)格式下的较小矩阵的双Kronecker积之和来近似的情况。该设定自然扩展了广为人知的Kronecker和与CANDECOMP/PARAFAC模型，但允许模态间更丰富的交互。作者提出了基于TT-SVD和适用于Tucker-2混合结构的高阶正交迭代(HOOI)的多项式时间迭代算法，并推导了考虑隐藏Kronecker积和张量训练结构的协方差估计精度的非渐近无维界限。

研究背景与动机

问题定义

给定独立同分布的中心化随机向量 $X, X_1, \ldots, X_n \in \mathbb{R}^d$，需要估计其协方差矩阵 $\Sigma = \mathbb{E}[XX^T] \in \mathbb{R}^{d \times d}$。

研究动机

1. 维数诅咒问题：在高维情况下，经典的样本协方差估计器 $\hat{\Sigma} = \frac{1}{n}\sum_{i=1}^n X_i X_i^T$ 面临维数诅咒，当 $d$ 很大时性能急剧下降。
2. 结构化假设的必要性：为克服这一问题，统计学家通常对 $\Sigma$ 施加额外的结构假设以利用数据结构并减少未知参数的总数。
3. 现有方法的局限：
   • Kronecker积模型 $\Sigma = \Phi \otimes \Psi$ 过于简单
   • Kronecker和模型 $\Sigma = \sum_{k=1}^K \Phi_k \otimes \Psi_k$ 缺乏足够的灵活性
   • CANDECOMP/PARAFAC模型在计算上面临NP难问题

本文创新

提出张量训练(TT)格式的协方差模型： $\Sigma = \sum_{j=1}^J \sum_{k=1}^K U_j \otimes V_{jk} \otimes W_k$ 其中 $U_j \in \mathbb{R}^{p \times p}$, $V_{jk} \in \mathbb{R}^{q \times q}$, $W_k \in \mathbb{R}^{r \times r}$，且 $pqr = d$。

核心贡献

1. 新的协方差模型：提出了基于张量训练分解的协方差结构，自然扩展了Kronecker和与CANDECOMP/PARAFAC模型，允许更丰富的模态间交互。
2. 高效算法：设计了HardTTh算法（Hard Tensor Train Thresholding），基于TT-SVD和适应Tucker-2混合结构的HOOI，计算复杂度为 $O((J+K)Td_1d_2d_3)$。
3. 理论保证：建立了非渐近、无维度的收敛界限，这是首个针对TT结构张量估计的无维度理论结果。
4. 实用性验证：通过数值实验验证了方法的有效性，展示了迭代改进的必要性。

方法详解

任务定义

输入：独立同分布样本 $X_1, \ldots, X_n \in \mathbb{R}^{pqr}$输出：协方差矩阵 $\Sigma$ 的估计 $\tilde{\Sigma}$约束：$\Sigma$ 具有TT结构，可表示为 $\Sigma = \sum_{j=1}^J \sum_{k=1}^K U_j \otimes V_{jk} \otimes W_k$

模型架构

张量重排与分解

1. 重排操作：将协方差矩阵 $\Sigma \in \mathbb{R}^{pqr \times pqr}$ 重排为三阶张量 $\mathcal{R}(\Sigma) \in \mathbb{R}^{p^2 \times q^2 \times r^2}$
2. TT分解表示： $\mathcal{R}(\Sigma) = \sum_{j=1}^J \sum_{k=1}^K \text{vec}(U_j) \otimes \text{vec}(V_{jk}) \otimes \text{vec}(W_k)$
3. 紧凑形式： $\mathcal{R}(\Sigma) = U \times_1 V \times_3 W$ 其中 $U \in O_{p^2,J}$, $V \in O_{r^2,K}$, $W \in \mathbb{R}^{J \times q^2 \times K}$

HardTTh算法

算法1：HardTTh

输入：张量 Y ∈ R^{d₁×d₂×d₃}, TT秩 (J,K), 迭代步数 T
输出：TT近似 T̂ = Û ×₁ V̂ ×₃ Ŵ

1. 计算 m₁(Y) 的截断SVD：Û₀, Σ₀,₁, Ũ₀ = SVD_J(m₁(Y))
2. 计算 m₃(Û₀ᵀ ×₁ Y) 的截断SVD：V̂₀, Σ₀,₂, Ṽ₀ = SVD_K(m₃(Û₀ᵀ ×₁ Y))

for t = 1, ..., T do:
3. Ût, Σt,₁, Ũt = SVD_J(m₁(V̂ₜ₋₁ᵀ ×₃ Y))
4. V̂t, Σt,₂, Ṽt = SVD_K(m₃(Ûtᵀ ×₁ Y))

5. 设置 Û = ÛT, V̂ = V̂T, Ŵ = Ûᵀ ×₁ V̂ᵀ ×₃ Y

技术创新点

1. Tucker-2混合结构：不同于标准Tucker分解需要三个正交因子，TT结构只需要两个正交因子，降低了计算复杂度。
2. 迭代改进策略：通过交替优化模态子空间，逐步改善估计精度。
3. 硬阈值处理：使用硬阈值而非软阈值，避免了张量核范数近似的NP难问题。

实验设置

数据生成模型

• TT秩：$J = 7, K = 9$
• 维度：$p = q = r = 10$，总维度 $d = 1000$
• 生成过程：
  • 生成随机对称矩阵 $A_j \in \mathbb{R}^{p \times p}$, $B_{jk} \in \mathbb{R}^{q \times q}$, $C_k \in \mathbb{R}^{r \times r}$
  • 随机向量定义为：$\sum_{j=1}^J \sum_{k=1}^K A_j \times_1 B_{jk} \times_2 C_k \times_3 E_{ijk}$
  • 其中 $E_{ijk}$ 为标准高斯张量

评价指标

相对误差：$\|\hat{S} - \Sigma\|_F / \|\Sigma\|_F$

对比方法

1. Sample Mean：样本协方差估计器
2. TT-HOSVD：HardTTh算法的无迭代版本（$T=0$）
3. Tucker：标准Tucker分解
4. Tucker+HOOI：带HOOI迭代的Tucker分解
5. PRLS：修改版的正则化最小二乘法

实现细节

• 迭代次数：$T = 10$
• PRLS参数：在对数尺度网格上调优 $\lambda_1, \lambda_2$
• 实验重复：每个设置重复16-32次

实验结果

主要结果

关键发现

1. 迭代的必要性：HardTTh相比TT-HOSVD显著改善，特别是在n=2000时，相对误差从0.154降至0.082。
2. 收敛行为：
   • n=500时：$\sin\Theta(\text{Im}\hat{U}_0, \text{Im}U^*) \approx 1$, $\sin\Theta(\text{Im}\hat{U}_T, \text{Im}U^*) \approx 1$
   • n=2000时：$\sin\Theta(\text{Im}\hat{U}_0, \text{Im}U^*) \approx 1$, $\sin\Theta(\text{Im}\hat{U}_T, \text{Im}U^*) = 0.33±0.08$
3. 计算效率：HardTTh的时间复杂度适中，比完整Tucker分解快但比TT-HOSVD慢。

理论验证

实验证实了理论条件的必要性：当奇异值条件不满足时（如n=500），算法无法有效恢复子空间；当条件满足时（如n≥2000），迭代显著改善性能。

相关工作

Kronecker积模型

• 单Kronecker积：Werner et al. (2008) 提出 $\Sigma = \Phi \otimes \Psi$ 模型
• Kronecker和：Tsiligkaridis & Hero (2013), Puchkin & Rakhuba (2024) 研究 $\Sigma = \sum_k \Phi_k \otimes \Psi_k$ 模型

张量分解方法

• CP分解：面临计算复杂性问题
• Tucker分解：Zhang & Xia (2018) 等建立了维度相关的界限
• TT分解：Oseledets (2011) 提出，本文首次应用于协方差估计

理论进展

• 维度相关界限：大多数现有结果依赖于环境维度
• 维度无关界限：仅限于简单情况，本文扩展到TT结构

结论与讨论

主要结论

1. 模型优势：TT格式协方差模型在保持计算可行性的同时提供了比传统Kronecker模型更丰富的结构。
2. 算法有效性：HardTTh算法实现了多项式时间复杂度，并通过迭代显著改善估计质量。
3. 理论保证：建立了首个针对TT结构的无维度收敛界限，方差项为： $\tilde{v} = 96\omega\|\Sigma\|\sqrt{\frac{Jr_1^2(\Sigma) + JKr_2^2(\Sigma) + Kr_3^2(\Sigma) + \log(48/\delta)}{n}}$

局限性

1. 奇异值条件：算法需要 $\sigma_J(m_1(\mathcal{R}(\Sigma))) \gtrsim \|\Sigma\|\sqrt{r_2^2(\Sigma)r_3^2(\Sigma)/n}$，比理论最优条件更强。
2. 噪声结构：理论分析假设特定的噪声结构，与齐次噪声不同。
3. 参数选择：TT秩$(J,K)$的选择需要先验知识或数据驱动方法。

未来方向

1. 去偏方法：开发处理非齐次噪声的去偏技术。
2. 自适应秩选择：建立理论保证的秩选择方法。
3. 扩展应用：将方法扩展到其他结构化矩阵估计问题。

深度评价

优点

1. 理论创新：首次为TT结构协方差估计提供无维度理论界限，填补了重要理论空白。
2. 方法实用：HardTTh算法计算复杂度合理，避免了NP难问题。
3. 实验充分：通过多种对比方法和不同样本大小验证了方法有效性。
4. 分析深入：提供了详细的理论分析和算法收敛性研究。

不足

1. 条件较强：理论条件比已知下界更严格，存在统计-计算间隙。
2. 模型限制：仅适用于可用TT格式良好近似的协方差矩阵。
3. 参数敏感：性能依赖于TT秩参数的正确选择。

影响力

1. 理论贡献：为高维统计中的张量方法提供了新的理论工具。
2. 实用价值：在多模态数据分析、信号处理等领域有潜在应用。
3. 方法论意义：展示了如何将张量分解技术有效应用于统计估计问题。

适用场景

1. 多模态数据：图像、视频等具有天然张量结构的数据
2. 时空数据：具有时间-空间结构的协方差估计
3. 高维金融数据：资产收益的结构化协方差建模
4. 传感器网络：多传感器数据的协方差估计

参考文献

1. Werner, K., Jansson, M., & Stoica, P. (2008). On estimation of covariance matrices with Kronecker product structure.
2. Tsiligkaridis, T., & Hero, A. O. (2013). Covariance estimation in high dimensions via Kronecker product expansions.
3. Zhang, A., & Xia, D. (2018). Tensor SVD: Statistical and computational limits.
4. Puchkin, N., & Rakhuba, M. (2024). Dimension-free structured covariance estimation.
5. Oseledets, I. V. (2011). Tensor-train decomposition.