A Spectral Theory for Tensors

Gnang, Edinah K.; Elgammal, Ahmed; Retakh, Vladimir

Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Tome 20 (2011) no. 4, pp. 801-841.

Nous proposons dans cet article une théorie générale de l’analyse spectrale des tenseurs. L’approche que nous proposons se fonde sur une factorisation des tenseurs à l’aide de tenseurs orthogonaux et de tenseurs diagonaux. Cette décomposition a l’avantage de fournir pour un tenseur donné une représentation comme somme de produits tensoriels de tenseurs d’ordres inférieurs à celui du tenseur consideré. La factorisation spectrale que nous proposons est fondée sur l’algèbre multilinéaire et exprime de façon explicite la relation entre les tenseurs propres et les polynômes caractéristiques généralisés. Cette théorie permet en outre de généraliser des notions d’algèbre linéaire telles que celle de matrices hermitiennes et en particulier celle de matrices orthogonales. Enfin la factorisation spectrale des tenseurs induit une analyse récursive qui détermine une hiérarchie spectrale associée aux tenseurs.

In this paper we propose a general spectral theory for tensors. Our proposed factorization decomposes a tensor into a product of orthogonal and scaling tensors. At the same time, our factorization yields an expansion of a tensor as a summation of outer products of lower order tensors. Our proposed factorization shows the relationship between the eigen-objects and the generalised characteristic polynomials. Our framework is based on a consistent multilinear algebra which explains how to generalise the notion of matrix hermicity, matrix transpose, and most importantly the notion of orthogonality. Our proposed factorization for a tensor in terms of lower order tensors can be recursively applied so as to naturally induces a spectral hierarchy for tensors.

[1] Cayley Arthur.— On the theory of linear transformations. Cambridge Math., J(4), p. 1-16 (1845).

[2] P. Bhattacharya.— A new three-dimensional transform using a ternary product. IEEE Trans. Signal Processing, 43(12), p. 3081-3084 (1995).

[3] Bruno Buchberger.— An algorithmic criterion for the solvability of a system of algebraic equations. Aequationes Mathematicae 4, p. 374-383 (1970). | MR | Zbl

[4] J. Carroll and J. Chang.— Analysis of individual differences in multidimensional scaling via an n-way generalization of eckart-young decomposition. Psychometrika, 35, p. 283-319 (1970). | Zbl

[5] Dustin Cartwright and Bernd Sturmfels.— The number of eigenvalues of a tensor. Preprint arXiv:1004.4953. (2010). | MR

[6] Lek-Heng Lim and Christopher Hillar.— Most tensor problems are np hard. Preprint arXiv:0911.1393v2 (2009).

[7] L. de Lathauwer, B. de Moor, and J. Vandewalle.— Independent component analysis and (simultaneous) third-order tensor diagonalization. IEEE Transactions on Signal Processing, 49, p. 2262-2271 (2001).

[8] David S. Dummit and Richard M. Foote.— Abstract Algebra. John Wiley & Sons, New York, New York (2003). | MR | Zbl

[9] A. Elgammal and C.-S. Lee.— Separating style and content on a nonlinear manifold. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), volume 1, p. 478-485 (2004).

[10] I. M. Gelfand, M. M. Kapranov and A. V. Zelevinsky.— Discriminants, Resultants and Multidimensional Determinants. Birkhauser (1994). | MR | Zbl

[11] D. Grigoriev.— Mutiplicative complexity of a pair of bilinear forms and of the polynomial multiplication. Lecture Notes Computer Science vol 64, p. 250-256 (1978). | MR | Zbl

[12] D. Grigoriev.— Multiplicative complexity of a bilinear form over a commutative ring. Lecture Notes Computer Science vol 118, p. 281-286 (1981). | MR | Zbl

[13] D. Grigoriev and A. Razborov.— Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields. Appl. Algebra Engrg. Comm. Comput. #6, p. 465-487 (2000). | MR | Zbl

[14] R. A. Harshman.— Foundations of the parafac procedure: Models and conditions for an explanatory multi-modal factor analysis. UCLA working papers in phonetics (1970).

[15] Johan Hastad.— Tensor rank is np-complete. J. Algorithms, 11(4), p. 644-654 (1990). | MR | Zbl

[16] M.E. Kilmer, C.D. Martin, and L. Perrone.— A third-order generalization of the matrix svd as a product of third-order tensors. Technical Report Technical Report Number TR-2008-4, Tufts University Department of Computer Science, Medford, MA, October 2008.

[17] M.E. Kilmer and C.D. Moravitz Martin.— Decomposing a tensor. SIAM News, 37(9), 2004.

[18] Tamara G. Kolda and Brett W. Bader.— Tensor decompositions and applications. SIAM Review, 51(3), September 2009. In press. | MR | Zbl

[19] Tamara G. Kolda, Brett W. Bader, and Joseph P. Kenny.— Higher-order web link analysis using multilinear algebra. In ICDM ’05: Proceedings of the Fifth IEEE International Conference on Data Mining, p. 242-249, Washington, DC, USA (2005). IEEE Computer Society.

[20] Tamara G. Kolda and Jimeng Sun.— Scalable tensor decompositions for multi-aspect data mining. In ICDM 2008: Proceedings of the 8th IEEE International Conference on Data Mining, p. 363-372, December 2008.

[21] Lieven De Lathauwer, Bart de Moor, and Joos Vandewalle.— A multilinear singular value decomposiiton. SIAM Journal On Matrix Analysis and Applications, 21(4), p. 1253-1278 (2000). | MR | Zbl

[22] Lieven De Lathauwer, Bart de Moor, and Joos Vandewalle.— On the best rank-1 and rank-(r1, r2, ..., rn) approximation of higher-order tensors. SIAM Journal On Matrix Analysis and Applications, 21(4), p. 1324-1342 (2000). | MR | Zbl

[23] Chan-Su Lee and Ahmed Elgammal.— Facial expression analysis using nonlinear decomposable generative models. In Proceedings of IEEE Workshop on on Analysis and Modeling of Faces and Gestures (AMFG), p. 17-31 (2005).

[24] Chan-Su Lee and Ahmed Elgammal.— Modeling view and posture manifolds for tracking. In Proceedings of International Conference on Computer Vision (ICCV) (2007).

[25] Chan-Su Lee and Ahmed M. Elgammal.— Towards scalable view-invariant gait recognition: Multilinear analysis for gait. In Proceedings of IEEE Conference on Audio, Video Biometric People Authentication (AVBPA), p. 395-405 (2005).

[26] Lek-Heng Lim.— Singular values and eigenvalues of tensors: a variational approach. Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP05(1), p. 129-132 (2005).

[27] David A. Cox, John B. Little Don O’Shea.— Ideals, Varieties, and Algorithms Third Edition, 2007. Springer (2007). | MR | Zbl

[28] Liqun Qi.— Eigenvalues of a real supersymmetric tensor. Journal of Symbolic Computation, 40, p. 1302-1324 (2005). | MR | Zbl

[29] Liqun Qi.— Rank and eigenvalues of a supersymmetric tensor, the multivariate homogeneous polynomial and the algebraic hypersurface it defines. Journal of Symbolic Computation, 41(12), p. 1309-1327 (2006). | MR | Zbl

[30] Liqun Qi.— Eigenvalues and invariants of tensors. Journal of Mathematical Analysis and Applications, 325, p. 1363-1377 (2007). | MR | Zbl

[31] Ran Raz.— Tensor-rank and lower bounds for arithmetic formulas. Proceeding of the 42nd STOC (2010). | MR | Zbl

[32] Amnon Shashua and Tamir Hazan.— Non-negative tensor factorization with applications to statistics and computer vision. In ICML ’05: Proceedings of the 22nd international conference on Machine learning, p. 792-799, New York, NY, USA, (2005) ACM.

[33] Jian tao Sun, Hua-Jun Zeng, Huan Liu, and Yuchang Lu.— Cubesvd: A novel approach to personalized web search. In In Proc. of the 14 th International World Wide Web Conference (WWW, p. 382-390. Press (2005).

[34] L.R. Tucker.— Some mathematical notes on three-mode factor analysis. Psychometrika, 31, p. 279-311 (1966). | MR

[35] M. A. O. Vasilescu.— An algorithm for extracting human motion signatures. In Proc. of IEEE CVPR, Hawai (2001).

[36] M. A. O. Vasilescu.— Human motion signatures for character animation. In In ACM SIGGRAPH 2001, Los Angeles (2001).

[37] M. A. O. Vasilescu and D. Terzopoulos.— Multilinear analysis of image ensebles: Tensorfaces. In Proc. of ECCV, Copenhagen, Danmark, p. 447-460 (2002). | Zbl

[38] M. Alex, O. Vasilescu and Demetri Terzopoulos.— Multilinear subspace analysis of image ensembles (2003).

[39] H.C. Wang and N. Ahuja.— Rank-r approximation of tensors: Using image-as-matrix representation. II: p. 346-353 (2005). | Zbl