基于Nystr?m近似的矩阵Rényi熵高效计算新方法及其在信息理论学习中的应用

本文针对矩阵Rényi熵（matrix-based Rényi's entropy）计算复杂度高的问题，创新性地提出基于Nystr?m的近似策略。通过结合草图技术（sketching techniques）和随机迹估计（stochastic trace estimation），将时间复杂度从O(n3)显著降低至O(n2s)（s?n）。与Hutch++方法相比，新方法减少了对称半正定矩阵（SPSD）的访问次数，在保持精度的同时大幅提升计算效率，为大规模机器学习任务提供了更优解决方案。

　　

亮点

• 我们开发了适用于任意α阶（α>0且α≠1）矩阵Rényi熵的Nystr?m感知近似方法。具体而言，对整数阶α采用迹估计，对分数阶α利用矩阵函数A^α的多项式逼近（泰勒和切比雪夫）。最终将时间复杂度从O(n³)降至O(n²s)，其中s为矩阵-向量乘积查询次数。

• 通过高斯草图低秩近似的精细分析，我们从理论上证明Nystr?m感知近似的查询复杂度s是最优的（仅差对数因子）。同时给出了泰勒和切比雪夫多项式阶数与逼近误差的显式关系，表明多项式阶数与核Gram矩阵A的条件数成正比。

• 通过大规模模拟数据和真实信息理论学习任务的综合评估，验证了我们所提方法的有效性。与基于传统Hutch++的最新近似方法直接对比，我们的方法在计算成本方面展现出显著优势。

数值实验

本节通过大规模合成数据和真实世界信息相关学习任务的评估，来验证所提近似算法的有效性。模拟研究使用Eigen线性代数库实现算法，真实任务则采用PyTorch实现。所有实验均在配备Intel CPU（2.10GHz）、256GB内存和4个GPU的计算系统上完成。

结论

本文提出了适用于任意α阶矩阵Rényi熵的Nystr?m感知近似算法。这些方法在运行时效率上优于最先进的Hutch++基近似方法。我们证明在整数阶和分数阶情况下，仅需O(1/?·√log(1/δ)+log(1/δ))次查询即可实现(1±?)近似，逼近最优查询复杂度。大规模模拟和真实信息理论学习任务的广泛实验佐证了我们的理论发现。