Workshop on Tensor Decompositions

Summary of Suggested References

G. H. Golub, T. G. Kolda, J. G. Nagy, and C. F. Van Loan

This document is an attempt to summarize the references suggested by workshop participants. We emphasize that this bibliography is not meant to represent a comprehensive review of the literature on the mathematics, computation and applications of tensors, but rather it provides a sample of the main interests and experiences of workshop participants. In fact, a very extensive bibliographic

database on tensors may be found at http://three-mode.leidenuniv.nl/

1 Background on Tensors and Decompositions

Several participants remarked that they found the work by De Lathauwer, De Moor and Vandewalle [2], Kolda [3], and Zhang and Golub [5] to be especially useful for an initial introduction to tensor decompositions. These papers, in particular, focus on the basic problem of extending the ideas of rank and SVD for matrices to higher order tensors.

Related work by Kolda [4] should also be considered in this introductory material, as it provides some basic examples of tensor decompositions.

We also recommend the ”partial” survey paper by Comon [1], which includes an extensive bibliography and discusses the difficulties of extending the concept of rank to high order tensors. This paper also provides an introduction to a variety of applications where decomposition of high order tensors have been used.

References

[1] P. Comon. Tensor decompositions. In J. G. McWhirter and I. K. Proudler, editors, Mathematics in Signal Processing V, pages 1–24. Clarendon Press, Oxford, 2002. Online at http://www.i3s.unice.fr/∼comon/biblio.html#Clarendon02.

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

[3] T. G. Kolda. Orthogonal tensor decompositions. SIAM J. Matrix Anal. Appl., 23(1):243–255, 2001.

[4] T. G. Kolda. A counterexample to the possibility of an extension of the Eckart-Young low-rank approximation theorem for the orthogonal rank tensor decomposition. SIAM J. Matrix Anal. Appl., 24(3):762–767, 2002.

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

2 Algorithms and Mathematical Issues of Tensor Decompositions

One of the aims of this workshop is to gain a better understanding of the mathematical properties of tensor decompositions, and to provide a framework for notational standards. Such work will help contribute to better algorithms and efficient computational methods. Several workshop participants have worked on these issues, and have suggested the following list of references [1, 2, 3, 4, 5, 6, 7, 8].

References

[1] C. A. Andersson and R. Bro. Improving the speed of multi-way algorithms. Part I: Tucker3. Chemometrics and Intelligent Laboratory Systems, 42:93–103, 1998.

[2] C. A. Andersson and R. Bro. The N-way toolbox for matlab. Chemometrics and Intelligent Laboratory Systems, 52:1–4, 2000.

[3] P. Comon. Decompositions of quantics in sums of powers of linear forms. Signal Processing, 53(2):93–107, September 1996. Online at http://www.i3s.unice.fr/∼comon/biblio.html#SP96.

[4] L. De Lathauwer, B. De Moor, and J. Vandewalle. On the best rank-1 and rank-(R_{1}, R_{2}, …, R_{N}) approximation of higher-order tensors. SIAM J. Matrix Anal. Appl., 21:1324–1342, 2000.

[5] R. A. Harshman. An index formalism that generalizes the capabilities of matrix notation and algebra to n-way arrays. J. Chemom, 15(9):689–714, 2001.

[6] H. A. L. Kiers. Towards a standardized notation and terminology in multiway analysis. J. Chemom, 14:105–122, 2000.

[7] J. B. Kruskal. Rank, decomposition, and uniqueness for 3-way and n-way arrays. In R. Coppi and S. Bolasco, editors, Multiway Data Analysis, pages 8–18. Elsevier, 1989.

[8] N. D. Sidiropoulos and R. Bro. On the uniqueness of multilinear decomposition of n-way arrays. J. Chemom, 14(3):229–239, 2000.

3 Applications using Tensor Decompositions

A second aim of the conferences is to identify applications where tensors play an important role, and, in particular, applications which have the potential to substantially benefit from contributions arising from this workshop. Applications of interest include:

• Blind identification, beamforming, and source separation [1, 11, 13].

• Biological applications [2, 3, 4, 5].

• Factor analysis [25, 26, 27, 28, 29, 36].

• Food industry [8].

• Various applications in image processing and computer vision [32, 34, 35, 39, 40, 41, 42, 43].

• Independent component analysis [10, 12, 14, 15, 44].

• Large matrix computations, including Monte Carlo algorithms [16, 17, 18], Kronecker product factorizations, [20, 21, 22, 23, 24, 32, 34, 37, 38], and more general linear operators [6, 19, 31].

• Of course there are many other areas in which tensors play an important role, especially in statistical applications [7, 9, 30, 33].

References

[1] L. Albera, A. Ferreol, P. Comon, and P. Chevalier. Blind identification of overcomplete mixtures of sources (BIOME). Lin. Algebra Appl., to appear, 2004. Online at http://www.i3s.unice.fr/∼comon/biblio.html#LAA04.

[2] O. Alter, P. O. Brown, and D. Botstein. Singular value decompositions for genome-wide expression data. Proceedings of the National Academy of Sciences, 97(18):10101–10106, August 2000. Online at http://genome-www.stanford.edu/SVD/htmls/pnas.html.

[3] O. Alter, P. O. Brown, and D. Botstein. Processing and modeling genome-wide expression data using singular value decomposition. In M. L. Bittner, Y. Chen, A. N. Dorsel, and E. R. Dougherty, editors, Microarrays: Optical Technologies and Informatics, volume 4266, pages 171–186. SPIE, Bellingham, 2001. Online at http://genomewww.stanford.edu/SVD/htmls/spie.html.

[4] O. Alter, P. O. Brown, and D. Botstein. Generalized singular value decompositions for comparative analysis of genome-scale expression datasets of two different organisms. Proceedings of the National Academy of Sciences, 100(6):3351–3356, March 2003. Online at http://genomewww.stanford.edu/GSVD/htmls/pnas.html.

[5] O. Alter, G. H. Golub, P. O. Brown, and D. Botstein. Novel genome-scale correlation between DNA replication and RNA transcription during the cell cycle in yeast is predicted by data-driven models. In M. P. Deutscher, D. Black, P. E. Boehmer, G. D’Urso, T. Fletcher, F. Huijing, A. Marshall, B. Pulverer, B. Renault, J. M. Slingerland, and W. J. Whelan, editors, Proceedings of the Miami Nature Biotechnology Winter Symposium on the Cell Cycle, Chromosomes and Cancer, volume 15, Miami, 2004. University of Miami School of Medicine. Online at http://www.med.miami.edu/mnbws/Alter.pdf.

[6] G. Beylkin and M. Mohlenkamp. Numerical operator calculus in higher dimensions. Proceedings of the National Academy of Sciences, 99:10246–10251, 2002.

[7] R. Bro. Multiway calibration. Multilinear PLS. J. Chemom, 10(1):47–61, 1996.

[8] R. Bro. Multi-way Analysis in the Food Industry: Models, Algorithms and Applications. PhD thesis, University of Amsterdam (NL), 1998.

[9] R. Bro, N. D. Sidiropoulos, and A. K. Smilde. Maximum likelihood fitting using simple least squares algorithms. J. Chemom, 16(8–10):837–400, 2002.

[10] R. Bro and A. K. Smilde. Centering and scaling in component analysis. J. Chemom, 10(1):16– 33, 2003.

[11] J. F. Cardosa and A. Souloumiac. Blind beamforming for non-Gaussian signals. IEE Proceeding-F, 140(6):362–370, 1993.

[12] P. Comon. Independent component analysis, a new concept? Signal Process., 36:287–314, 1994.

[13] P. Comon. Blind identification and source separation in 2x3 under-determined mixtures. IEEE Trans. Signal Processing, 52(1):1–13, January 2004. Online at http://www.i3s.unice.fr/∼comon/biblio.html#TSP04.

[14] L. De Lathauwer. An introduction to independent component analysis. J. Chemom, 14:123– 149, 2000.

[15] L. De Lathauwer, B. De Moor, and J. Vandewalle. Independent component analysis and (simultaneous) third-order tensor diagonalization. IEEE Trans. Signal Proc., 21(4):1253–1278, 2001.

[16] P. Drineas, R. Kannan, and M. W. Mahoney. Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication. Technical Report TR-1269, Department of Computer Science, Yale University, 2004.

[17] P. Drineas, R. Kannan, and M. W. Mahoney. Fast Monte Carlo algorithms for matrices II: Computing low-rank approximations to a matrix. Technical Report TR-1270, Department of Computer Science, Yale University, 2004.

[18] P. Drineas, R. Kannan, and M. W. Mahoney. Fast Monte Carlo algorithms for matrices III: Computing an efficient approximate decomposition of a matrix. Technical Report TR-1271, Department of Computer Science, Yale University, 2004.

[19] G. Fann, G. Beylkin, R. J. Harrison, and K. E. Jordan. Singular operators in multiwavelet bases. IBM Journal of Research and Development, 28:161–171, 2004.

[20] J. M. Ford, I. V. Oseledets, and E. E. Tyrtyshnikov. Matrix approximations and solvers using tensor products and non-standard wavelet transforms related to irregular grids. Rus. J. Numer. Anal. and Math. Modelling, 19(2):185–204, 2004.

[21] J. M. Ford and E. E. Tyrtyshnikov. Combining Kronecker produce approximation with discrete wavelet transforms to solve dense, function related systems. SIAM J. Sci. Comp., 25(3):961– 981, 2003.

[22] G. A. Goreinov and E. E. Tyrtyshnikov. The maximal-volume concept in approximation by low-rank matrices. Contemporary Mathematics, 208:47–51, 2001.

[23] L. Grasedyck. Existence and computation of a low Kronecker-rank approximation to the solution of a tensor system with tensor right-hand side. Technical Report 48, Max-Planck-Institute for Mathematics and the Sciences, Leipzig, 2003. To appear in Computing.

[24] W. Hackbusch, B. N. Khoromskij, and E. Tyrtyshnikov. Hierarchical Kronecker tensor-product approximation. Technical Report 35, Max-Planck-Institute for Mathematics and the Sciences, Leipzig, 2003.

[25] R. A. Harshman. Foundations of the PARAFAC procedure: Models and conditions for an ”explanatory” multi-modal factor analysis. UCLA Working Papers in Phonetics, 16:1–16, 1970. Online at http://publish.uwo.ca/∼harshman/wpppfac0.pdf.

[26] R. A. Harshman. Determination and proof of minimum uniqueness conditions for PARAFAC1. UCLA Working Papers in Phonetics, 22:111–117, 1972. Online at http://publish.uwo.ca/∼harshman/wpppfac1.pdf.

[27] R. A. Harshman. PARAFAC2: Mathematical and technical notes. UCLA Working Papers in Phonetics, 22:30–47, 1972. Online at http://publish.uwo.ca/∼harshman/wpppfac2.pdf.

[28] R. A. Harshman and M. E. Lundy. The PARAFAC model for three-way factor analysis and multidimensional scaling. In H. G. Law, Jr. C. W. Snyder, J. Hattie, and R. P. McDonald, editors, Research Methods for Multimode Data Analysis, pages 122–215. Praeger, New York, 1984.

[29] R. A. Harshman and M. E. Lundy. PARAFAC: Parallel factor analysis. Computational Statistics and Data Analysis, 18:39–72, 1994.

[30] C. Henk and A. L. Kiers. Tuckals core rotations and constrained tuckals modelling. Statistica Applicata, 4:661–667, 1992.

[31] M. Huhtanen and O. Nevanlinna. Approximating real linear operators. Online at http://www.math.hut.fi/∼mhuhtane/valmis.ps.

[32] J. Kamm and J. G. Nagy. Optimal Kronecker product approximation of block Toeplitz matrices. SIAM J. Matrix Anal. Appl., 22(1):155–172, 2000.

[33] M. E. Lundy, R. A. Harshman, and J. B. Kruskal. A two-stage procedure incorporating good features of both trilinear and quadrilinear methods. In Multiway Data Analysis, pages 123–130. Elsevier, Amsterdam, 1989. Online at http://publish.uwo.ca/∼harshman/pfcore89.pdf.

[34] J. G. Nagy, M. K. Ng, and L. Perrone. Kronecker product approximation for image restoration with reflexive boundary conditions. SIAM J. Matrix Anal. Appl., 25:829–841, 2004.

[35] T. Nielsen, R. B. West, S. C. Linn, O. Alter, M. A. Knowling, J. O’Connell, S. Zhu, M. Fero, G. Sherlock, . R. Pollack, P. O. Brown, D. Botstein, and M. van de Rijn. Molecular characterization of soft tissue tumours: A gene expression study. The Lancet, 359(9314):1301–1307, April 2002. Online at http://genome-www.stanford.edu/SVD/Lancet.html.

[36] N. D. Sidiropoulos, R. Bro, and G. B. Giannakis. Parallel factor analysis in sensor array processing. IEEE Transactions on Signal Processing, 48(8):2377–2388, 2000.

[37] E. E. Tyrtyshnikov. Kronecker-product approximations for some function-related matrices. Linear Algebra Appl., 379:423–437, 2004.

[38] C. F. Van Loan. The ubiquitous Kronecker product. J. Comput. Appl. Math., 123:85–100, 2000.

[39] M. A. O. Vasilescu. Human motion signatures: Analysis, synthesis, recognition. In Proceedings of the International Conference on Pattern Recognition (ICPR’02), volume 3, pages 456–460, Quebec City, Canada, August 2002.

[40] M. A. O. Vasilescu and D. Terzopoulos. Multilinear analysis of image ensembles: Tensor-Faces. In Proceedings of the European Conf. on Computer Vision (ECCV’02), pages 447–460, Copenhagen, Denmark, May 2002.

[41] M. A. O. Vasilescu and D. Terzopoulos. Multilinear image analysis for facial recognition. In Proceedings of the International Conference on Pattern Recognition (ICPR’02), volume 2, pages 511–514, Quebec City, Canada, August 2002.

[42] M.A.O. Vasilescu and D. Terzopoulos. Multilinear subspace analysis for image ensembles. In IEEE Conference on Computer Vision and Pattern Recognition, volume 2, pages 93–99, Madison, WI, 2003.

[43] M.A.O. Vasilescu and D. Terzopoulos. Tensortextures: Multilinear image-based rendering. ACM Transactions on Graphics, 23(3):in press, 2004. Proc. ACM SIGGRAPH 2004.

[44] M.A.O. Vasilescu and D. Terzopoulos. Multilinear Independent Component Analysis. In Learning, Snowbird, April 2004.