The condition number of many tensor decompositions is invariant under Tucker compression. (English) Zbl 1523.65040
Summary: We characterise the sensitivity of several additive tensor decompositions with respect to perturbations of the original tensor. These decompositions include canonical polyadic decompositions, block term decompositions, and sums of tree tensor networks. Our main result shows that the condition number of all these decompositions is invariant under Tucker compression. This result can dramatically speed up the computation of the condition number in practical applications. We give the example of an \(265\times 371\times 7\) tensor of rank 3 from a food science application whose condition number was computed in 6.9 milliseconds by exploiting our new theorem, representing a speedup of four orders of magnitude over the previous state of the art.
MSC:
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
| 65F55 | Numerical methods for low-rank matrix approximation; matrix compression |
| 15A69 | Multilinear algebra, tensor calculus |
Keywords:
structured block term decomposition; sum of tensor trains; condition number; Tucker compression; invarianceSoftware:
JuliaReferences:
| [1] | Kolda, TG; Bader, BW, Tensor decompositions and applications, SIAM Review, 51, 3, 455-500 (2009) · Zbl 1173.65029 · doi:10.1137/07070111X |
| [2] | Sidiropoulos, ND; De Lathauwer, L.; Fu, X.; Huang, K.; Papalexakis, EE; Faloutsos, C., Tensor Decomposition for Signal Processing and Machine Learning, IEEE Transactions on Signal Processing, 65, 13, 3551-3582 (2017) · Zbl 1415.94232 · doi:10.1109/TSP.2017.2690524 |
| [3] | Breiding, P.; Vannieuwenhoven, N., The Condition Number of Join Decompositions, SIAM Journal on Matrix Analysis and Applications, 39, 1, 287-309 (2018) · Zbl 1384.49035 · doi:10.1137/17M1142880 |
| [4] | Hitchcock, FL, The Expression of a Tensor or a Polyadic as a Sum of Products, Journal of Mathematics and Physics, 6, 1-4, 164-189 (1927) · JFM 53.0095.01 · doi:10.1002/sapm192761164 |
| [5] | De Lathauwer, L., Decompositions of a Higher-Order Tensor in Block Terms-Part II: Definitions and Uniqueness, SIAM Journal on Matrix Analysis and Applications, 30, 3, 1033-1066 (2008) · Zbl 1177.15032 · doi:10.1137/070690729 |
| [6] | Oseledets, IV, Tensor-Train Decomposition, SIAM Journal on Scientific Computing, 33, 5, 2295-2317 (2011) · Zbl 1232.15018 · doi:10.1137/090752286 |
| [7] | Ehrlacher, V., Fuente-Ruiz, M., Lombardi, D.: SoTT: greedy approximation of a tensor as a sum of Tensor Trains (2021) · Zbl 1492.65108 |
| [8] | Hackbusch, W.; Kühn, S., A new scheme for the tensor representation, Journal of Fourier Analysis and Applications, 15, 5, 706-722 (2009) · Zbl 1188.15022 · doi:10.1007/s00041-009-9094-9 |
| [9] | Grasedyck, L., Hierarchical singular value decomposition of tensors, SIAM Journal on Matrix Analysis and Applications, 31, 4, 2029-2054 (2010) · Zbl 1210.65090 · doi:10.1137/090764189 |
| [10] | Andersen, CM; Bro, R., Practical aspects of PARAFAC modeling of fluorescence excitation-emission data, Journal of Chemometrics, 17, 4, 200-215 (2003) · doi:10.1002/cem.790 |
| [11] | Harshman, R.a.: Foundations of the PARAFAC procedure: Models and conditions for an “explanatory” multimodal factor analysis. UCLA Working Papers in Phonetics 16(10), 1-84 (1970) |
| [12] | De Lathauwer, L.; De Moor, B.; Vandewalle, J., A multilinear singular value decomposition, SIAM Journal on Matrix Analysis and Applications, 21, 4, 1253-1278 (2000) · Zbl 0962.15005 · doi:10.1137/S0895479896305696 |
| [13] | Tucker, LR, Some mathematical notes on three-mode factor analysis, Psychometrika, 31, 3, 279-311 (1966) · doi:10.1007/BF02289464 |
| [14] | de Silva, V.; Lim, L-H, Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem, SIAM Journal on Matrix Analysis and Applications, 30, 3, 1084-1127 (2008) · Zbl 1167.14038 · doi:10.1137/06066518X |
| [15] | Greub, W., Multilinear Algebra (1978), New York: Springer, New York · Zbl 0387.15001 · doi:10.1007/978-1-4613-9425-9 |
| [16] | Bro, R.; Andersson, CA, Improving the speed of multiway algorithms part II: Compression, Chemometrics and Intelligent Laboratory Systems, 42, 1-2, 105-113 (1998) · doi:10.1016/S0169-7439(98)00011-2 |
| [17] | Vannieuwenhoven, N.; Vandebril, R.; Meerbergen, K., A new truncation strategy for the higher-order singular value decomposition, SIAM Journal on Scientific Computing, 34, 2, 1027-1052 (2012) · Zbl 1247.65055 · doi:10.1137/110836067 |
| [18] | Rice, JR, A Theory of Condition, SIAM Journal on Numerical Analysis, 3, 2, 287-310 (1966) · Zbl 0143.37101 · doi:10.1137/0703023 |
| [19] | Vannieuwenhoven, N., Condition numbers for the tensor rank decomposition, Linear Algebra and its Applications, 535, 35-86 (2017) · Zbl 1375.65063 · doi:10.1016/j.laa.2017.08.014 |
| [20] | Bürgisser, P., Cucker, F.: Condition. Grundlehren der mathematischen Wissenschaften, vol. 349. Springer, Berlin, Heidelberg (2013) · Zbl 1280.65041 |
| [21] | Arslan, B.; Noferini, V.; Tisseur, F., The structured condition number of a differentiable map between matrix manifolds, with applications, SIAM Journal on Matrix Analysis and Applications, 40, 2, 774-799 (2019) · Zbl 1429.65094 · doi:10.1137/17M1148943 |
| [22] | Nocedal, J.; Wright, SJ, Numerical Optimization (2006), New York: Springer Series in Operations Research and Financial Engineering. Springer, New York · Zbl 1104.65059 |
| [23] | Absil, P-A; Mahony, R.; Sepulchre, R., Optimization Algorithms on Matrix Manifolds (2008), Princeton: Princeton University Press, Princeton · Zbl 1147.65043 · doi:10.1515/9781400830244 |
| [24] | Breiding, P.; Vannieuwenhoven, N., Convergence analysis of Riemannian Gauss-Newton methods and its connection with the geometric condition number, Applied Mathematics Letters, 78, 42-50 (2018) · Zbl 1381.65043 · doi:10.1016/j.aml.2017.10.009 |
| [25] | Bezanson, J.; Edelman, A.; Karpinski, S.; Shah, VB, Julia: A Fresh Approach to Numerical Computing, SIAM Review, 59, 1, 65-98 (2017) · Zbl 1356.68030 · doi:10.1137/141000671 |
| [26] | Orús, R., A practical introduction to tensor networks: Matrix product states and projected entangled pair states, Annals of Physics, 349, 117-158 (2014) · Zbl 1343.81003 · doi:10.1016/j.aop.2014.06.013 |
| [27] | Uschmajew, A.; Vandereycken, B., The geometry of algorithms using hierarchical tensors, Linear Algebra and Its Applications, 439, 1, 133-166 (2013) · Zbl 1281.65062 · doi:10.1016/j.laa.2013.03.016 |
| [28] | Landsberg, J.M.: Tensors: Geometry and Applications Graduate Studies in Mathematics vol. 128, (2012) · Zbl 1238.15013 |
| [29] | Lee, JM, Introduction to Smooth Manifolds (2013), New York: Springer, New York · Zbl 1258.53002 |
| [30] | Munkres, J., Topology (2014), Harlow: Pearson Education, Harlow |
| [31] | Kolda, TG, Orthogonal tensor decompositions, SIAM Journal on Matrix Analysis and Applications, 23, 1, 243-255 (2001) · Zbl 1005.15020 · doi:10.1137/S0895479800368354 |
| [32] | Navasca, C., De Lathauwer, L., Kindermann, S.: Swamp reducing technique for tensor decomposition. European Signal Processing Conference (Eusipco) (2008) |
| [33] | Sorber, L.; Van Barel, M.; De Lathauwer, L., Optimization-based algorithms for tensor decompositions: Canonical polyadic decomposition, decomposition in rank-(Lr, Lr, 1) terms, and a new generalization, SIAM Journal on Optimization, 23, 2, 695-720 (2013) · Zbl 1277.90073 · doi:10.1137/120868323 |
| [34] | De Lathauwer, L.; Nion, D., Decompositions of a Higher-Order Tensor in Block Terms-Part III: Alternating Least Squares Algorithms, SIAM Journal on Matrix Analysis and Applications, 30, 3, 1067-1083 (2008) · Zbl 1177.15033 · doi:10.1137/070690730 |
| [35] | Angelini, E.; Chiantini, L., On the identifiability of ternary forms, Linear Algebra and its Applications, 599, 36-65 (2020) · Zbl 1440.14236 · doi:10.1016/j.laa.2020.03.042 |
| [36] | Golub, GH; Van Loan, CF, Matrix Computations (2013), Baltimore: JHU press, Baltimore · Zbl 1268.65037 · doi:10.56021/9781421407944 |
| [37] | Olikier, G., Absil, P.A., De Lathauwer, L.: Variable projection applied to block term decomposition of higher-order tensors. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10891 LNCS(30468160), 139-148 (2018) |
| [38] | Phan, A.-H., Tichavský, P., Sobolev, K., Sozykin, K., Ermilov, D., Cichocki, A.: Canonical polyadic tensor decomposition with low-rank factor matrices. In: ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 4690-4694 (2021) |
| [39] | Breiding, P.; Vannieuwenhoven, N., The Condition Number of Riemannian Approximation Problems, SIAM Journal on Optimization, 31, 1, 1049-1077 (2021) · Zbl 1462.90133 · doi:10.1137/20M1323527 |
| [40] | Vervliet, N., Debals, O., De Lathauwer, L.: Tensorlab 3.0 - Numerical optimization strategies for large-scale constrained and coupled matrix/tensor factorization. Conference Record - Asilomar Conference on Signals, Systems and Computers 32, 1733-1738 (2017) |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
