Dominant Z-Eigenpairs of Tensor Kronecker Products Decouple
Dominant Z-Eigenpairs of Tensor Kronecker Products Decouple
复制标题
DOI：
10.1137/22m1502008
复制
发表时间：
2023-07
期刊：
影响因子：
--
通讯作者：
Charles Colley;Huda Nassar;D. Gleich
中科院分区：
文献类型：
--
作者：
Charles Colley;Huda Nassar;D. Gleich
张量Kronecker积是矩阵Kronecker积的自然推广，在多个研究团体中独立出现。和矩阵一样，张量泛化为隐式乘法和因式分解定理提供了结构。给出了张量Kronecker积的优势特征向量的解耦定理，这是矩阵理论在张量特征向量上的罕见推广。这个定理意味着在Kronecker积上的张量幂方法的迭代中应该存在低秩结构。我们研究了一种幂次启发式网络对齐算法TAME中的低秩结构。直接使用低秩结构或通过新的启发式嵌入方法，我们产生的新算法在提高或保持准确性的同时速度更快，并且可以扩展到现有技术无法实际处理的问题。
Tensor Kronecker products, the natural generalization of the matrix Kronecker product, are independently emerging in multiple research communities. Like their matrix counterpart, the tensor generalization gives structure for implicit multiplication and factorization theorems. We present a theorem that decouples the dominant eigenvectors of tensor Kronecker products, which is a rare generalization from matrix theory to tensor eigenvectors. This theorem implies low-rank structure ought to be present in the iterates of tensor power methods on Kronecker products. We investigate low-rank structure in the network alignment algorithm TAME, a power method heuristic. Using the low-rank structure directly or via a new heuristic embedding approach, we produce new algorithms which are faster while improving or maintaining accuracy, and which scale to problems that cannot be realistically handled with existing techniques.