A Spectral Theory for Tensors

Edinah K. Gnang[1]; Ahmed Elgammal[1]; Vladimir Retakh[2]

  • [1] Department of Computer Science, Rutgers University, Piscataway, NJ 08854-8019 USA
  • [2] Department of Mathematics, Rutgers University, Piscataway, NJ 08854-8019 USA

Annales de la faculté des sciences de Toulouse Mathématiques (2011)

  • Volume: 20, Issue: 4, page 801-841
  • ISSN: 0240-2963

Abstract

top
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.

How to cite

top

Gnang, Edinah K., Elgammal, Ahmed, and Retakh, Vladimir. "A Spectral Theory for Tensors." Annales de la faculté des sciences de Toulouse Mathématiques 20.4 (2011): 801-841. <http://eudml.org/doc/219706>.

@article{Gnang2011,
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.},
affiliation = {Department of Computer Science, Rutgers University, Piscataway, NJ 08854-8019 USA; Department of Computer Science, Rutgers University, Piscataway, NJ 08854-8019 USA; Department of Mathematics, Rutgers University, Piscataway, NJ 08854-8019 USA},
author = {Gnang, Edinah K., Elgammal, Ahmed, Retakh, Vladimir},
journal = {Annales de la faculté des sciences de Toulouse Mathématiques},
keywords = {tensors; spectral theory; multilinear algebra; tensor algebra; characteristic polynomial},
language = {eng},
month = {7},
number = {4},
pages = {801-841},
publisher = {Université Paul Sabatier, Toulouse},
title = {A Spectral Theory for Tensors},
url = {http://eudml.org/doc/219706},
volume = {20},
year = {2011},
}

TY - JOUR
AU - Gnang, Edinah K.
AU - Elgammal, Ahmed
AU - Retakh, Vladimir
TI - A Spectral Theory for Tensors
JO - Annales de la faculté des sciences de Toulouse Mathématiques
DA - 2011/7//
PB - Université Paul Sabatier, Toulouse
VL - 20
IS - 4
SP - 801
EP - 841
AB - 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.
LA - eng
KW - tensors; spectral theory; multilinear algebra; tensor algebra; characteristic polynomial
UR - http://eudml.org/doc/219706
ER -

References

top
  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). Zbl0212.06401MR268178
  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). Zbl0202.19101
  5. Dustin Cartwright and Bernd Sturmfels.— The number of eigenvalues of a tensor. Preprint arXiv:1004.4953. (2010). Zbl1213.14010MR2643580
  6. Lek-Heng Lim and Christopher Hillar.— Most tensor problems are np hard. Preprint arXiv:0911.1393v2 (2009). Zbl1281.68126
  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). Zbl1037.00003MR2286236
  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). Zbl0827.14036MR1264417
  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). Zbl0381.68045MR519843
  12. D. Grigoriev.— Multiplicative complexity of a bilinear form over a commutative ring. Lecture Notes Computer Science vol 118, p. 281-286 (1981). Zbl0467.68044MR652760
  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). Zbl1040.68045MR1770876
  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). Zbl0716.65043MR1079455
  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. Zbl1173.65029MR2535056
  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). Zbl0962.15005MR1780272
  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). Zbl0958.15026MR1780276
  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). Zbl1118.13001MR2290010
  28. Liqun Qi.— Eigenvalues of a real supersymmetric tensor. Journal of Symbolic Computation, 40, p. 1302-1324 (2005). Zbl1125.15014MR2178089
  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). Zbl1121.14050MR2271327
  30. Liqun Qi.— Eigenvalues and invariants of tensors. Journal of Mathematical Analysis and Applications, 325, p. 1363-1377 (2007). Zbl1113.15020MR2270090
  31. Ran Raz.— Tensor-rank and lower bounds for arithmetic formulas. Proceeding of the 42nd STOC (2010). MR2743315
  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). MR205395
  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). Zbl1034.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). Zbl1126.34325

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.