用近似理查森迭代加速张量补全，实测快100倍。
Fast Tensor Completion via Approximate Richardson Iteration
- 将张量补全转化为可复用低秩分解算法的近似求解框架
- 在真实数据上实现比传统方法快100倍的CP张量补全
- 适合需要高速处理大规模张量数据的研究者
我们从低秩张量分解的角度研究张量补全（TC）。许多张量分解算法通过快速交替最小化求解高度结构化的线性回归问题（如CP、Tucker和张量列车分解）。然而，此类代数结构在张量补全问题中常被破坏，导致直接扩展不明确。本文提出一种新颖的升维方法，利用结构化张量分解回归算法作为黑盒子程序，近似求解张量补全回归问题，从而实现亚线性时间复杂度的方法。我们分析了基于近似理查森迭代算法的收敛速度，并通过实验验证：在真实张量上，该方法对CP补全可比直接方法快100倍。
原文摘要 · Abstract (English)
We study tensor completion (TC) through the lens of low-rank tensor decomposition (TD). Many TD algorithms use fast alternating minimization methods to solve highly structured linear regression problems at each step (e.g., for CP, Tucker, and tensor-train decompositions). However, such algebraic structure is often lost in TC regression problems, making direct extensions unclear. This work proposes a novel lifting method for approximately solving TC regression problems using structured TD regression algorithms as blackbox subroutines, enabling sublinear-time methods. We analyze the convergence rate of our approximate Richardson iteration-based algorithm, and our empirical study shows that it can be 100x faster than direct methods for CP completion on real-world tensors.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。