×

Exploiting efficient representations in large-scale tensor decompositions. (English) Zbl 07045251


MSC:

65-XX Numerical analysis
68-XX Computer science
15A69 Multilinear algebra, tensor calculus
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] E. Acar, D. M. Dunlavy, and T. G. Kolda, A scalable optimization approach for fitting canonical tensor decompositions, J. Chemometrics, 25 (2011), pp. 67–86, .
[2] E. Acar, T. G. Kolda, and D. M. Dunlavy, All-at-once Optimization for Coupled Matrix and Tensor Factorizations, preprint, , 2011.
[3] R. Badeau and R. Boyer, Fast multilinear singular value decomposition for structured tensors, SIAM J. Matrix Anal. Appl., 30 (2008), pp. 1008–1021, . · Zbl 1168.65339
[4] B. Bader and T. G. Kolda, Efficient MATLAB computations with sparse and factored tensors, SIAM J. Sci. Comput., 30 (2007), pp. 205–231, . · Zbl 1159.65323
[5] H. N. Bharath, D. Sima, N. Sauwen, U. Himmelreich, L. De Lathauwer, and S. Van Huffel, Nonnegative canonical polyadic decomposition for tissue-type differentiation in gliomas, IEEE J. Biomed. Health Inform., 21 (2017), pp. 1124–1132, .
[6] R. Bro, Multi-way Analysis in the Food Industry: Models, Algorithms, and Applications, Ph.D. thesis, University of Amsterdam, Amsterdam, The Netherlands, 1998.
[7] R. Bro and C. A. Andersson, Improving the speed of multiway algorithms: Part II: Compression, Chemometr. Intell. Lab., 42 (1998), pp. 105–113, .
[8] R. Bro, R. A. Harshman, N. D. Sidiropoulos, and M. E. Lundy, Modeling multi-way data with linearly dependent loadings, J. Chemometrics, 23 (2009), pp. 324–340, .
[9] C. Caiafa and A. Cichocki, Generalizing the column-row matrix decomposition to multi-way arrays, Linear Algebra Appl., 433 (2010), pp. 557–573, . · Zbl 1194.15025
[10] D. Callaerts, B. De Moor, J. Vandewalle, W. Sansen, G. Vantrappen, and J. Janssens, Comparison of SVD methods to extract the foetal electrocardiogram from cutaneous electrode signals, Med. Biol. Eng. Comput., 28 (1990), pp. 217–224, .
[11] J. D. Carroll and J.-J. Chang, Analysis of individual differences in multidimensional scaling via an n-way generalization of “Eckart–Young” decomposition, Psychometrika, 35 (1970), pp. 283–319, . · Zbl 0202.19101
[12] J. D. Carroll, S. Pruzansky, and J. B. Kruskal, CANDELINC: A general approach to multidimensional analysis of many-way arrays with linear constraints on parameters, Psychometrika, 45 (1980), pp. 3–24, . · Zbl 0478.62050
[13] J. H. Choi and S. V. N. Vishwanathan, DFacTo: Distributed factorization of tensors, in Proceedings of the 27th International Conference on Neural Information Processing Systems, NIPS’14, Cambridge, MA, USA, 2014, MIT, Cambrige, MA, pp. 1296–1304.
[14] A. Cichocki, D. Mandic, A.-H. Phan, C. Caiafa, G. Zhou, Q. Zhao, and L. De Lathauwer, Tensor decompositions for signal processing applications: From two-way to multiway component analysis, IEEE Signal Process. Mag., 32 (2015), pp. 145–163, .
[15] J. E. Cohen, R. Cabral Farias, and P. Comon, Fast decomposition of large nonnegative tensors, IEEE Signal Process. Lett., 22 (2015), pp. 862–866, .
[16] P. Comon and C. Jutten, Handbook of Blind Source Separation: Independent Component Analysis and Applications, Academic Press, Oxford, 2010.
[17] A. de Almeida, G. Favier, and J. C. M. Mota, A constrained factor decomposition with application to MIMO antenna systems, IEEE Trans. Signal Process., 56 (2008), pp. 2429–2442, . · Zbl 1390.94809
[18] L. De Lathauwer, Decompositions of a higher-order tensor in block terms — Part II: Definitions and uniqueness, SIAM J. Matrix Anal. Appl., 30 (2008), pp. 1033–1066, . · Zbl 1177.15032
[19] L. De Lathauwer, Blind separation of exponential polynomials and the decomposition of a tensor in rank-\((L_r,L_r,1)\) terms, SIAM J. Matrix Anal. Appl., 32 (2011), pp. 1451–1474, . · Zbl 1239.15016
[20] L. De Lathauwer, B. de Moor, and J. Vandewalle, Fetal electrocardiogram extraction by blind source subspace separation, IEEE Trans. Biomed. Eng., 47 (2000), pp. 567–572, .
[21] L. De Lathauwer, B. De Moor, and J. Vandewalle, A multilinear singular value decomposition, SIAM J. Matrix Anal. Appl., 21 (2000), pp. 1253–1278, . · Zbl 0962.15005
[22] L. De Lathauwer, B. De Moor, and J. Vandewalle, On the best rank-\(1\) and rank-\((R_1, R_2, …, R_N)\) approximation of higher-order tensors, SIAM J. Matrix Anal. Appl., 21 (2000), pp. 1324–1342, . · Zbl 0958.15026
[23] L. De Lathauwer and D. Nion, Decompositions of a higher-order tensor in block terms — Part III: Alternating least squares algorithms, SIAM J. Matrix Anal. Appl., 30 (2008), pp. 1067–1083, . · Zbl 1177.15033
[24] B. De Moor, DaISy: Database for the identification of systems, Department of Electrical Engineering, ESAT/SISTA, KU Leuven, Belgium, , July, 1. 2018. (Used dataset: cutaneous potential recordings of a pregnant woman, biomedial systems, 96-012).
[25] O. Debals and L. De Lathauwer, The Concept of Tensorization, Technical Report 17–99, ESAT-STADIUS, KU Leuven, Belgium, 2017, .
[26] O. Debals, L. De Lathauwer, and M. Van Barel, About Higher-Order Löwner Tensors, Technical Report 17–98, ESAT-STADIUS, KU Leuven, Leuven, Belgium, 2017, .
[27] O. Debals, M. Van Barel, and L. De Lathauwer, Löwner-based blind signal separation of rational functions with applications, IEEE Trans. Signal Process., 64 (2016), pp. 1909–1918, . · Zbl 1414.94156
[28] W. Ding, L. Qi, and Y. Wei, Fast Hankel tensor-vector product and its application to exponential data fitting, Numer. Linear Algebra Appl., 22 (2015), pp. 814–832, . · Zbl 1349.65070
[29] I. Gohberg and V. Olshevsky, Complexity of multiplication with vectors for structured matrices, Linear Algebra Appl., 202 (1994), pp. 163–192, . · Zbl 0803.65053
[30] I. Gohberg and V. Olshevsky, Fast algorithms with preprocessing for matrix-vector multiplication problems, J. Complexity, 10 (1994), pp. 411–427, . · Zbl 0820.68051
[31] L. Grasedyck, Hierarchical singular value decomposition of tensors, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 2029–2054, . · Zbl 1210.65090
[32] L. Grasedyck, D. Kressner, and C. Tobler, A literature survey of low-rank tensor approximation techniques, GAMM-Mitt., 36 (2013), pp. 53–78, . · Zbl 1279.65045
[33] W. Hackbusch, Tensor Spaces and Numerical Tensor Calculus, Springer Ser. Comput. Math. 42, Springer, Heidelberg, 2012, . · Zbl 1244.65061
[34] W. Hackbusch, B. N. Khoromskij, and E. E. Tyrtyshnikov, Hierarchical Kronecker tensor-product approximations, J. Numer. Math., 13 (2005), pp. 119–156, . · Zbl 1081.65035
[35] W. Hackbusch and S. Kühn, A new scheme for the tensor representation, J. Fourier Anal. Appl., 15 (2009), pp. 706–722, . · Zbl 1188.15022
[36] F. L. Hitchcock, The expression of a tensor or a polyadic as a sum of products, Journal of Mathematics and Physics, 6 (1927), pp. 164–189, . · JFM 53.0095.01
[37] S. Holtz, T. Rohwedder, and R. Schneider, The alternating linear scheme for tensor optimization in the Tensor Train format, SIAM J. Sci. Comput., 34 (2012), pp. A683–A713, . · Zbl 1252.15031
[38] K. Huang, N. D. Sidiropoulos, and A. P. Liavas, A flexible and efficient algorithmic framework for constrained matrix and tensor factorization, IEEE Trans. Signal Process., 64 (2016), pp. 5052–5065, . · Zbl 1414.94253
[39] M. Ishteva, P.-A. Absil, S. Van Huffel, and L. De Lathauwer, Best low multilinear rank approximation of higher-order tensors, based on the Riemannian trust-region scheme, SIAM J. Matrix Anal. Appl., 32 (2011), pp. 115–135, . · Zbl 1218.65041
[40] M. Ishteva, L. De Lathauwer, P.-A. Absil, and S. Van Huffel, The best rank-\((R_1,R_2,R_3)\) approximation of tensors by means of a geometric Newton method, AIP Conference Proceedings, 1048 (2008), pp. 274–277, . · Zbl 1167.65363
[41] B. Jeon, I. Jeon, L. Sael, and U. Kang, SCouT: Scalable coupled matrix-tensor factorization — algorithm and discoveries, in 2016 IEEE 32nd International Conference on Data Engineering (ICDE), IEEE, 2016, pp. 811–822, .
[42] I. Jeon, E. E. Papalexakis, U. Kang, and C. Faloutsos, HaTen2: Billion-scale tensor decompositions, in 2015 IEEE 31st International Conference on Data Engineering, IEEE, 2015, pp. 1047–1058, .
[43] U. Kang, E. E. Papalexakis, A. Harpale, and C. Faloutsos, GigaTensor: Scaling tensor analysis up by 100 times - algorithms and discoveries, Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD ’12, ACM, New York, 2012, pp. 316–324, .
[44] O. Kaya and B. Uçar, Scalable sparse tensor decompositions in distributed memory systems, in Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis on - SC ’15, ACM, New York, 2015, 77, .
[45] O. Kaya and B. Uçar, High performance parallel algorithms for the Tucker decomposition of sparse tensors, in 2016 45th International Conference on Parallel Processing (ICPP), IEEE, 2016, pp. 103–112, .
[46] C. Kelley, Iterative Methods for Optimization, SIAM, Philadelphia, 1999, . · Zbl 0934.90082
[47] B. N. Khoromskij, Structured rank-\((r_1, …, r_D)\) decomposition of function-related tensors in \({R}^D\), Comput. Methods Appl. Math., 6 (2006), pp. 194–220, . · Zbl 1120.65052
[48] B. N. Khoromskij and V. Khoromskaia, Low rank Tucker-type tensor approximation to classical potentials, Cent. Eur. J. Math., 5 (2007), pp. 523–550, . · Zbl 1130.65060
[49] B. N. Khoromskij and V. Khoromskaia, Multigrid accelerated tensor approximation of function related multidimensional arrays, SIAM J. Sci. Comput., 31 (2009), pp. 3002–3026, . · Zbl 1197.65215
[50] H. A. L. Kiers and R. A. Harshman, Relating two proposed methods for speedup of algorithms for fitting two- and three-way principal component and related multilinear models, Chemometr. Intell. Lab., 36 (1997), pp. 31–40, .
[51] T. G. Kolda, Orthogonal tensor decompositions, SIAM J. Matrix Anal. Appl., 23 (2001), pp. 243–255, . · Zbl 1005.15020
[52] T. G. Kolda and B. Bader, Tensor Decompositions and Applications, SIAM Rev., 51 (2009), pp. 455–500, .
[53] T. G. Kolda and J. Sun, Scalable tensor decompositions for multi-aspect data mining, 2008 Eighth IEEE International Conference on Data Mining, 2008, .
[54] P. M. Kroonenberg and J. de Leeuw, Principal component analysis of three-mode data by means of alternating least squares algorithms, Psychometrika, 45 (1980), pp. 69–97, . · Zbl 0431.62035
[55] A. P. Liavas and N. D. Sidiropoulos, Parallel algorithms for constrained tensor factorization via alternating direction method of multipliers, IEEE Trans. Signal Process., 63 (2015), pp. 5450–5463, . · Zbl 1394.94321
[56] M. W. Mahoney, M. Maggioni, and P. Drineas, Tensor-CUR decompositions for tensor-based data, SIAM J. Matrix Anal. Appl., 30 (2008), pp. 957–987, . · Zbl 1168.65340
[57] T. Müller, K. Kruppa, G. Lichtenberg, and N. Réhault, Fault detection with qualitative models reduced by tensor decomposition methods, IFAC-PapersOnLine, 48 (2015), pp. 416–421, .
[58] J. Nocedal and S. J. Wright, Numerical Optimization, 2nd ed., Springer, New York, 2006. · Zbl 1104.65059
[59] R. Orús, A practical introduction to tensor networks: Matrix product states and projected entangled pair states, Ann. Physics, 349 (2014), pp. 117–158, . · Zbl 1343.81003
[60] I. V. Oseledets, Tensor-train decomposition, SIAM J. Sci. Comput., 33 (2011), pp. 2295–2317, . · Zbl 1232.15018
[61] I. V. Oseledets and S. Dolgov, Solution of linear systems and matrix inversion in the TT-format, SIAM J. Sci. Comput., 34 (2012), pp. A2718–A2739, . · Zbl 1259.65071
[62] I. V. Oseledets, S. Dolgov, V. Kazeev, D. V. Savostyanov, O. Lebedeva, P. Zhlobich, T. Mach, and L. Song, TT-Toolbox, available online at .
[63] I. V. Oseledets, D. V. Savostianov, and E. E. Tyrtyshnikov, Tucker dimensionality reduction of three-dimensional arrays in linear time, SIAM J. Matrix Anal. Appl., 30 (2008), pp. 939–956, . · Zbl 1180.15025
[64] I. V. Oseledets, D. V. Savostyanov, and E. E. Tyrtyshnikov, Linear algebra for tensor problems, Computing, 85 (2009), pp. 169–188, . · Zbl 1172.65018
[65] I. V. Oseledets and E. E. Tyrtyshnikov, Breaking the curse of dimensionality, or how to use SVD in many dimensions, SIAM J. Sci. Comput., 31 (2009), pp. 3744–3759, . · Zbl 1200.65028
[66] I. V. Oseledets and E. E. Tyrtyshnikov, TT-cross approximation for multidimensional arrays, Linear Algebra Appl., 432 (2010), pp. 70–88, . · Zbl 1183.65040
[67] E. E. Papalexakis, C. Faloutsos, and N. D. Sidiropoulos, ParCube: Sparse parallelizable CANDECOMP-PARAFAC tensor decomposition, ACM Trans. Knowl. Discov. Data, 10 (2015), pp. 1–25, .
[68] J. M. Papy, L. De Lathauwer, and S. Van Huffel, Exponential data fitting using multilinear algebra: The single-channel and multi-channel case, Numer. Linear Algebra Appl., 12 (2005), pp. 809–826, . · Zbl 1164.93012
[69] A.-H. Phan, P. Tichavský, and A. Cichocki, Fast alternating LS algorithms for high order CANDECOMP/PARAFAC tensor factorizations, IEEE Trans. Signal Process., 61 (2013), pp. 4834–4846, .
[70] M. J. Reynolds, G. Beylkin, and A. Doostan, Optimization via separated representations and the canonical tensor decomposition, J. Comput. Phys., 348 (2017), pp. 220–230, . · Zbl 1380.65112
[71] J.-P. Royer, N. Thirion-Moreau, and P. Comon, Computing the polyadic decomposition of nonnegative third order tensors, Signal Processing, 91 (2011), pp. 2159–2171, . · Zbl 1219.94048
[72] D. V. Savostyanov, Fast revealing of mode ranks of tensor in canonical form, Numer. Math. Theor. Meth. Appl, 2 (2009), pp. 439–444, . · Zbl 1212.65182
[73] D. V. Savostyanov, E. E. Tyrtyshnikov, and N. L. Zamarashkin, Fast truncation of mode ranks for bilinear tensor operations, Numer. Linear Algebra Appl., 19 (2011), pp. 103–111, . · Zbl 1274.15041
[74] N. D. Sidiropoulos, R. Bro, and G. B. Giannakis, Parallel factor analysis in sensor array processing, IEEE Trans. Signal Process., 48 (2000), pp. 2377–2388, .
[75] N. D. Sidiropoulos, L. De Lathauwer, X. Fu, K. Huang, E. E. Papalexakis, and C. Faloutsos, Tensor decomposition for signal processing and machine learning, IEEE Trans. Signal Process., 65 (2017), pp. 3551–3582, . · Zbl 1415.94232
[76] N. D. Sidiropoulos, E. E. Papalexakis, and C. Faloutsos, Parallel randomly compressed cubes: A scalable distributed architecture for big tensor decomposition, IEEE Signal Process. Mag., 31 (2014), pp. 57–70, .
[77] S. Smith and G. Karypis, Tensor-matrix products with a compressed sparse tensor, in Proceedings of the 5th Workshop on Irregular Applications Architectures and Algorithms - IA3 ’15, ACM, New York, 2015, 5, .
[78] S. Smith and G. Karypis, A medium-grained algorithm for sparse tensor factorization, in 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS), IEEE, 2016, pp. 902–911, .
[79] S. Smith, N. Ravindran, N. D. Sidiropoulos, and G. Karypis, SPLATT: Efficient and parallel sparse tensor-matrix multiplication, in 2015 IEEE International Parallel and Distributed Processing Symposium, IEEE, 2015, pp. 61–70, .
[80] L. Sorber, I. Domanov, M. Van Barel, and L. De Lathauwer, Exact line and plane search for tensor optimization, Comput. Optim. Appl., 63 (2015), pp. 121–142, . · Zbl 1361.90046
[81] L. Sorber, M. Van Barel, and L. De Lathauwer, Unconstrained optimization of real functions in complex variables, SIAM J. Optim., 22 (2012), pp. 879–898, . · Zbl 1260.90150
[82] L. Sorber, M. Van Barel, and L. De Lathauwer, Optimization-based algorithms for tensor decompositions: Canonical polyadic decomposition, decomposition in rank-\((L_r,L_r,1)\) terms, and a new generalization, SIAM J. Optim., 23 (2013), pp. 695–720, . · Zbl 1277.90073
[83] L. Sorber, M. Van Barel, and L. De Lathauwer, Structured data fusion, IEEE J. Sel. Topics Signal Process., 9 (2015), pp. 586–600, .
[84] G. Tomasi and R. Bro, A comparison of algorithms for fitting the PARAFAC model, Comput. Stat. Data Anal., 50 (2006), pp. 1700 – 1734, . · Zbl 1445.62136
[85] M. Vandecappelle, N. Vervliet, and L. De Lathauwer, Nonlinear least squares updating of the canonical polyadic decomposition, in 2017 25th European Signal Processing Conference (EUSIPCO17), 2017, pp. 693–697, .
[86] N. Vannieuwenhoven, Condition numbers for the tensor rank decomposition, Linear Algebra Appl., 535 (2017), pp. 35–86, . · Zbl 1375.65063
[87] N. Vannieuwenhoven, K. Meerbergen, and R. Vandebril, Computing the gradient in optimization algorithms for the CP decomposition in constant memory through tensor blocking, SIAM J. Sci. Comput., 37 (2015), pp. C415–C438, . · Zbl 1320.65066
[88] N. Vannieuwenhoven, R. Vandebril, and K. Meerbergen, A new truncation strategy for the higher-order singular value decomposition, SIAM J. Sci. Comput., 34 (2012), pp. A1027–A1052, . · Zbl 1247.65055
[89] N. Vervliet and L. De Lathauwer, A randomized block sampling approach to canonical polyadic decomposition of large-scale tensors, IEEE J. Sel. Topics Signal Process., 10 (2016), pp. 284–295, .
[90] N. Vervliet and L. De Lathauwer, Numerical Optimization Based Algorithms for Data Fusion, in Data Fusion Methodology and Applications, M. Cocchi, ed., Elsevier, 2018, accepted for publication.
[91] N. Vervliet, O. Debals, and L. De Lathauwer, Tensorlab 3.0—Numerical optimization strategies for large-scale constrained and coupled matrix/tensor factorization, in 2016 50th Asilomar Conference on Signals, Systems and Computers, 2016, pp. 1733–1738, .
[92] N. Vervliet, O. Debals, and L. De Lathauwer, Canonical Polyadic Decomposition of Incomplete Tensors with Linearly Constrained Factors, Technical Report 16–172, ESAT-STADIUS, KU Leuven, Belgium, 2017, .
[93] N. Vervliet, O. Debals, L. Sorber, and L. De Lathauwer, Breaking the curse of dimensionality using decompositions of incomplete tensors: Tensor-based scientific computing in big data analysis, IEEE Signal Process. Mag., 31 (2014), pp. 71–79, .
[94] N. Vervliet, O. Debals, L. Sorber, M. Van Barel, and L. De Lathauwer, Tensorlab 3.0, 2016, available online at .
[95] Z. Yawen, D. Guangjun, and X. Zhixiang, Hyperspectral image tensor feature extraction based on fusion of multiple spectral-spatial features, in Proceedings of the 2016 International Conference on Intelligent Information Processing - ICIIP ’16, ACM, New York, 2016, 43, .
[96] G. Zhou, A. Cichocki, and S. Xie, Decomposition of Big Tensors with Low Multilinear Rank, preprint, 2014, .
[97] G. Zhou, A. Cichocki, Q. Zhao, and S. Xie, Nonnegative matrix and tensor factorizations: An algorithmic perspective, IEEE Signal Process. Mag., 31 (2014), pp. 54–65, .
[98] G. Zhou, A. Cichocki, Q. Zhao, and S. Xie, Efficient nonnegative Tucker decompositions: Algorithms and uniqueness, IEEE Trans. Image Process., 24 (2015), pp. 4990–5003, . · Zbl 1408.94841
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.