×

Computing dense tensor decompositions with optimal dimension trees. (English) Zbl 1421.68259

Summary: Dense tensor decompositions have been widely used in many signal processing problems including analyzing speech signals, identifying the localization of signal sources, and many other communication applications. Computing these decompositions poses major computational challenges for big datasets emerging in these domains. CANDECOMP/PARAFAC (CP) and Tucker formulations are the prominent tensor decomposition schemes heavily used in these fields, and the algorithms for computing them involve applying two core operations, namely tensor-times-matrix and tensor-times-vector multiplication, which are executed repetitively within an iterative framework. In the recent past, efficient computational schemes using a data structure called dimension tree, are employed to significantly reduce the cost of these two operations, through storing and reusing partial results that are commonly used across different iterations of these algorithms. This framework has been introduced for sparse CP and Tucker decompositions in the literature, and a recent work investigates using an optimal binary dimension tree structure in computing dense Tucker decompositions. In this paper, we investigate finding an optimal dimension tree for both CP and Tucker decompositions. We show that finding an optimal dimension tree for an \(N\)-dimensional tensor is NP-hard for both decompositions, provide faster exact algorithms for finding an optimal dimension tree in \(O(3^N)\) time using \(O(2^N)\) space for the Tucker case, and extend the algorithm to the case of CP decomposition with the same time and space complexities.

MSC:

68W40 Analysis of algorithms
15A69 Multilinear algebra, tensor calculus
65F30 Other matrix algorithms (MSC2010)
68P05 Data structures
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
PDF BibTeX XML Cite
Full Text: DOI Link

References:

[1] Acar, E.; Dunlavy, DM; Kolda, TG, A scalable optimization approach for fitting canonical tensor decompositions, J. Chemom., 25, 67-86, (2011)
[2] Andersson, CA; Bro, R., The N-way toolbox for MATLAB, Chemom. Intell. Lab. Syst., 52, 1-4, (2000)
[3] Bader, BW; Kolda, TG, Efficient MATLAB computations with sparse and factored tensors, SIAM J. Sci. Comput., 30, 205-231, (2007) · Zbl 1159.65323
[4] Bader, B.W., Kolda, T.G., et al.: Matlab tensor toolbox version 2.6. Available online (2015)
[5] Baskaran, M., Meister, B., Vasilache, N., Lethin, R.: Efficient and scalable computations with sparse tensors. In: Proceedings of the IEEE Conference on High Performance Extreme Computing, HPEC 2012, pp. 1-6 (2012). https://doi.org/10.1109/HPEC.2012.6408676
[6] Carlson, A., Betteridge, J., Kisiel, B., Settles, B., Jr., E.R.H., Mitchell, T.M.: Toward an architecture for never-ending language learning. In: Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI ’10, pp. 1306-1313. AAAI Press (2010). http://dl.acm.org/citation.cfm?id=2898607.2898816
[7] Carroll, DJ; Chang, J., Analysis of individual differences in multidimensional scaling via an N-way generalization of “Eckart-Young” decomposition, Psychometrika, 35, 283-319, (1970) · Zbl 0202.19101
[8] Chakaravarthy, V.T., Choi, J., Joseph, D.J., Liu, X., Murali, P., Sabharwal, Y., Sreedhar, D.: On optimizing distributed tucker decomposition for dense tensors. In: Proceedings of the IEEE International Symposium on Parallel and Distributed Processing, IPDPS ’17, Orlando, FL, USA (2017)
[9] Choi, J.H., Vishwanathan, S.V.N.: DFacTo: distributed factorization of tensors. In: 27th Advances in Neural Information Processing Systems, Montreal, Quebec, Canada, pp. 1296-1304 (2014)
[10] Grasedyck, L., Hierarchical singular value decomposition of tensors, SIAM J. Matrix Anal. Appl., 31, 2029-2054, (2010) · Zbl 1210.65090
[11] Harshman, R.A.: Foundations of the PARAFAC procedure: models and conditions for an “explanatory” multi-modal factor analysis. UCLA Working Papers in Phonetics 16, 1-84 (1970)
[12] Håstad, J., Tensor rank is np-complete, J. Algorithms, 11, 644-654, (1990) · Zbl 0716.65043
[13] Kang, U., Papalexakis, E., Harpale, A., Faloutsos, C.: GigaTensor: Scaling tensor analysis up by 100 times—algorithms and discoveries. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’12, pp. 316-324. ACM, New York (2012)
[14] Kaya, O., Uçar, B.: High-performance parallel algorithms for the Tucker decomposition of higher order sparse tensors. Technical Report RR-8801, Inria, Grenoble-Rhône-Alpes (2015)
[15] Kaya, O., Uçar, B.: Scalable sparse tensor decompositions in distributed memory systems. Technical Report RR-8722, Inria, Grenoble-Rhône-Alpes (2015)
[16] Kaya, O., Uçar, B.: Scalable sparse tensor decompositions in distributed memory systems. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC ’15, pp. 77:1-77:11. ACM, New York (2015). https://doi.org/10.1145/2807591.2807624
[17] Kaya, O., Uçar, B.: High performance parallel algorithms for the Tucker decomposition of sparse tensors. In: Proceedings of the 45th International Conference on Parallel Processing, ICPP ’16, pp. 103-112 (2016). https://doi.org/10.1109/ICPP.2016.19
[18] Kaya, O., Uçar, B.: Parallel CP decomposition of sparse tensors using dimension trees. Research Report RR-8976, Inria - Research Centre Grenoble-Rhône-Alpes (2016)
[19] Kolda, T.G., Bader, B.: The TOPHITS model for higher-order web link analysis. In: Proceedings of Link Analysis, Counterterrorism and Security, pp. 26-29 (2006)
[20] Kolda, TG; Bader, B., Tensor decompositions and applications, SIAM Rev., 51, 455-500, (2009) · Zbl 1173.65029
[21] Lathauwer, L.D., Moor, B.D.: From matrix to tensor: Multilinear algebra and signal processing. In: Proceedings of the Institute of Mathematics and Its Applications Conference Series, vol. 67, pp. 1-16 (1998)
[22] Lathauwer, LD; Moor, BD; Vandewalle, J., A multilinear singular value decomposition, SIAM J. Matrix Anal. Appl., 21, 1253-1278, (2000) · Zbl 0962.15005
[23] Li, J., Choi, J., Perros, I., Sun, J., Vuduc, R.: Model-driven sparse CP decomposition for higher-order tensors. In: Proceedings of the IEEE International Symposium on Parallel and Distributed Processing, IPDPS ’17, Orlando, FL, USA, pp. 1048-1057 (2017)
[24] Ng, C.; Barketau, M.; Cheng, T.; Kovalyov, MY, Product partition and related problems of scheduling and systems reliability: computational complexity and approximation, Eur. J. Oper. Res., 207, 601-604, (2010) · Zbl 1205.68174
[25] Nion, D.; Mokios, KN; Sidiropoulos, ND; Potamianos, A., Batch and adaptive PARAFAC-based blind separation of convolutive speech mixtures, IEEE Trans. Audio Speech Lang. Process., 18, 1193-1207, (2010)
[26] Nion, D.; Sidiropoulos, ND, Tensor algebra and multidimensional harmonic retrieval in signal processing for mimo radar, IEEE Trans. Signal Process., 58, 5693-5705, (2010) · Zbl 1392.94361
[27] Perros, I., Chen, R., Vuduc, R., Sun, J.: Sparse hierarchical Tucker factorization and its application to healthcare. In: Proceedings of the 2015 IEEE International Conference on Data Mining, ICDM 2015, pp. 943-948 (2015)
[28] Phan, AH; Tichavský, P.; Cichocki, A., Fast alternating LS algorithms for high order CANDECOMP/PARAFAC tensor factorizations, IEEE Trans. Signal Process., 61, 4834-4846, (2013)
[29] Rendle, S., Lars, T.S.: Pairwise interaction tensor factorization for personalized tag recommendation. In: Proceedings of the Third ACM International Conference on Web Search and Data Mining, WSDM ’10, pp. 81-90. ACM, New York (2010). https://doi.org/10.1145/1718487.1718498
[30] Rendle, S., Leandro, B.M., Nanopoulos, A., Schmidt-Thieme, L.: Learning optimal ranking with tensor factorization for tag recommendation. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’09, pp. 727-736. ACM, New York (2009). https://doi.org/10.1145/1557019.1557100
[31] Sidiropoulos, ND; Bro, R.; Giannakis, GB, Parallel factor analysis in sensor array processing, IEEE Trans. Signal Process., 48, 2377-2388, (2000)
[32] Smith, S., Karypis, G.: A medium-grained algorithm for sparse tensor factorization. In: 2016 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2016, Chicago, IL, USA, May 23-27, 2016, pp. 902-911 (2016)
[33] Smith, S., Ravindran, N., Sidiropoulos, N.D., Karypis, G.: SPLATT: Efficient and parallel sparse tensor-matrix multiplication. In: Proceedings of the 29th IEEE International Parallel and Distributed Processing Symposium, IPDPS ’15, pp. 61-70. IEEE Computer Society, Hyderabad (2015)
[34] Symeonidis, P., Nanopoulos, A., Manolopoulos, Y.: Tag recommendations based on tensor dimensionality reduction. In: Proceedings of the 2008 ACM Conference on Recommender Systems, RecSys ’08, pp. 43-50. ACM, New York (2008). https://doi.org/10.1145/1454008.1454017
[35] Vasilescu, M.A.O., Terzopoulos, D.: Multilinear analysis of image ensembles: TensorFaces. In: Computer Vision—ECCV 2002, pp. 447-460. Springer, Berlin (2002) · Zbl 1034.68693
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.