MACH: Fast Randomized Tensor Decompositions
MACH: Fast Randomized Tensor Decompositions
复制标题
DOI：
10.1137/1.9781611972801.60
复制
发表时间：
2009-09
期刊：
影响因子：
--
通讯作者：
Charalampos E. Tsourakakis
中科院分区：
文献类型：
--
作者：
Charalampos E. Tsourakakis
张量自然地模拟了许多真实的世界过程，这些过程生成多方面的数据。此类过程出现在许多不同的研究学科中，例如化学计量学、计算机视觉、心理测量学和神经成像分析。Tucker分解等张量分解用于分析多方面数据并提取潜在因素，这些因素捕获多线性数据结构。这种分解是强大的挖掘工具，用于从大量数据中提取模式。然而，最常用的算法，这种分解涉及计算昂贵的奇异值分解。在本文中，我们提出了MACH，一个新的采样算法来计算这样的分解。我们的方法是张量流，如环境监测系统，IP流量矩阵随着时间的推移，大量的数据积累和分析是计算密集型的，但也在“事后”数据分析的情况下，张量不适合在可用的内存中具有重要的实用价值。我们提供了我们所提出的方法的理论分析，并验证其有效性在监控系统的应用。
Tensors naturally model many real world processes which generate multi-aspect data. Such processes appear in many different research disciplines, e.g, chemometrics, computer vision, psychometrics and neuroimaging analysis. Tensor decompositions such as the Tucker decomposition are used to analyze multi-aspect data and extract latent factors, which capture the multilinear data structure. Such decompositions are powerful mining tools, for extracting patterns from large data volumes. However, most frequently used algorithms for such decompositions involve the computationally expensive Singular Value Decomposition. In this paper we propose MACH, a new sampling algorithm to compute such decompositions. Our method is of significant practical value for tensor streams, such as environmental monitoring systems, IP traffic matrices over time, where large amounts of data are accumulated and the analysis is computationally intensive but also in "post-mortem" data analysis cases where the tensor does not fit in the available memory. We provide the theoretical analysis of our proposed method, and verify its efficacy in monitoring system applications.