论文标题
稀疏最佳秩-1近似与高阶张量的几种近似算法
Several Approximation Algorithms for Sparse Best Rank-1 Approximation to Higher-Order Tensors
论文作者
论文摘要
稀疏张量最佳等级-1近似（BR1Approx）是密度张量BR1Approx的稀疏性概括，并且是稀疏矩阵BR1Approx的高阶扩展，是稀疏张量分解和来自统计学和机器学习引起的稀疏张量分解和相关问题中最重要的问题之一。通过利用问题的多线性以及稀疏性结构，提出了四种近似值算法，这些算法很容易实现，具有低计算复杂性，并可以用作迭代算法的初始过程。另外，在所有算法上都证明了理论上保证的最坏情况近似的下限。我们提供有关合成和实际数据的数值实验，以说明所提出的算法的有效性。
Sparse tensor best rank-1 approximation (BR1Approx), which is a sparsity generalization of the dense tensor BR1Approx, and is a higher-order extension of the sparse matrix BR1Approx, is one of the most important problems in sparse tensor decomposition and related problems arising from statistics and machine learning. By exploiting the multilinearity as well as the sparsity structure of the problem, four approximation algorithms are proposed, which are easily implemented, of low computational complexity, and can serve as initial procedures for iterative algorithms. In addition, theoretically guaranteed worst-case approximation lower bounds are proved for all the algorithms. We provide numerical experiments on synthetic and real data to illustrate the effectiveness of the proposed algorithms.
