Efficient MATLAB computations with sparse and factored tensors

被引:298
作者
Bader, Brett W. [1 ]
Kolda, Tamara G. [2 ]
机构
[1] Sandia Natl Labs, Appl Computat Methods Dept, Albuquerque, NM 87185 USA
[2] Sandia Natl Labs, Math Informat & Decis Sci Dept, Livermore, CA 94551 USA
关键词
sparse multidimensional arrays; multilinear algebraic computations; tensor decompositions; Tucker model; parallel factors (PARAFAC) model; MATLAB classes; canonical decomposition (CANDECOMP);
D O I
10.1137/060676489
中图分类号
O29 [应用数学];
学科分类号
070104 [应用数学];
摘要
In this paper, the term tensor refers simply to a multidimensional or N-way array, and we consider how specially structured tensors allow for efficient storage and computation first, we study sparse tensors, which have the property that the vast majority of the elements are zero. We propose storing sparse tensors using coordinate format and describe the computational efficiency of this scheme for various mathematical operations, including those typical to tensor decomposition algorithms. Second, we study factored tensors, which have the property that they can be assembled from more basic components. We consider two specific types: A Tucker tensor can be expressed as the product of a core tensor (which itself may be dense, sparse, or factored) and a matrix along each mode, and a Kruskal tensor can be expressed as the sum of rank-1 tensors. We are interested in the case where the storage of the components is less than the storage of the full tensor, and we demonstrate that many elementary operations can be computed using only the components. All of the efficiencies described in this paper are implemented in the Tensor Toolbox for MATLAB.
引用
收藏
页码:205 / 231
页数:27
相关论文
共 58 条
[1]
Acar E, 2006, LECT NOTES COMPUT SC, V3975, P213
[2]
The N-way Toolbox for MATLAB [J].
Andersson, CA ;
Bro, R .
CHEMOMETRICS AND INTELLIGENT LABORATORY SYSTEMS, 2000, 52 (01) :1-4
[3]
[Anonymous], 1998, Multi-way Analysis in the Food Industry: Models, Algorithms and Applications
[4]
[Anonymous], MULTIWAY DATA ANAL
[5]
[Anonymous], 1971, GEN INVERSES MATRICE
[6]
[Anonymous], WWW 2005
[7]
[Anonymous], 2004, MULTIWAY ANAL APPL C
[8]
STRATEGIES FOR ANALYZING DATA FROM VIDEO FLUOROMETRIC MONITORING OF LIQUID-CHROMATOGRAPHIC EFFLUENTS [J].
APPELLOF, CJ ;
DAVIDSON, ER .
ANALYTICAL CHEMISTRY, 1981, 53 (13) :2053-2056
[9]
Algorithm 862: MATLAB tensor classes for fast algorithm prototyping [J].
Bader, Brett W. ;
Kolda, Tamara G. .
ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 2006, 32 (04) :635-653
[10]
BADER BW, 2006, MATLAB TENSOR TOOLBO