×

Bilinear factorizations subject to monomial equality constraints via tensor decompositions. (English) Zbl 1472.15037

The authors consider a problem of uniqueness of a tensor decomposition, related to tensors \(\mathcal X\) of type \(I\times J\times K\). In particular, they are interested in decompositions which arise by unfolding \(\mathcal X\) to a matrix \(X\) and considering representations of type \(X=(A\odot B)S^t\), where \( A\), \(B\), \(S\) are matrices of size \(I\times R\), \(J\times R\), \(K\times R\), respectively, and \(\odot\) represents the column-wise Kronecker product. The authors consider the uniqueness of the decomposition when the entries of the matrix \(A\) are subject to monomial equality constraints, i.e., the entries must satisfy equations of type \(a_{p_1r}\cdots a_{p_Lr} = a_{s_1r}\cdots a_{s_Lr}\), and similar constraints hold on the entries of \(S\). Such monomial equality constraints arise naturally in decomposition problems related to signal processing or binary latent variable modeling. The authors extend existing methods for detecting the uniqueness of a general rank decomposition to tensor decompositions with monomial equality constraints. The block term decomposition method allows to restrict the monomial constraints to rank constraint. Thus, the authors are able to find several conditions that guarantee the uniqueness of the decomposition. The authors observe that the same methods can provide uniqueness results even for weighted decompositions of type \(X=(D*A\odot B)S^t\), where \(D\) is a matrix of weights, and \(*\) denotes the entry-wise (Hadamard) product.

MSC:

15A69 Multilinear algebra, tensor calculus
15A23 Factorization of matrices

References:

[1] Cichocki, A.; Mandic, D.; Caifa, C.; Phan, A.; Zhou, G.; De Lathauwer, L., Tensor decompositions for signal processing applications: from two-way to multiway component analysis, IEEE Signal Process. Mag., 32, 145-163 (2015)
[2] Sidiropoulos, N. D.; De Lathauwer, L.; Fu, X.; Huang, K.; Papalexakis, E. E.; Faloutsos, C., Tensor decomposition for signal processing and machine learning, IEEE Trans. Signal Process., 65, 3551-3582 (2017) · Zbl 1415.94232
[3] Harshman, R. A., Foundations of the PARAFAC procedure: models and conditions for an explanatory multimodal factor analysis, UCLA Work. Pap. Phon., 16, 1-84 (1970)
[4] Carroll, J. D.; 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
[5] Roy, R.; Kailath, T., Estimation of signal parameters via rotational invariance techniques, IEEE Trans. Acoust. Speech Signal Process., 32, 984-995 (1989)
[6] Sidiropoulos, N. D.; Bro, R.; Giannakis, G. B., Parallel factor analysis in sensor array processing, IEEE Trans. Signal Process., 48, 2377-2388 (2000)
[7] van der Veen, A.-J.; Paulraj, A., An analytical constant modulus algorithm, IEEE Trans. Signal Process., 44, 1136-1155 (1996)
[8] Shashua, A.; Hazan, T., Non-negative tensor factorization with applications to statistics and computer vision, (Proceedings of the 22nd International Conference on Machine Learning (ICML’05). Proceedings of the 22nd International Conference on Machine Learning (ICML’05), Bonn, Germany, August 07-11 (2005)), 792-799
[9] Allman, E.; Matias, C.; Rhodes, J., Identifiability of parameters in latent structure models with many observed variables, Ann. Stat., 37, 3099-3132 (2009) · Zbl 1191.62003
[10] Lim, L.-H.; Comon, P., Nonnegative approximations of nonnegative tensors, J. Chemom., 23, 432-441 (2009)
[11] Kargas, N.; Sidiropoulos, N. D.; Fu, X., Tensors, learning, and ‘Kolmogorov extension’ for finite-alphabet random vectors, IEEE Trans. Signal Process., 66, 4854-4868 (2018) · Zbl 1415.94146
[12] Sørensen, M.; De Lathauwer, L., Coupled canonical polyadic decompositions and (coupled) decompositions in multilinear rank-\(( L_{r , n}, L_{r , n}, 1)\) terms — Part I: uniqueness, SIAM J. Matrix Anal. Appl., 36, 496-522 (2015) · Zbl 1320.15010
[13] Sørensen, M.; Domanov, I.; De Lathauwer, L., Coupled canonical polyadic decompositions and (coupled) decompositions in multilinear rank-\(( L_{r , n}, L_{r , n}, 1)\) terms — Part II: algorithms, SIAM J. Matrix Anal. Appl., 36, 1015-1045 (2015) · Zbl 1321.65068
[14] Sørensen, M.; Domanov, I.; De Lathauwer, L., Coupled canonical polyadic decompositions and multiple shift-invariance in array processing, IEEE Trans. Signal Process., 66, 3665-3680 (2018) · Zbl 1415.94237
[15] Sørensen, M.; Van Eeghem, F.; De Lathauwer, L., Blind multichannel deconvolution and convolutive extensions of canonical polyadic and block term decompositions, IEEE Trans. Signal Process., 65, 4132-4145 (2017) · Zbl 1414.94582
[16] Sørensen, M.; De Lathauwer, L., Multidimensional harmonic retrieval via coupled canonical polyadic decomposition — Part I: model and identifiability, IEEE Trans. Signal Process., 65, 517-527 (2017) · Zbl 1414.94579
[17] Sørensen, M.; De Lathauwer, L., Multidimensional harmonic retrieval via coupled canonical polyadic decomposition — Part II: algorithm and multirate sampling, IEEE Trans. Signal Process., 65, 528-539 (2017) · Zbl 1414.94580
[18] van der Veen, A.-J., Analytical method for blind binary signal separation, IEEE Trans. Signal Process., 45, 1078-1082 (1997)
[19] Grellier, O.; Comon, P., Analytical blind discrete source separation, (Proc. EUSIPCO (2000))
[20] Ghahramani, Z.; Griffiths, T. L., Infinite latent feature models and the Indian buffet process, (Advances in Neural Information Processing Systems 18. Advances in Neural Information Processing Systems 18, Cambridge, MA, USA (2005))
[21] Slawski, M.; Hein, M.; Lutsik, P., Matrix factorization with binary components, (Proceedings of the 26th International Conference on Neural Information Processing Systems (NIPS’13). Proceedings of the 26th International Conference on Neural Information Processing Systems (NIPS’13), Lake Tahoe, Nevada, USA, Dec. 05-10 (2013))
[22] Jaffe, A.; Weiss, R.; Nadler, B.; Carmi, S.; Kluger, Y., Learning binary latent variable models: a tensor eigenpair approach, (Proc. of the 35th International Conference on Machine Learning. Proc. of the 35th International Conference on Machine Learning, Stockholm Sweden, July 10-15 (2018))
[23] Bader, B. W.; Harshman, R. A.; Kolda, T. G., Temporal analysis of semantic graphs using ASALSAN, (Proc. of the Seventh IEEE International Conference on Data Mining (ICDM 2007). Proc. of the Seventh IEEE International Conference on Data Mining (ICDM 2007), Omaha, Nebraska, USA, Oct. 28-31 (2007))
[24] Papalexakis, E. E.; Sidiropolous, N. D.; Bro, R., From K-means to higher-way co-clustering: multilinear decomposition with sparse latent factors, IEEE Trans. Signal Process., 61, 493-506 (2013)
[25] Bocci, C.; Chiantini, L.; Ottaviani, G., Refined methods for the identifiability of tensors, Ann. Mat. Pura Appl., 193, 1691-1702 (2014) · Zbl 1314.14102
[26] Domanov, I.; De Lathauwer, L., Generic uniqueness of a structured matrix factorization and applications in blind source separation, IEEE J. Sel. Top. Signal Process., 10, 701-711 (2016)
[27] Comon, P.; Qi, Y.; Usevich, K., Identifiability of an X-rank decomposition of polynomial maps, SIAM J. Appl. Algebra Geom., 1, 388-414 (2017) · Zbl 1373.14061
[28] Sørensen, M.; Sidiropoulos, N. D.; De Lathauwer, L., Canonical polyadic decomposition of a tensor that has missing fibers: a monomial factorization approach, (Proc. of the 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). Proc. of the 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Brighton, United Kingdom, May 12-17 (2019))
[29] De Lathauwer, L., Decomposition of a higher-order tensor in block terms — Part II: definitions and uniqueness, SIAM J. Matrix Anal. Appl., 30, 1033-1066 (2008) · Zbl 1177.15032
[30] Jiang, T.; Sidiropoulos, N. D., Kruskal’s permutation lemma and the identification of CANDECOMP/PARAFAC and bilinear model with constant modulus constraints, IEEE Trans. Signal Process., 52, 2625-2636 (2004) · Zbl 1369.94186
[31] De Lathauwer, L., A link between the canonical decomposition in multilinear algebra and simultaneous matrix diagonalization, SIAM J. Matrix Anal. Appl., 28, 642-666 (2006) · Zbl 1126.15007
[32] Domanov, I.; De Lathauwer, L., On the uniqueness of the canonical polyadic decomposition of third-order tensors — Part I: basic results and uniqueness of one factor matrix, SIAM J. Matrix Anal. Appl., 34, 855-875 (2013) · Zbl 1282.15019
[33] Domanov, I.; De Lathauwer, L., On the uniqueness of the canonical polyadic decomposition of third-order tensors — Part II: overall uniqueness, SIAM J. Matrix Anal. Appl., 34, 876-903 (2013) · Zbl 1282.15020
[34] Domanov, I.; De Lathauwer, L., Canonical polyadic decomposition of third-order tensors: reduction to generalized eigenvalue decomposition, SIAM J. Matrix Anal. Appl., 35, 636-660 (2014) · Zbl 1306.15022
[35] Kruskal, J. B., Three-way arrays: rank and uniqueness of trilinear decompositions, with applications to arithmetic complexity and statistics, Linear Algebra Appl., 18, 95-138 (1977) · Zbl 0364.15021
[36] Marcus, M.; Minc, H., On the relation between the determinant and the permanent, Ill. J. Math., 5, 376-381 (1961) · Zbl 0104.00904
[37] Minc, H., Permanents (1984), Cambridge University Press · Zbl 0166.29904
[38] Leurgans, S. E.; Ross, R. T.; Abel, R. B., A decomposition of three-way arrays, SIAM J. Matrix Anal. Appl., 14, 1064-1083 (1993) · Zbl 0788.65145
[39] Domanov, I.; De Lathauwer, L., Canonical polyadic decomposition of third-order tensors: relaxed uniqueness conditions and algebraic algorithm, Linear Algebra Appl., 513, 342-375 (2017) · Zbl 1349.15065
[40] Bapat, R. B., Mixed discriminants of positive semidefinite matrices, Linear Algebra Appl., 126, 107-124 (1989) · Zbl 0696.15007
[41] Bapat, R. B.; Raghavan, T. E.S., Nonnegative Matrices and Applications (1997), Cambridge University Press · Zbl 0879.15015
[42] Stegeman, A.; Sidiropoulos, N. D., On Kruskal’s uniqueness condition for the CANDECOMP/PARAFAC decomposition, Linear Algebra Appl., 420, 540-552 (2007) · Zbl 1120.15002
[43] Comon, P.; Golub, G.; Lim, L.-H.; Mourrain, B., Symmetric tensors and symmetric tensor rank, SIAM J. Matrix Anal. Appl., 30, 1254-1279 (2008) · Zbl 1181.15014
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.