Geometric All-Way Boolean Tensor Decomposition
Geometric All-Way Boolean Tensor Decomposition
复制标题
DOI：
--
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Changlin Wan;Wennan Chang;Tong Zhao;Sha Cao;Chi Zhang
中科院分区：
文献类型：
--
作者：
Changlin Wan;Wennan Chang;Tong Zhao;Sha Cao;Chi Zhang
布尔张量已被广泛用于表示收集在空间、时间和/或其他关系域上的高维逻辑数据。布尔张量分解（BTD）将一个二元张量分解为多个秩为1的张量的布尔和，这是一个NP难问题。现有的BTD方法在大规模或高阶张量的应用中受到其高计算成本的限制。在这项工作中，我们提出了一个计算效率高的BTD算法，即\textit{几何扩展全阶张量分解}（GETF），从几何角度依次识别张量的秩1基分量。对GETF分解全阶张量的有效性和算法效率进行了严格的理论分析。在合成数据和真实数据上的实验表明，GETF在重建精度、潜在结构提取等方面都有显著提高，比其他最先进的方法快一个数量级。
Boolean tensor has been broadly utilized in representing high dimensional logical data collected on spatial, temporal and/or other relational domains. Boolean Tensor Decomposition (BTD) factorizes a binary tensor into the Boolean sum of multiple rank-1 tensors, which is an NP-hard problem. Existing BTD methods have been limited by their high computational cost, in applications to large scale or higher order tensors. In this work, we presented a computationally efficient BTD algorithm, namely \textit{Geometric Expansion for all-order Tensor Factorization} (GETF), that sequentially identifies the rank-1 basis components for a tensor from a geometric perspective. We conducted rigorous theoretical analysis on the validity as well as algorithemic efficiency of GETF in decomposing all-order tensor. Experiments on both synthetic and real-world data demonstrated that GETF has significantly improved performance in reconstruction accuracy, extraction of latent structures and it is an order of magnitude faster than other state-of-the-art methods.