cnrs   Université de Toulouse

Table of contents for this issue | Previous article | Next article
Edinah K. Gnang; Ahmed Elgammal; Vladimir Retakh
A Spectral Theory for Tensors
Annales de la faculté des sciences de Toulouse Sér. 6, 20 no. 4 (2011), p. 801-841, doi: 10.5802/afst.1325
Article PDF | Reviews MR 2918215 | Zbl 1238.15004

Résumé - Abstract

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 268178 |  Zbl 0212.06401
[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 0202.19101
[5] Dustin Cartwright and Bernd Sturmfels.— The number of eigenvalues of a tensor. Preprint arXiv:1004.4953. (2010).  MR 2643580
[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 2286236 |  Zbl 1037.00003
[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 1264417 |  Zbl 0827.14036
[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 519843 |  Zbl 0381.68045
[12] D. Grigoriev.— Multiplicative complexity of a bilinear form over a commutative ring. Lecture Notes Computer Science vol 118, p. 281-286 (1981).  MR 652760 |  Zbl 0467.68044
[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 1770876 |  Zbl 1040.68045
[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 1079455 |  Zbl 0716.65043
[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 2535056 |  Zbl 1173.65029
[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 1780272 |  Zbl 0962.15005
[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 1780276 |  Zbl 0958.15026
[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 2290010 |  Zbl 1118.13001
[28] Liqun Qi.— Eigenvalues of a real supersymmetric tensor. Journal of Symbolic Computation, 40, p. 1302-1324 (2005).  MR 2178089 |  Zbl 1125.15014
[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 2271327 |  Zbl 1121.14050
[30] Liqun Qi.— Eigenvalues and invariants of tensors. Journal of Mathematical Analysis and Applications, 325, p. 1363-1377 (2007).  MR 2270090 |  Zbl 1113.15020
[31] Ran Raz.— Tensor-rank and lower bounds for arithmetic formulas. Proceeding of the 42nd STOC (2010).  MR 2743315
[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 205395
[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 1034.68693
[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 1126.34325
Search for an article
Search within the site