--- 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.' altloc: [] chapter: ~ commentary: ~ commref: ~ confdates: ~ conference: ~ confloc: ~ contact_email: ~ creators_id: - peter.turney@nrc-cnrc.gc.ca creators_name: - family: Turney given: Peter D. honourific: '' lineage: '' date: 2007-11-12 date_type: completed datestamp: 2007-11-22 21:41:22 department: Institute for Information Technology dir: disk0/00/00/58/41 edit_lock_since: ~ edit_lock_until: ~ edit_lock_user: ~ editors_id: [] editors_name: [] eprint_status: archive eprintid: 5841 fileinfo: /style/images/fileicons/application_pdf.png;/5841/1/NRC%2D49877.pdf full_text_status: public importid: ~ institution: National Research Council of Canada isbn: ~ ispublished: unpub issn: ~ item_issues_comment: [] item_issues_count: 0 item_issues_description: [] item_issues_id: [] item_issues_reported_by: [] item_issues_resolved_by: [] item_issues_status: [] item_issues_timestamp: [] item_issues_type: [] keywords: 'tensors, singular value decomposition, Tucker decomposition, tensor decomposition, latent semantic analysis' lastmod: 2011-03-11 08:57:00 latitude: ~ longitude: ~ metadata_visibility: show note: ~ number: ~ pagerange: ~ pubdom: FALSE publication: ~ publisher: ~ refereed: FALSE referencetext: "E. Acar and B. Yener. 2007. Unsupervised multiway data analysis: A literature survey. Technical report, Computer Science Department, Rensselaer Polytechnic Institute, Troy, NY.\r\nO. 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.\r\nB.W. Bader and T.G. Kolda. 2007a. Efficient MATLAB computations with sparse and factored tensors. SIAM Journal on Scientific Computing.\r\nB.W. Bader and T.G. Kolda. 2007b. MATLAB Tensor Toolbox version 2.2.\r\nD. Billsus and M.J. Pazzani. 1998. Learning collaborative information filters. Proceedings of the Fifteenth International Conference on Machine Learning, pages 46–54.\r\nM. 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\nR. Bro and C.A. Andersson. 1998. Improving the speed of multiway algorithms – Part II: Compression. Chemometrics and Intelligent Laboratory Systems, 42(1):105–113.\r\nJ.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.\r\nP.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.\r\nL. De Lathauwer, B. De Moor, and J. Vandewalle. 2000a. A multilinear singular value decomposition. SIAM Journal on Matrix Analysis and Applications, 21:1253–1278.\r\nL. 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.\r\nS. 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.\r\nD.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\nR.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.\r\nT.G. Kolda. 2006. Multilinear operators for higher-order decompositions. Technical Report SAND2006-2081, Sandia National Laboratories, Livermore, CA.\r\nT.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.\r\nM.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.\r\nC.K. Ogden. 1930. Basic English: A general introduction with rules and grammar. Kegan Paul, Trench, Trubner and Co., London.\r\nH. Schuetze. 1998. Automatic word sense discrimination. Computational Linguistics, 24(1):97–123.\r\nJ. 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.\r\nL.R. Tucker. 1966. Some mathematical notes on three-mode factor analysis. Psychometrika, 31(3):279–311.\r\nP.D. Turney. 2006. Similarity of semantic relations. Computational Linguistics, 32(3):379–416.\r\nH. 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.\r\nH.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\r\n2005, 24:527–535.\r\nY. 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.\r\n" relation_type: [] relation_uri: [] reportno: 'ERB-1152, NRC-49877' rev_number: 30 series: ~ source: ~ status_changed: 2007-11-22 21:41:22 subjects: - comp-sci-lang - comp-sci-stat-model - ling-comput - comp-sci-mach-learn - comp-sci-art-intel succeeds: ~ suggestions: ~ sword_depositor: ~ sword_slug: ~ thesistype: ~ title: Empirical Evaluation of Four Tensor Decomposition Algorithms type: techreport userid: 2175 volume: ~