Identifiability of Nonnegative Tucker Decompositions—Part I: Theory

[en] Abstract. Tensor decompositions have become a central tool in data science, with applications in areas such as data analysis, signal processing, and machine learning. A key property of many tensor decompositions, such as the canonical polyadic decomposition, is identifiability: the factors are unique, up to trivial scaling and permutation ambiguities. This allows one to recover the groundtruth sources that generated the data. The Tucker decomposition (TD) is a central and widely used tensor decomposition model. However, it is in general not identifiable. In this paper, we study the identifiability of the nonnegative TD (nTD). By adapting and extending identifiability results of nonnegative matrix factorization, we provide uniqueness results for nTD. Our results require the nonnegative matrix factors to have some degree of sparsity (namely, satisfy the separability condition, or the sufficiently scattered condition), while the core tensor only needs to have some slices (or linear combinations of them) or unfoldings with full column rank (but does not need to be nonnegative). Under such conditions, we derive several procedures, using either unfoldings or slices of the input tensor, to obtain identifiable nTDs by minimizing the volume of unfoldings or slices of the core tensor.

Disciplines :

Mathematics
Computer science

Author, co-author :

Saha, Subhayan ; Université de Mons - UMONS > Recherche > Service ERC Unit - Matrix Theory and Optimization

Barbarino, Giovanni ; Departamento de Ciencias Integradas, Facultad de Ciencias Experimentales, Universidad de Huelva, campus El Carmen, Huelva 21007, Spain. GB is member of the Research Group GNCS (Gruppo Nazionale per il Calcolo Scientifico) of INdAM (Istituto Nazionale di Alta Matematica).

Gillis, Nicolas ; Université de Mons - UMONS > Faculté Polytechnique > Service de Mathématique et Recherche opérationnelle

Language :

English

Title :

Identifiability of Nonnegative Tucker Decompositions—Part I: Theory

Publication date :

13 July 2026

Journal title :

SIAM Journal on Matrix Analysis and Applications

ISSN :

0895-4798

eISSN :

1095-7162

Publisher :

Society for Industrial & Applied Mathematics (SIAM)

Volume :

Issue :

Pages :

1210-1252

Peer reviewed :

Peer Reviewed verified by ORBi

Research unit :

F151 - Mathématique et Recherche opérationnelle

Research institute :

R300 - Institut de Recherche en Technologies de l'Information et Sciences de l'Informatique
R450 - Institut NUMEDIART pour les Technologies des Arts Numériques

European Projects :

HE - 101085607 - eLinoR - Beyond Low-Rank Factorizations

Funders :

European Union
European Union

Available on ORBi UMONS :

since 13 July 2026

Statistics

Number of views

18 (3 by UMONS)

Number of downloads

8 (0 by UMONS)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

M. Abdolali and N. Gillis, Simplex-structured matrix factorization: Sparsity-based identifiability and provably correct algorithms, SIAM J. Math. Data Sci., 3 (2021), pp. 593–623, https://doi.org/10.1137/20M1354982.
J. Agterberg and A. R. Zhang, Estimating higher-order mixed memberships via the ℓ₂,∞ tensor perturbation bound, J. Amer. Statist. Assoc., 120 (2024), pp. 1–11, https://doi.org/10.1080/01621459.2024.2404265.
E. M. Airoldi, D. Blei, S. Fienberg, and E. Xing, Mixed membership stochastic blockmodels, J. Mach. Learn. Res., 9 (2008), pp. 1981–2014.
A. Anandkumar, D. J. Hsu, M. Janzamin, and S. M. Kakade, When are overcomplete topic models identifiable? Uniqueness of tensor Tucker decompositions with structured sparsity, J. Mach. Learn. Res., 16 (2015), pp. 2643–2694.
S. Arora, R. Ge, Y. Halpern, D. Mimno, A. Moitra, D. Sontag, Y. Wu, and M. Zhu, A practical algorithm for topic modeling with provable guarantees, JMLR Workshop Conf. Proc., 28 (2013), pp. 280–288.
S. Arora, R. Ge, R. Kannan, and A. Moitra, Computing a nonnegative matrix factorization–provably, in ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 145–162.
B. W. Bader, T. G. Kolda, MATLAB Tensor Toolbox Version 2.6, (2015) https://github.com/andrewssobral/tensor_toolbox.
X. Bai, F. Xu, L. Zhou, Y. Xing, L. Bai, and J. Zhou, Nonlocal similarity based nonnegative Tucker decomposition for hyperspectral image denoising, IEEE J. Sel. Top. Appl. Earth Observ. Remote Sens, 11 (2018), pp. 701–712, https://doi.org/10.1109/JSTARS.2018.2791718.
G. Ballard and T. G. Kolda, Tensor Decompositions for Data Science, Cambridge University Press, Cambridge, 2025.
A. Ben-Tal and A. Nemirovski, On polyhedral approximations of the second-order cone, Math. Oper. Res., 26 (2001), pp. 193–205, https://doi.org/10.1287/moor.26.2.193.10561.
J. W. Boardman, F. A. Kruse, and R. O. Green, Mapping Target Signatures via Partial Unmixing of AVIRIS Data, NASA technical report N95-33736, 1995, pp. 23–26.
A. Cichocki, R. Zdunek, A. H. Phan, and S. I. Amari, Nonnegative Matrix and Tensor Factorizations: Applications to Exploratory Multi-way Data Analysis and Blind Source Separation, Wiley, New York, 2009.
M. D. Craig, Minimum-volume transforms for remotely sensed data, IEEE Trans. Geosci. Remote Sens., 32 (1994), pp. 542–552, https://doi.org/10.1109/36.297973.
C. Ding, T. Li, W. Peng, and H. Park, Orthogonal nonnegative matrix t-factorizations for clustering, in ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York, 2006, pp. 126–135.
I. Domanov and L. De Lathauwer, Canonical polyadic decomposition of third-order tensors: Relaxed uniqueness conditions and algebraic algorithm, Linear Algebra Appl., 513 (2017), pp. 342–375, https://doi.org/10.1016/j.laa.2016.10.019.
D. Donoho and V. Stodden, When does non-negative matrix factorization give a correct decomposition into parts?, in Advances in Neural Information Processing Systems, Curran Associaters, Red Hook, NY, 16 2004, pp. 1141–1148.
X. Fu, K. Huang, and N. D. Sidiropoulos, On identifiability of nonnegative matrix factorization, IEEE Signal Process. Lett., 25 (2018), pp. 328–332, https://doi.org/10.1109/LSP.2018.2789405.
X. Fu, K. Huang, N. D. Sidiropoulos, and W. K. Ma, Nonnegative matrix factorization for signal and data analytics: Identifiability, algorithms, and applications, IEEE Signal Process. Mag., 36 (2019), pp. 59–80, https://doi.org/10.1109/MSP.2018.2877582.
X. Fu, K. Huang, N. D. Sidiropoulos, Q. Shi, and M. Hong, Anchor-free correlated topic modeling, IEEE Trans. Pattern Anal. Mach. Intell., 41 (2019), pp. 1056–1071, https://doi.org/10.1109/TPAMI.2018.2827377.
X. Fu, K. Huang, B. Yang, W. K. Ma, and N. D. Sidiropoulos, Robust volume minimization-based matrix factorization for remote sensing and document clustering, IEEE Trans. Signal Process., 64 (2016), pp. 6254–6268, https://doi.org/10.1109/TSP.2016.2602800.
X. Fu, W. K. Ma, K. Huang, and N. D. Sidiropoulos, Blind separation of quasi-stationary sources: Exploiting convex geometry in covariance domain, IEEE Trans. Signal Process., 63 (2015), pp. 2306–2320, https://doi.org/10.1109/TSP.2015.2404577.
X. Fu, N. Vervliet, L. De Lathauwer, K. Huang, and N. Gillis, Computing large-scale matrix and tensor decomposition with structured factors: A unified nonconvex optimization perspective, IEEE Signal Process. Mag., 37 (2020), pp. 78–94, https://doi.org/10.1109/MSP.2020.3003544.
N. Gillis, Nonnegative Matrix Factorization, SIAM, Philadelphia, 2020.
N. Gillis and R. Luce, Checking the sufficiently scattered condition using a global non-convex optimization software, IEEE Signal Process. Lett., 31 (2024), pp. 1610–1614, https://doi.org/10.1109/LSP.2024.3411521.
S. Hassanzadeh and A. Karami, Compression and noise reduction of hyperspectral images using non-negative tensor decomposition and compressed sensing, Eur. J. Remote Sens., 49 (2016), pp. 587–598, https://doi.org/10.5721/EuJRS20164931.
K. Huang, X. Fu, and N. D. Sidiropoulos, Anchor-free correlated topic modeling: Identifiability and algorithm, Adv. Neural Inform. Process. Syst., 29 (2016), pp. 1794–1802.
K. Huang, N. D. Sidiropoulos, and A. P. Llavas, A flexible and efficient algorithmic framework for constrained matrix and tensor factorization, IEEE Trans. Signal Process., 64 (2016), pp. 5052–5065, https://doi.org/10.1109/TSP.2016.2576427.
K. Huang, N. D. Sidiropoulos, and A. Swami, Non-negative matrix factorization revisited: Uniqueness and algorithm for symmetric decomposition, IEEE Trans. Signal Process., 62 (2013), pp. 211–224, https://doi.org/10.1109/TSP.2013.2285514.
P. Koiran, An efficient uniqueness theorem for overcomplete tensor decomposition, in ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2025, pp. 1909–1932.
P. Koiran and S. Saha, Absolute reconstruction for sums of powers of linear forms: Degree 3 and beyond, Comput. Complex., 32 (2023), 8, https://doi.org/10.1007/s00037-023-00239-8.
P. Koiran and S. Saha, Undercomplete Decomposition of Symmetric Tensors in Linear Time, and Smoothed Analysis of the Condition Number, preprint, 2403.00643, 2024.
P. Koiran and S. Saha, Complete decomposition of symmetric tensors in linear time and polylogarithmic precision, Theoret. Comput. Sci., 1037 (2025), 115159, https://doi.org/10.1016/j.tcs.2025.115159.
T. G. Kolda and B. W. Bader, Tensor decompositions and applications, SIAM Rev, 51 (2009), pp. 455–500, https://doi.org/10.1137/07070111X.
C. Kolomvakis, A. Vandaele, and N. Gillis, Boolean matrix tri-factorization, in IEEE International Conference on Acoustics, Speech and Signal Processing, IEEE, Piscataway, NJ, 2025, pp. 1–5.
J. Kossaifi, Y. Panagakis, A. Anandkumar, and M. Pantic, Tensorly: Tensor learning in python, J. Mach. Learn. Res., 20 (2019), pp. 1–6, http://jmlr.org/papers/v20/18-277.html.
P. K. Kothari, A. Moitra, and A. S. Wein, Overcomplete tensor decomposition via Koszul-Young flattenings, in IEEE Symposium on Foundations of Computer Science, IEEE, Piscataway, NJ, 2025, pp. 1874–1885.
J. B. Kruskal, Three-way arrays: Rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics, Linear Algebra Appl., 18 (1977), pp. 95–138, https://doi.org/10.1016/0024-3795(77)90069-6.
V. Leplat, N. Gillis, and A. M. Ang, Blind audio source separation with minimum-volume beta-divergence NMF, IEEE Trans. Signal Process., 68 (2020), pp. 3400–3410, https://doi.org/10.1109/TSP.2020.2991801.
C. H. Lin, W. K. Ma, W. C. Li, C. Y. Chi, and A. Ambikapathi, Identifiability of the simplex volume minimization criterion for blind hyperspectral unmixing: The no-pure-pixel case, IEEE Trans. Geosci. Remote Sens., 53 (2015), pp. 5530–5546, https://doi.org/10.1109/TGRS.2015.2424719.
Q. Liu, L. Lu, and Z. Chen, Non-negative Tucker decomposition with graph regularization and smooth constraint for clustering, Pattern Recognit., 148 (2024), 110207, https://doi.org/10.1016/j.patcog.2023.110207.
A. Marmoret, J. E. Cohen, N. Bertin, and F. Bimbot, Uncovering Audio Patterns in Music with Nonnegative Tucker Decomposition for Structural Segmentation, in Proceedings of the 21st International Society for Music Information Retrieval Conference (ISMIR), 2020, pp. 788–794.
Z. Roštáková, R. Rosipal, S. Seifpour, and L. J. Trejo, A comparison of non-negative Tucker decomposition and parallel factor analysis for identification and measurement of human EEG rhythms, Meas. Sci. Rev., 20 (2020), pp. 126–138, https://doi.org/10.2478/msr-2020-0015.
S. Saha, Algebraic and Numerical Algorithms for Symmetric Tensor Decompositions, Thesis, Ecole Normale Supérieure de Lyon Lyon, France, 2023.
S. Saha, G. Barbarino, and N. Gillis, Identifiability of Nonnegative Tucker Decompositions —Part II: Algorithms and Applications, in preparation.
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, https://doi.org/10.1109/TSP.2017.2690524.
J. B. Smith, Y. Kawasaki, and M. Goto, Unmixer: An interface for extracting and remixing loops, in International Society for Music Information Retrieval (ISMIR), ISMIR, 2020. pp. 824–831.
Y. Sun and K. Huang, Volume-regularized nonnegative Tucker decomposition with identifiability guarantees, in IEEE International Conference on Acoustics, Speech and Signal Processing, Piscataway, NJ, 2023.
C. F. Van Loan and N. Pitsianis, Approximation with Kronecker Products, Springer, Dordrecht, Netherlands, 1993, pp. 293–314.
N. Vervliet, O. Debals, L. Sorber, M. Van Barel, 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, Pacific Grove, CA, USA, 2016, pp. 1733–1738, https://doi.org/10.1109/ACSSC.2016.7869679.
O. Vu Thanh, Low-rank Matrix Factorizations with Volume-based Constraints and Regularizations, Ph.D. thesis, University of Mons, Mons, Belgium, 2024.
H. Wang, F. Nie, H. Huang, and F. Makedon, Fast nonnegative matrix tri-factorization for large-scale data co-clustering, in International Joint Conference on Artificial Intelligence, https://www.ijcai.org/Proceedings/11/Papers/261.pdf (2011).
M. Wang and Y. Zeng, Multiway clustering via tensor block models, Adv. Neural Inform. Process. Syst., 32 (2019), pp. 715–725.
W. Yin, Y. Qu, Z. Ma, and Q. Liu, HyperNTF: A hypergraph regularized nonnegative tensor factorization for dimensionality reduction, Neurocomputing, 512 (2022), pp. 190–202.
M. Zare, M. S. Helfroush, K. Kazemi, and P. Scheunders, Hyperspectral and multispectral image fusion using coupled non-negative Tucker tensor decomposition, Remote Sens., 13 (2021), 2930, https://doi.org/10.3390/rs13152930.
Y. Zhang and D. Y. Yeung, Overlapping community detection via bounded nonnegative matrix tri-factorization, in ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York, 2012, pp. 606–614.
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, https://doi.org/10.1109/TIP.2015.2478396.