Nonnegative non-redundant tensor decomposition

Abstract

Nonnegative tensor decomposition allows us to analyze data in their ‘native’ form and to present results in the form of the sum of rank-1 tensors that does not nullify any parts of the factors. In this paper, we propose the geometrical structure of a basis vector frame for sum-of-rank-1 type decomposition of real-valued nonnegative tensors. The decomposition we propose reinterprets the orthogonality property of the singularvectors of matrices as a geometric constraint on the rank-1 matrix bases which leads to a geometrically constrained singularvector frame. Relaxing the orthogonality requirement, we developed a set of structured-bases that can be utilized to decompose any tensor into a similar constrained sum-of-rank-1 decomposition. The proposed approach is essentially a reparametrization and gives us an upper bound of the rank for tensors. At first, we describe the general case of tensor decomposition and then extend it to its nonnegative form. At the end of this paper, we show numerical results which conform to the proposed tensor model and utilize it for nonnegative data decomposition.

Keywords

matrix / tensor / rank-1 decomposition / basis vector frame

References

[1] Bronshtein I. N., Semendyayev K. A., Musiol G., Muehling H.. Handbook of Mathematics, 2007 4th ed. Berlin: Springer-Verlag

[2] Carroll J., Chang J. -J.. Analysis of individual differences in multidimensional scaling via an n-way generalization of Eckart-Younga decomposition. Psychometrika, 1970, 35(3): 283-319

[3] Cichocki A., Zdunek R., Phan A. H., Amari S.. Nonnegative Matrix and Tensor Factorizations: Applications to Exploratory Multi-way Data Analysis and Blind Source Separation, 2009, Hoboken: John Wiley & Sons, Ltd

[4] Comon P., Golub G., Lim L. -H., Mourrain B.. Symmetric tensors and symmetric tensor rank. SIAM J Matrix Anal Appl, 2008, 30: 1254-1279

[5] Comon P., Mourrain B.. Decomposition of quantics in sums of powers of linear forms. Signal Processing, 1996, 53: 93-107

[6] Edelman A., Murakami H.. Polynomial roots from companion matrix eigenvalues. Math Comp, 1995, 64: 763-776

[7] Goldstine H. H., Murray F. J., von Neumann J.. The Jacobi method for real symmetric matrices. J ACM, 1959, 6(1): 59-96

[8] Golub G. H., Van Loan C. F.. Matrix Computations, 1996 3rd ed. Baltimore: Johns Hopkins University Press

[9] Harshman R. A.. Foundations of the PARAFAC procedure: Models and conditions for an explanatory multi-modal factor analysis. UCLAWorking Papers in Phonetics, 1970, 16(1): 84

[10] Kolda T. G., Bader B. W.. Tensor decompositions and applications. SIAM Review, 2009, 51(3): 455-500

[11] Kyrgyzov O, Erdogmus D. Geometric structure of sum-of-rank-1 decompositions for n-dimensional order-p symmetric tensors. In: ISCAS, Seattle, WA, USA, 2008. 2008, 1340–1343

[12] Kyrgyzov O. Non-redundant tensor decomposition. https://sites.google.com/site/kyrgyzov/tensor

[13] Kyrgyzov O, Erdogmus D. Non-redundant tensor decomposition. NIPS, Tensor Workshop, 2010

[14] Lathauwer L. D., Moor B. D., Vandewalle J.. A multilinear singular value decomposition. SIAM J Matrix Anal Appl, 2000, 21(4): 1253-1278

[15] Lathauwer L. D., Moor B. D., Vandewalle J.. On the best rank-1 and rank-(R₁,R₂, …, R_N) approximation of higher-order tensors. SIAM J Matrix Anal Appl, 2000, 21(4): 1324-1342

[16] Lovisolo L., da Silva E.. Uniform distribution of points on a hyper-sphere with applications to vector bit-plane encoding. IEE Proceedings: Vision, Image and Signal Processing, 2001, 148(3): 187-193

[17] Minati L., Aquino D.. Trappl R.. Probing neural connectivity through diffusion tensor imaging DTI. Cybernetics and Systems, 2006, Vienna: ASCS 263 268

[18] Steinhaus H.. Mathematical Snapshots, 1999 3ed ed. New York: Dover Publications

[19] Tucker L.. Some mathematical notes on three-mode factor analysis. Psychometrika, 1966, 31(3): 279-311