Cogprints

Empirical Evaluation of Four Tensor Decomposition Algorithms

Turney, Peter D. (2007) Empirical Evaluation of Four Tensor Decomposition Algorithms. [Departmental Technical Report] (Unpublished)

Full text available as:

[img]
Preview
 PDF
164Kb

Abstract

Higher-order tensor decompositions are analogous to the familiar Singular Value Decomposition (SVD), but they transcend the limitations of matrices (second-order tensors). SVD is a powerful tool that has achieved impressive results in information retrieval, collaborative filtering, computational linguistics, computational vision, and other fields. However, SVD is limited to two-dimensional arrays of data (two modes), and many potential applications have three or more modes, which require higher-order tensor decompositions. This paper evaluates four algorithms for higher-order tensor decomposition: Higher-Order Singular Value Decomposition (HO-SVD), Higher-Order Orthogonal Iteration (HOOI), Slice Projection (SP), and Multislice Projection (MP). We measure the time (elapsed run time), space (RAM and disk space requirements), and fit (tensor reconstruction accuracy) of the four algorithms, under a variety of conditions. We find that standard implementations of HO-SVD and HOOI do not scale up to larger tensors, due to increasing RAM requirements. We recommend HOOI for tensors that are small enough for the available RAM and MP for larger tensors.

Item Type:Departmental Technical Report
Keywords:tensors, singular value decomposition, Tucker decomposition, tensor decomposition, latent semantic analysis
Subjects:Computer Science > Language
Computer Science > Statistical Models
Linguistics > Computational Linguistics
Computer Science > Machine Learning
Computer Science > Artificial Intelligence
ID Code:5841
Deposited By: Turney, Peter
Deposited On:22 Nov 2007 21:41
Last Modified:11 Mar 2011 08:57

References in Article

Select the SEEK icon to attempt to find the referenced article. If it does not appear to be in cogprints you will be forwarded to the paracite service. Poorly formated references will probably not work.

E. Acar and B. Yener. 2007. Unsupervised multiway data analysis: A literature survey. Technical report, Computer Science Department, Rensselaer Polytechnic Institute, Troy, NY.

O. Alter, P.O. Brown, and D. Botstein. 2000. Singular value decomposition for genome-wide expression data processing and modeling. Proceedings of the National Academy of Sciences, 97(18):10101–10106.

B.W. Bader and T.G. Kolda. 2007a. Efficient MATLAB computations with sparse and factored tensors. SIAM Journal on Scientific Computing.

B.W. Bader and T.G. Kolda. 2007b. MATLAB Tensor Toolbox version 2.2.

D. Billsus and M.J. Pazzani. 1998. Learning collaborative information filters. Proceedings of the Fifteenth International Conference on Machine Learning, pages 46–54.

M. Brand. 2002. Incremental singular value decomposition of uncertain data with missing values. Proceedings of the 7th European Conference on Computer Vision, pages 707–720.

R. Bro and C.A. Andersson. 1998. Improving the speed of multiway algorithms – Part II: Compression. Chemometrics and Intelligent Laboratory Systems, 42(1):105–113.

J.D. Carroll and J.J. Chang. 1970. Analysis of individual differences in multidimensional scaling via an n-way generalization of "Eckart-Young" decomposition. Psychometrika, 35(3):283–319.

P.A. Chew, B.W. Bader, T.G. Kolda, and A. Abdelali. 2007. Cross-language information retrieval using PARAFAC2. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 143–152.

L. De Lathauwer, B. De Moor, and J. Vandewalle. 2000a. A multilinear singular value decomposition. SIAM Journal on Matrix Analysis and Applications, 21:1253–1278.

L. De Lathauwer, B. DeMoor, and J. Vandewalle. 2000b. On the best rank-1 and rank-(R1,R2, ..., RN) approximation of higher-order tensors. SIAM Journal on Matrix Analysis and Applications, 21:1324–1342.

S. Deerwester, S.T. Dumais, G.W. Furnas, T.K. Landauer, and R. Harshman. 1990. Indexing by latent semantic analysis. Journal of the American Society for Information Science, 41(6):391–407.

D.M. Dunlavy, T.G. Kolda, and W.P. Kegelmeyer. 2006. Multilinear algebra for analyzing data with multiple linkages. Technical Report SAND2006-2079, Sandia National Laboratories, Livermore, CA.

R.A. Harshman. 1970. Foundations of the PARAFAC procedure: Models and conditions for an "explanatory" multi-modal factor analysis. UCLA Working Papers in Phonetics, 16:1–84.

T.G. Kolda. 2006. Multilinear operators for higher-order decompositions. Technical Report SAND2006-2081, Sandia National Laboratories, Livermore, CA.

T.K. Landauer and S.T. Dumais. 1997. A solution to Plato’s problem: The latent semantic analysis theory of acquisition, induction, and representation of knowledge. Psychological Review, 104(2):211–240.

M.W. Mahoney, M. Maggioni, and P. Drineas. 2006. Tensor-CUR decompositions for tensor-based data. Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 327–336.

C.K. Ogden. 1930. Basic English: A general introduction with rules and grammar. Kegan Paul, Trench, Trubner and Co., London.

H. Schuetze. 1998. Automatic word sense discrimination. Computational Linguistics, 24(1):97–123.

J. Sun, D. Tao, and C. Faloutsos. 2006. Beyond streams and graphs: Dynamic tensor analysis. Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 374–383.

L.R. Tucker. 1966. Some mathematical notes on three-mode factor analysis. Psychometrika, 31(3):279–311.

P.D. Turney. 2006. Similarity of semantic relations. Computational Linguistics, 32(3):379–416.

H. Wang and N. Ahuja. 2005. Rank-R approximation of tensors: Using image-as-matrix representation. Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05), 2:346–353.

H.Wang, Q.Wu, L. Shi, Y. Yu, and N. Ahuja. 2005. Out-of-core tensor approximation of multi-dimensional matrices of visual data. International Conference on Computer Graphics and Interactive Techniques, SIGGRAPH

2005, 24:527–535.

Y. Xu, L. Zhang, and W. Liu. 2006. Cubic analysis of social bookmarking for personalized recommendation. Lecture Notes in Computer Science: Frontiers of WWW Research and Development – APWeb 2006, 3841:733–738.

Metadata

Repository Staff Only: item control page

Cogprints is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.