Numerical multilinear algebra and its applications

Abstract

Numerical multilinear algebra (or called tensor computation), in which instead of matrices and vectors the higher-order tensors are considered in numerical viewpoint, is a new branch of computational mathematics. Although it is an extension of numerical linear algebra, it has many essential differences from numerical linear algebra and more difficulties than it. In this paper, we present a survey on the state of the art knowledge on this topic, which is incomplete, and indicate some new trends for further research. Our survey also contains a detailed bibliography as its important part. We hope that this new area will be receiving more attention of more scholars.

Keywords

Numerical multilinear algebra / higher order tensor / tensor decomposition / lower rank approximation of tensor / multi-way data analysis

References

[1] Alon N., de la Vega W. F., Kannan R. Random sampling and approximation of max-csps. J Comput System Sci, 2003, 67: 212-243.

[2] Bergman G. M. Ranks of tensors and change of base field. J Algebra, 1969, 11: 613-621.

[3] Bienvenu G., Kopp L. Optimality of high-resolution array processing using the eigen-system approach. IEEE Trans ASSP, 1983, 31: 1235-1248.

[4] Cao X. R., Liu R. W. General approach to blind source separation. IEEE Trans Signal Processing, 1996, 44: 562-570.

[5] Cardoso J F. Super-symmetric decomposition of the forth-order cumulant tensor. Blind identification of more sources than sensors. In: Proceedings of the IEEE International Conference on Acoust, Speech, and Signal Processing (ICASSP’91), Toronto, Canada, 1991

[6] Cardoso J. F. High-order contrasts for independent component analysis. Neural Computation, 1999, 11: 157-192.

[7] Caroll J. D., Chang J. J. Analysis of individual differences in multidimensional scaling via n-way generalization of Eckart-Young decomposition. Psychometrika, 1970, 35: 283-319.

[8] Comon P. Tensor diagonalization, a useful tool in signal processing. In: Blanke M, Soderstrom T, eds. IFAC-SYSID, 10th IFAC Symposium on System Identification (Copenhagen, Denmark, July 4–6, 1994. Invited Session). Vol. 1, 77–82

[9] Comon P. Independent component analysis, a new concept?. Signal Processing, Special Issue on Higher-Order Statistics, 1994, 36: 287-314.

[10] Comon P., Mourrain B. Decomposition of quantics in sums of powers of linear forms. Signal Processing, Special Issue on Higher-Order Statistics, 1996, 53: 96-107.

[11] Comon P. Block methods for channel identification and source separation. In: IEEE Symposium on Adaptive Systems for Signal Process, Commun Control (Lake Louise, Alberta, Canada, Oct 1–4, 2000. Invited Plenary). 87–92

[12] Comon P., Chevalier P. Haykin S. Blind source separation: Models, concepts, algorithms, and performance. Unsupervised Adaptive Filtering, Vol 1, 2000, New York: John Wiley.

[13] Comon P. McWhirter J. G., Proundler I. K. Tensor decompositions: State of the art and applications. Mathematics in Signal Processing, V, 2002, Oxford: Oxford University Press.

[14] Comon P. Canonical tensor decompositions. In: ARCC Workshop on Tensor Decompositions, Americal Institute of Mathematics (AIM), Palo Alto, California, USA, July 19–23, 2004

[15] Comon P, Golub G, Lim L H, et al. Symmetric tensors and symmetric tensor rank. SIAM J Matrix and Applications, 2007 (in press)

[16] Coppi R., Bolasco S. Multiway Data Analysis, 1989, Amsterdam: Elsevier.

[17] de la Vega W. F., Kannan R., Karpinski M. Tensor Decomposition and Approximation Algorithms for Constraint Satisfaction Problems, 2005, New York: ACM Press, 747-754.

[18] Defant A., Floret K. Tensor Norms and Operator Ideals. North-Holland Mathematics Studies, No 176, 1993, Amsterdam: North-Holland.

[19] Ferrier C. Hilbert’s 17th problem and best dual bounds in quadatic minimization. Cybernet Systems Anal, 1998, 34: 696-709.

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

[21] Golub G, Kolda T G, Nagy J, et al. Workshop on Tensor Decompositions, American Institute of Mathematics, Palo Alto, California, 19–23 July, 2004. http://www.aimath.org/WWN/tensordecomp

[22] Golub G, Mahoney M, Drinears P, et al. Workshop for Modern Massive Data Sets, 21–24 June, 2006. http://www.stanford.edu/group/mmds

[23] Golub G, Mahoney M, Drinears P, et al. Bridge the gap between numerical linear algebra, theoretical computer science, and data applications. SIAM News, 2006, 39(8). http://www.siam.org/pdf/news/1019.pdf

[24] Greub W. H. Multilinear Algebra, 1967, Berlin: Springer-Verlag.

[25] Harshman R. A. Determination and proof of minimum uniqueness conditions of PARAFAC. UCLA Working Papers in Phonetics, 1972, 22: 111-117.

[26] He X., Sun W. Introduction to Generalized Inverses of Matrices, 1990, Nanjing: Jiangsu Sci & Tech Publishing House.

[27] Hitchcock F. L. The expression of a tensor or a polyadic as a sum of products. J Math Physics, 1927, 6: 164-189.

[28] Hitchcock F. L. Multiple invariants and generalized rank of a p-way matrix or tensor. J Math Physics, 1927, 7: 39-79.

[29] Kilmer M E, Martin C D M. Decomposing a tensor. SIAM News, 2004, 37. http://www.siam.org/siamnews/11-04/tensor.pdf

[30] Kofidis E., Regalia P. A. Olshevsky V. Tensor approximation and signal processing applications. Structured Matrices in Mathematics, Computer Science and Engineering, Vol. I, 2001, Providence: AMS.

[31] Kofidis E., Regalia P. A. On the best rank-1 approximation of higher-order supersymmetric tensors. SIAM J Matrix Anal Appl, 2002, 23: 863-884.

[32] Kolda T. G. Orthogonal tensor decompositions. SIAM J Matrix Anal Appl, 2001, 22: 243-255.

[33] Kroonenberg P. M. Coppi R., Bolasco S. Singular value decompositions of interactions in three-way contigency tables. Multiway Data Analysis, 1989, North Holland: Elsevier Science Publishers, 169-184.

[34] Kruskal J. B. Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics. Linear Algebra and Applications, 1977, 18: 95-138.

[35] Lasserre J. B. Global optimization with polynomials and the problem of moments. SIAM J Optimization, 2001, 11: 796-817.

[36] Lasserre J. B. Semidefinite programming vs. LP relaxations for polynomial programming. Mathematics of Operations Research, 2002, 27: 347-360.

[37] Lasserre J. B. Polynomial programming: LP-relaxations also converge. SIAM J Optimization, 2004, 15: 383-393.

[38] Lasserre J. B. A sum of squares approximation of nonnegative polynomials. SIAM J Optimization, 2006, 16: 751-765.

[39] De Lathauwer L, Comon P, De Moor B, et al. Higher-order power method—application in independent component analysis. In: Proceedings of the International Symposium on Nonlinear Theory and Its Applications (NOLTA’95), Las Vegas, NV. 1995, 91–96

[40] De Lathauwer L., De Moor B. From matrix to tensor: Multilinear algebra and signal processing. Mathematics in Signal Processing, IMA Conference Series (Warwick, Dec 17–19, 1996), 1996, Oxford: Oxford University Press.

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

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

[43] De Lathauwer L. First-order perturbation analysis of the best rank-(R₁, R₂, R₃) approximation in multilinear algebra. J Chemometrics, 2004, 18: 2-11.

[44] De Lathauwer L., De Moor B., Vandewalle J. Computation of the canonical decomposition by means of a simultaneous generalized Schur decomposition. SIAM J Matrix Anal Appl, 2004, 26: 295-327.

[45] De Lathauwer L, Comon P. Workshop on Tensor Decompositions and Applications, Luminy, Marseille, France, August 29–September 2, 2005. http://www.etis.ensea.fr/wtda

[46] Leon S. Workshop Report: Algorithms for Modern Massive Data Sets (MMDS). NA Digest, 2006, Vol 6, No 27

[47] Leurgans S. E., Ross R. T., Abel R. B. A decomposition for three-way arrays. SIAM J Matrix Anal Appl, 1993, 14: 1064-1083.

[48] Li C, Sun W. A nonsmooth Newton-type method for nonlinear semidefinite programs. Technical Report, School of Mathematics and Computer Science, Nanjing Normal University, March, 2007

[49] Li C, Sun W. Filter-Successive Linearization Methods for Nonlinear Semidefinite Programs. Technical Report, School of Mathematics and Computer Science, Nanjing Normal University, December, 2006

[50] Lim L H. Singular values and eigenvalues of tensors: A variational approach. In: Proceedings of the 1st IEEE International Workshop on Computational Advances of multi-sensor Adaptive Processing (CAMSAP), December 13–15, 2005. 2005, 129–132

[51] Liu X., Sidiropoulos N. D. Cramer-Rao lower bounds for low-rank decomposition of multidimensional arrays. IEEE Trans on Signal Processing, 2001, 49: 2074-2086.

[52] Luo Z. Q., Lu J. On blind source separation using mutual information criterion. Mathematical Programming, Ser B, 2003, 97: 587-603.

[53] McCullagh P. Tensor Methods in Statistics. Monographs in Statistics and Applied Probability, 1987, London: Chapman and Hall.

[54] Merris R. Multilinear Algebra, 1997, The Netherland: Gordon and Breach Science Publishers.

[55] Moré J. J. Watson G. A. The Levenberg-Marquadt algorithm: implementation and theory. Numerical Analysis, 1977, Berlin: Springer-Verlag, 105-116.

[56] Nesterov Y. Frenk H., Roos K., Terlaky T. Squared functional systems and optimization problems. High Performance Optimization, 2000, Dordrecht: Kluwer, 405-440.

[57] Ni G., Qi L., Wang F. The degree of the E-characteristic polynomial of an even order tensor. Journal of Mathematical Analysis and Applications, 2007, 329: 1218-1229.

[58] Ni G. Y., Wang Y. J. On the best rank-1 approximation to higher-order symmetric tensors. Mathematical and Computer Modeling, 2007, 46: 1345-1352.

[59] Northcoot D. G. Multilinear Algebra, 1984, Cambridge: Cambridge University Press.

[60] Paatero P. A weighted non-negative least squares algorithm for three-way “PARAFAC” factor analysis. Chemometrics Intell Lab Syst, 1997, 38: 223-242.

[61] Parrilo P. A. Semidefinite programming relaxation for semialgebraic problems. Mathematical Programming, 2003, 96: 293-320.

[62] Qi L. Eigenvalues of a real supersymmetric tensor. Journal of Symbolic Computation, 2005, 40: 1302-1324.

[63] Qi L. Rank and eigenvalues of a supersymmetric tensor, a multivariate homogeneous polynomial and an algebraic surface defined by them. Journal of Symbolic Computation, 2006, 41: 1309-1327.

[64] Qi L. Eigenvalues and invariants of tensors. Journal of Mathematical Analysis and Applications, 2007, 325: 1363-1377.

[65] Qi L, Wang F, Wang Y. Z-eigenvalue methods for a global polynomial optimization problem. Mathematical Programming, 2008 (in press)

[66] Schnabel R. B. Bachem A., Grotschel M., Korte B. Conic methods for unconstrained optimization and tensor methods for nonlinear equations. Mathematical Programming, The State of the Art, 1983, Berlin: Springer-Verlag, 417-438.

[67] Schnabel R. B., Frank P. D. Tensor methods for nonlinear equations. SIAM J Numerical Analysis, 1984, 21: 815-843.

[68] Schnabel R. B., Chow T. T. Tensor methods for unconstrained optimization using second derivatives. SIAM J Optimization, 1991, 1: 293-315.

[69] Schott J. R. Matrix Analysis for Statistics, 2005 2 New York: John Wiley & Sons, Inc.

[70] Schweighofer M. Optimization of polynomials on compact semialgebraic sets. SIAM J Optimization, 2005, 15: 805-825.

[71] Shor N. Z. Class of global minimum bounds of polynomial functions. Cybernetics, 1987, 23: 731-734.

[72] Shor N. Z. Nondifferentiable Optimization and Polynomial Problems, 1998, Dordrecht: Kluwer.

[73] Sidiropoulos N., Giannakis G., Bro R. Blind PARAFAC receivers for DS-CDMA systems. IEEE Trans Signal Process, 2000, 48: 810-823.

[74] Sidiropoulos N., Bro R. On the uniqueness of multilinear decomposition of N-way arrays. J Chemometrics, 2000, 14: 229-239.

[75] Sun W. Quasi-Newton methods for nonlinear matrix equations. Technical Report, School of Mathematics and Computer Science, Nanjing Normal University, 2006

[76] Sun W., Du Q., Chen J. Computational Methods, 2007, Beijing: Science Press.

[77] Sun W., Yuan Y. Optimization Theory and Methods: Nonlinear Programming, 2006, New York: Springer.

[78] Talwar S., Vilberg M., Paulraj A. Blind estimation of multiple cochannel digital signals arriving at an antenna array: Part I, algorithms. IEEE Trans Signal Process, 1996, 44: 1184-1197.

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

[80] Van Der Veen A.-J., Paulraj A. An analytical constant modulus algorithm. IEEE Trans Signal Processing, 1996, 44: 1136-1155.

[81] Vorobyov S. A., Rong Y., Sidiropoulos N. D. Robust iterative fitting of multilinear models. IEEE Trans on Signal Processing, 2005, 53: 2678-2689.

[82] Wang Y. J., Qi L. Q. On the successive supersymmetric rank-1 decomposition of higher-order supersymmetric tensors. Numerical Linear Algebra with Applications, 2007, 14(6): 503-519.

[83] Zhang T., Golub G. H. Rank-one approximation to high order tensors. SIAM J Matrix Anal Appl, 2001, 23: 534-550.