Structured multi-way arrays and their applications

Abstract

Based on the structure of the rank-1 matrix and the different unfolding ways of the tensor, we present two types of structured tensors which contain the rank-1 tensors as special cases. We study some properties of the ranks and the best rank-r approximations of the structured tensors. By using the upper-semicontinuity of the matrix rank, we show that for the structured tensors, there always exist the best rank-r approximations. This can help one to better understand the sequential unfolding singular value decomposition (SVD) method for tensors proposed by J. Salmi et al. [IEEE Trans Signal Process, 2009, 57(12): 4719–4733] and offer a generalized way of low rank approximations of tensors. Moreover, we apply the structured tensors to estimate the upper and lower bounds of the best rank-1 approximations of the 3rd-order and 4th-order tensors, and to distinguish the well written and non-well written digits.

Keywords

Tensor / rank / singular value decomposition (SVD) / higher-order singular value decomposition / approximation

References

[1] Chang K, Pearson K, Zhang T. Perron-Frobenius theorem for nonnegative tensors. Commun Math Sci, 2008, 6: 507-520

[2] Chang K, Pearson K, Zhang T. On eigenvalue problems of real symmetric tensors. J Math Anal Appl, 2009, 350: 416-422

[3] Comon P. Mcwhirter J G, Proudler I K. Tensor decompositions: state of the art and applications. Mathematics in Signal Processing V, 2001, Oxford: Oxford University Press 1 24

[4] De Lathauwer L. Signal Processing Based on Multilinear Algebra. Ph D Thesis, 1997, Leuven: Katholieke Universiteit Leuven

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

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

[7] De Silva V, Lim L H. Tensor rank and the ill-posedness of the best low-rank approximation problem. SIAM J Matrix Anal Appl, 2008, 30(3): 1084-1127

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

[9] Hastie T, Tibshirani R, Friedman J. The Elements of Statistical Learning, 2001 2nd ed. New York: Springer-Verlag

[10] Huang J, Wium H, Qvist K B, Esbensen K. Multi-way methods in image analysis: Relationships and applications. Chemom Intel Lab Syst, 2003, 66: 141-158

[11] Jiang Y, Chen R M M, Huang Z L. A parallel approach for computing complex eigenvalue problems. IEICE T Fund Electr, 2000, E83A(10): 2000-2008

[12] Jiang Y, Wing O. On the spectra of waveform relaxation operators for circuit equations. IEICE T Fund Electr, 1998, E81A(4): 685-689

[13] Kiers H A L. Towards a standardized notation and terminology in multiway analysis. J Chemometrics, 2000, 14: 105-122

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

[15] Kong X, Jiang Yaolin. Subtracting a best rank-1 approximation from p × p × 2 (p ⩾ 2) tensors. Numer Linear Algebra Appl, 2012, 19(3): 503-523

[16] Oseledets I V, Tyrtyshnikov E E. Breaking the curse of dimensionality, or how to use SVD in many dimensions. SIAM J Sci Comput, 2009, 31(5): 3744-3759

[17] Qi Liqun. Eigenvalues of a real supersymmetric tensor. J Symbolic Comput, 2005, 40: 1302-1324

[18] Qi Liqun. Rank and eigenvalues of a supersymmetric tensor, a multivariate homogeneous polynomial and an algebraic surface defined by them. J Symbolic Comput, 2005, 41: 1309-1327

[19] Qi L, Dai H, Han Deren. Conditions for strong ellipticity and M-eigenvalues. Front Math China, 2009, 4(2): 349-364

[20] Qi L, Sun W, Wang Yiju. Numerical multilinear algebra and its applications. Front Math China, 2007, 2: 501-526

[21] Salmi J, Richter A, Koivunen V. Sequential unfolding SVD for tensors with applications in array signal processing. IEEE Trans Signal Process, 2009, 57(12): 4719-4733

[22] Savas B, Richter A, Eldén L. Handwritten digit classification using higher order singular value decomposition. Pattern Recognition, 2007, 40: 993-1003

[23] Sun J, Zeng H, Liu H, Lu Y, Chen Zheng. CubeSVD: A novel approach to personalized web search. Proceedings of the 14th International Conference on World Wide Web, 2005, New York: ACM Press 382 390

[24] Tucker L R. Some mathematical notes on three-mode factor analysis. Psychometrika, 1996, 31: 279-311

[25] Zhang T, Golub G H. Rank-one approximation to high order tensor. SIAM J Matrix Anal Appl, 2001, 23(2): 534-550