×

Generic and typical ranks of multi-way arrays. (English) Zbl 1168.15309

Summary: The concept of tensor rank was introduced in the 1920s. In the 1970s, when methods of component analysis on arrays with more than two indices became popular, tensor rank became a much studied topic. The generic rank may be seen as an upper bound to the number of factors that are needed to construct a random tensor. We explain in this paper how to obtain numerically in the complex field the generic rank of tensors of arbitrary dimensions, based on Terracini’s lemma [A. Terracini, Torino Atti 51, 643–653 (1916; JFM 46.0154.01)], and compare it with the algebraic results already known in the real or complex fields. In particular, we examine the cases of symmetric tensors, tensors with symmetric matrix slices, complex tensors enjoying Hermitian symmetries, or merely tensors with free entries.

MSC:

15A69 Multilinear algebra, tensor calculus
15A03 Vector spaces, linear dependence, rank, lineability
15A72 Vector and tensor algebra, theory of invariants
15B57 Hermitian, skew-Hermitian, and related matrices
46M05 Tensor products in functional analysis

Citations:

JFM 46.0154.01

Software:

PARAFAC
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Howell, T. D., Global properties of tensor rank, Linear Algebra Appl., 22, 9-23 (1978) · Zbl 0389.15009
[2] Strassen, V., Rank and optimal computation of generic tensors, Linear Algebra Appl., 52, 645-685 (1983) · Zbl 0514.15018
[3] Alexander, J.; Hirschowitz, A., Polynomial interpolation in several variables, J. Algebraic Geom., 4, 2, 201-222 (1995) · Zbl 0829.14002
[4] Comon, P.; Mourrain, B., Decomposition of quantics in sums of powers of linear forms, Signal Process., 53, 2, 93-107 (1996), (Special issue on High-Order Statistics) · Zbl 0875.94079
[5] Comon, P.; Golub, G.; Lim, L.-H.; Mourrain, B., Symmetric tensors and symmetric tensor rank, SIAM J. Matrix Anal. Appl., 30, 3, 1254-1279 (2008) · Zbl 1181.15014
[6] BÜrgisser, P.; Clausen, M.; Shokrollahi, M. A., Algebraic Complexity Theory (1997), Springer: Springer Berlin · Zbl 1087.68568
[7] Carroll, J. D.; Chang, J. J., Analysis of individual differences in multidimensional scaling via \(n\)-way generalization of Eckart-Young decomposition, Psychometrika, 35, 3, 283-319 (1970) · Zbl 0202.19101
[8] R.A. Harshman, Foundations of the Parafac procedure: models and conditions for an explanatory multimodal factor analysis, UCLA Working Papers in Phonetics, vol. 16, 1970, pp. 1-84. <http://publish.uwo.ca/ harshman>.; R.A. Harshman, Foundations of the Parafac procedure: models and conditions for an explanatory multimodal factor analysis, UCLA Working Papers in Phonetics, vol. 16, 1970, pp. 1-84. <http://publish.uwo.ca/ harshman>.
[9] Hitchcock, F. L., Multiple invariants and generalized rank of a \(p\)-way matrix or tensor, J. Math. Phys., 7, 1, 39-79 (1927) · JFM 53.0097.01
[10] Smilde, A.; Bro, R.; Geladi, P., Multi-Way Analysis (2004), Wiley
[11] De Lathauwer, L.; De Moor, B.; Vandewalle, J., A multilinear singular value decomposition, SIAM J. Matrix Anal. Appl., 21, 1253-1278 (2000) · Zbl 0962.15005
[12] L.R. Tucker, The extension of factor analysis to three-dimensional matrices, in: H. Gulliksen, N. Frederiksen (Eds.), Contributions to Mathematical Psychology, Holt, Rinehart & Winston, NY, 1964, pp. 109-127.; L.R. Tucker, The extension of factor analysis to three-dimensional matrices, in: H. Gulliksen, N. Frederiksen (Eds.), Contributions to Mathematical Psychology, Holt, Rinehart & Winston, NY, 1964, pp. 109-127.
[13] Tucker, L. R., Some mathematical notes for three-mode factor analysis, Psychometrika, 31, 279-311 (1966)
[14] ten Berge, J. M.F.; Smilde, A. K., Non-triviality and identification of a constrained tucker 3 analysis, J. Chemometrics, 16, 609-612 (2002)
[15] Gurden, S. P.; Westerhuis, J. A.; Bijlsma, S.; Smilde, A., Modeling of spectroscopic batch process data using grey models to incorporate external information, J. Chemometrics, 15, 101-121 (2001)
[16] De Lathauwer, L.; Castaing, J., Blind identification of underdetermined mixtures by simultaneous matrix diagonalization, IEEE Trans. Signal Process., 56, 3, 1096-1105 (2008) · Zbl 1390.94146
[17] P. Comon, Tensor decompositions, in: J.G. McWhirter, I.K. Proudler (Eds.), Mathematics in Signal Processing V, Clarendon Press, Oxford, UK, 2002, pp. 1-24.; P. Comon, Tensor decompositions, in: J.G. McWhirter, I.K. Proudler (Eds.), Mathematics in Signal Processing V, Clarendon Press, Oxford, UK, 2002, pp. 1-24. · Zbl 1014.65007
[18] Sidiropoulos, N. D.; Giannakis, G. B.; Bro, R., Blind parafac receivers for ds-cdma systems, IEEE Trans. Signal Process., 48, 3, 810-823 (2000)
[19] Sidiropoulos, N. D.; Bro, R.; Giannakis, G. B., Parallel factor analysis in sensor array processing, IEEE Trans. Signal Process., 48, 8, 2377-2388 (2000)
[20] Sidiropoulos, N. D.; Budampati, R., Khatri-rao space-time codes, IEEE Trans. Signal Process., 50, 10, 2396-2407 (2002) · Zbl 1369.94449
[21] P. Comon, Supervised classification, a probabilistic approach, in: Verleysen (Ed.), ESANN-European Symposium on Artificial Neural Networks, Brussels, April 19-21, 1995, D facto Publ. invited paper, pp. 111-128.; P. Comon, Supervised classification, a probabilistic approach, in: Verleysen (Ed.), ESANN-European Symposium on Artificial Neural Networks, Brussels, April 19-21, 1995, D facto Publ. invited paper, pp. 111-128.
[22] Beylkin, G.; Mohlenkamp, M. J., Algorithms for numerical analysis in high dimensions, SIAM J. Sci. Comput., 26, 2133-2159 (2005) · Zbl 1085.65045
[23] Hackbush, W.; Khoromskij, B. N., Tensor-product approximation to operators and functions in high dimension, J. Complexity, 23, 697-714 (2007) · Zbl 1141.65032
[24] J.B. Kruskal, Rank, decomposition, and uniqueness for 3-way and \(n\)-way arrays, in: R. Coppi, S. Bolasco (Eds.), Multiway Data Analysis, Elsevier Science, North-Holland, 1989, pp. 7-18.; J.B. Kruskal, Rank, decomposition, and uniqueness for 3-way and \(n\)-way arrays, in: R. Coppi, S. Bolasco (Eds.), Multiway Data Analysis, Elsevier Science, North-Holland, 1989, pp. 7-18.
[25] ten Berge, J. M.F.; Kiers, H. A.L., Simplicity of core arrays in three-way principal component analysis and the typical rank of \(p \times q \times 2\) arrays, Linear Algebra Appl., 294, 169-179 (1999) · Zbl 0931.62050
[26] H. Abo, G. Ottaviani, C. Peterson, Induction for secant varieties of Segre varieties, August 2006. arXiv:math/0607191.; H. Abo, G. Ottaviani, C. Peterson, Induction for secant varieties of Segre varieties, August 2006. arXiv:math/0607191. · Zbl 1170.14036
[27] J.B. Kruskal, Statement of some current results about three-way arrays, 1983, Unpublished manuscript, AT&T Bell Labs, Murray Hill, NC. Pdf available from: <http://three-mode.leidenuniv.nl>.; J.B. Kruskal, Statement of some current results about three-way arrays, 1983, Unpublished manuscript, AT&T Bell Labs, Murray Hill, NC. Pdf available from: <http://three-mode.leidenuniv.nl>.
[28] A. Franc, Etudes algébriques des multitableaux: Apports de l’algèbre tensiorielle. Doctorate, Université de Montpellier, 1992.; A. Franc, Etudes algébriques des multitableaux: Apports de l’algèbre tensiorielle. Doctorate, Université de Montpellier, 1992.
[29] ten Berge, J. M.F., The typical rank of tall three-way arrays, Psychometrika, 65, 525-532 (2000) · Zbl 1291.62255
[30] Atkinson, M. D.; Lloyd, S., Bounds on the ranks of some 3-tensors, Linear Algebra Appl., 31, 19-31 (1980) · Zbl 0432.15018
[31] ten Berge, J. M.F., Partial uniqueness in CANDECOMP/PARAFAC, J. Chemometrics, 18, 12-16 (2004)
[32] ten Berge, J. M.F.; Stegeman, A.; arrays, Symmetry transformations for square sliced three way, with applications to their typical rank, Linear Algebra Appl., 418, 215-224 (2006)
[33] ten Berge, J. M.F.; Sidiropoulos, N. D.; Rocci, R., Typical rank and INDSCAL dimensionality for symmetric three-way arrays of order \(i \times 2 \times 2\) or \(i \times 3 \times 3\), Linear Algebra Appl., 388, 363-377 (2004) · Zbl 1057.15002
[34] J.M.F. ten Berge, A. Stegeman, M. Bennani-Dosse, The Carroll & Chang conjecture of equal INDSCAL components when Candecomp/Parafac gives perfect fit, Linear Algebra Appl. in press.; J.M.F. ten Berge, A. Stegeman, M. Bennani-Dosse, The Carroll & Chang conjecture of equal INDSCAL components when Candecomp/Parafac gives perfect fit, Linear Algebra Appl. in press. · Zbl 1185.65073
[35] R.A. Harshman, M.E. Lundy, Data preprocessing and the extended Parafac model, in: J.A. Hattie, H.G. Law, C.W. Snyder, R.P. McDonald (Eds.), Research Methods for Multimode Data Analysis, Praeger, New York, 1984, pp. 216-284.; R.A. Harshman, M.E. Lundy, Data preprocessing and the extended Parafac model, in: J.A. Hattie, H.G. Law, C.W. Snyder, R.P. McDonald (Eds.), Research Methods for Multimode Data Analysis, Praeger, New York, 1984, pp. 216-284.
[36] A. Terracini, Sulla rappresentazione delle forme quaternarie mediante somme di poten ze di forme lineari, Atti della R. Acc. delle Scienze di Torino, 51, 1916.; A. Terracini, Sulla rappresentazione delle forme quaternarie mediante somme di poten ze di forme lineari, Atti della R. Acc. delle Scienze di Torino, 51, 1916.
[37] Lasker, E., Kanonische Formen, Math. Ann., 58, 434-440 (1904) · JFM 35.0122.01
[38] Wakeford, E. K., Apolarity and canonical forms, Proc. London Math. Soc., 18, 32, 403-410 (1918) · JFM 47.0880.01
[39] P. Comon, J.M.F. ten Berge, Generic and typical ranks of three-way arrays, Research Report ISRN I3S/RR-2006-29-FR, I3S, Sophia-Antipolis, France, September 4, 2006.; P. Comon, J.M.F. ten Berge, Generic and typical ranks of three-way arrays, Research Report ISRN I3S/RR-2006-29-FR, I3S, Sophia-Antipolis, France, September 4, 2006. · Zbl 1168.15309
[40] J. Castaing, Méthodes PARAFAC pour la Séparation de Signaux, Ph.D. Thesis, Université de Cergy-Pontoise, 2006.; J. Castaing, Méthodes PARAFAC pour la Séparation de Signaux, Ph.D. Thesis, Université de Cergy-Pontoise, 2006.
[41] Albera, L.; Ferreol, A.; Comon, P.; Chevalier, P., Blind identification of overcomplete mixtures of sources (BIOME), Linear Algebra Appl., 391, 1-30 (2004) · Zbl 1060.94503
[42] De Lathauwer, L., A link between canonical decomposition in multilinear algebra and simultaneous matrix diagonalization, SIAM J. Matrix Anal., 28, 3, 642-666 (2006) · Zbl 1126.15007
[43] Lickteig, T., Typical tensorial rank, Linear Algebra Appl., 69, 95-120 (1985) · Zbl 0575.15013
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.