Tensor Eigenvectors and Stochastic Processes

This web site accompanies the SIAM ALA 2018 minitutorial by Austin Benson and David Gleich.
10:45 AM–12:45 PM, May 6, 2018.
Room AAB201, SIAM ALA 2018, Hong Kong.

Presentation materials
  • Slides [slideshare] [pdf]
  • Handout [pdf]
  • Jupyter notebooks and scripts for generating content in the slides [code]
Additonal codes
  • Julia code for nonnegative tensor data clustering [code]
  • Julia code snippet for integrating the dynamical system for the dominant eigenvector with a forward Euler scheme [code]
Overview

The current generation of tensor analysis and computations has been a significant success story for studying datasets now routinely collected in diverse scientific disciplines such as signal processing, biology, and social networks. In this tutorial, the presenters will cover recent innovations and relationships between tensor eigenvectors and stochastic processes that present a challenging new set of computational motivations, generalizations, and trade-offs. Much of the ALA community is familiar with the close relationships between Markov chains—a simple type of stochastic process—and matrix computations. For instance, stationary distributions of Markov chains can be formulated as the solution to a matrix eigenvector problem. By the end of this mini-tutorial, we will have “gone up” a dimension and surveyed relationships between tensors, higher-order Markov chains, and various types of tensor eigenvectors, as well as their applications in data analysis. To this end, the tutorial will involve new types of stochastic processes including vertex-reinforced random walks and spacey random walks. This line of research area has raised several possibilities for future research, and this tutorial will place a specific emphasis on providing well-defined open problems.

Bibliography for slides
  • [Benson-Gleich 18] Computing tensor Z-eigenvectors with dynamical systems. A. R. Benson and D. F. Gleich. arXiv, 2018.
  • [Nie-Zhang 18] Real eigenvalues of nonsymmetric tensors. J. Nie. and X. Zhang. Computational Optimization and Applications, 2018.
  • [Arrigo-Gringod-Higham-Noferini 18] Nonbacktracking walk centrality for directed networks. F. Arrigo, P. Grindrod, D. J. Higham, V. Noferini. J. of Complex Networks, 2018.
  • [Benson-Gleich-Lim 17] The Spacey Random Walk: A Stochastic Process for Higher-Order Data. A. R. Benson, D. F. Gleich, and L.-H. Lim. SIAM Review, 2017.
  • [Culp-Pearson-Zhang 17] On the uniqueness of the Z1-eigenvector of transition probability tensors. J. Culp, K. Pearson, and T. Zhang. Linear and Multilinear Algebra, 2017.
  • [Qi-Luo 17] Tensor Analysis: Spectral Theory and Special Tensors. L. Qi and Z. Luo. SIAM, 2017.
  • [Meini-Poloni 17] Perron–based algorithms for the multilinear pagerank. B. Meini and F. Poloni. arXiv, 2017.
  • [Wu-Benson-Gleich 16] General Tensor Spectral Co-clustering for Higher-Order Data. T. Wu, A. R. Benson, and D. F. Gleich. Advances in Neural Information Processing Systems, 2016.
  • [Hu-Qi-Zhang 16] Computing the geometric measure of entanglement of multipartite pure states by means of non-negative tensors. S. Hu, L. Qi, and G. Zhang. Physical Review A, 2016.
  • [Gleich-Lim-Yu 15] Multilinear PageRank. D. F. Gleich, L.-H. Lim, and Y. Yu. SIAM J. on Matrix Analysis and Applications, 2015.
  • [Li-Ng 14] On the limiting probability distribution of a transition probability tensor. W. Li and M. K. Ng. Linear and Multilinear Algebra, 2014.
  • [Nie-Wang 14] Semidefinite Relaxations for Best Rank-1 Tensor Approximations. J. Nie and L. Wang. SIAM J. on Matrix Analysis and Applications, 2014.
  • [Kolda-Mayo 14] T. G. Kolda and J. R. Mayo. An Adaptive Shifted Power Method for Computing Generalized Tensor Eigenpairs. SIAM J. on Matrix Analysis and Applications, 2014.
  • [Chu-Wu 14] On the second dominant eigenvalue affecting the power method for transition probability tensors. M. T. Chu and S.-J. Wu. Technical Report, 2014.
  • [Cui-Dai-Nie 14] All Real Eigenvalues of Symmetric Tensors. C.-F. Cui, Y.-H. Dai, J. Nie. SIAM J. on Matrix Analysis and Applications, 2014.
  • [Rosvall+ 14] Memory in network flows and its effects on spreading dynamics and community detection. M. Rosvall, A. V. Esquivel, A. Lancichinetti, J. D. West, and R. Lambiotte. Nature Communications, 2014.
  • [Krzakala+ 13] Spectral redemption in clustering sparse networks. F. Krzakala, C. Moore, E. Mossel, J. Neeman, A. Sly, L. Zdeborová, and P. Zhang. Proceedings of the National Academy of Sciencies, 2013.
  • [Chang-Qi-Zhang 13] A survey on the spectral theory of nonnegative tensors. K. Chang, L. Qi, and T. Zhang. Numerical Linear Algebra with Applications, 2013.
  • [Hillar-Lim 13] Most Tensor Problems Are NP-Hard. C. J. Hillar, L.-H. Lim. J. of the ACM, 2013.
  • [Ragnarsson-Van Loan 13] Block tensors and symmetric embeddings. S. Ragnarsson and C. F. Van Loan. Linear Algebra and its Applications, 2013.
  • [Chierichetti+ 12] Are Web Users Really Markovian? F. Chierichetti, R. Kumar, P. Raghavan, and T. Sarlós. Proceedings of the 21st international conference on World Wide Web, 2012.
  • [Meini-Poloni 11] A Perron Iteration for the Solution of a Quadratic Vector Equation Arising in Markovian Binary Trees. B. Meini and F. Poloni. SIAM J. on Matrix Analysis and Applications, 2011.
  • [Bini-Meini-Poloni 11] On the solution of a quadratic vector equation arising in Markovian Binary Trees. D. A. Bini, B. Meini, and F. Poloni. Numerical Linear Algebra with Applications, 2011.
  • [Kolda-Mayo 11] T. G. Kolda and J. R. Mayo. Shifted Power Method for Computing Tensor Eigenpairs. SIAM J. on Matrix Analysis and Applications, 2011.
  • [Qi-Wang-Wu 08] D-eigenvalues of diffusion kurtosis tensors. L. Qi, Y. Wang, E. X. Wu. J. of Computational and Applied Mathematics, 2008.
  • [de Silva-Lim 08] Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem. V. de Silva and L.-H. Lim. SIAM J. on Matrix Analysis and Applications, 2008.
  • [Bean-Kontoleon-Taylor 08] Markovian trees: properties and algorithms. N. G. Bean, N. Kontoleon, and P. G. Taylor. Annals of Operations Research, 2008.
  • [Ching-Ng-Fung 08] Higher-order multivariate Markov chains and their applications. W. K. Ching, M. K. Ng, and E. S. Fung. Linear Algebra and its Applications, 2008.
  • [Pemantle 07] A survey of random processes with reinforcement. R. Pemantle. Probability Surveys, 2007.
  • [Lim 05] Singular values and eigenvalues of tensors: a variational approach. L.-H. Lim. Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, 2005.
  • [Ching-Fung-Ng 04] Higher-order Markov chain models for categorical data sequences. W. K. Ching, E. S. Fung, and M. K. Ng. Naval Research Logistics, 2004.
  • [Kolda 03] A Counterexample to the Possibility of an Extension of the Eckart–Young Low-Rank Approximation Theorem for the Orthogonal Rank Tensor Decomposition. T. G. Kolda. SIAM J. on Matrix Analysis and Applications, 2003.
  • [Wei-Goldbart 03] Geometric measure of entanglement and applications to bipartite and multipartite quantum states. T.-C. Wei and P. M. Goldbart. Physical Review A, 2003.
  • [Kofidis-Regalia 02] On the Best Rank-1 Approximation of Higher-Order Supersymmetric Tensors. E. Kofidis and P. A. Regalia. SIAM J. on Matrix Analysis and Applications, 2002.
  • [Kofidis-Regalia 01] Tensor approximation and signal processing applications. E. Kofidis and P. A. Regalia. Contemporary Mathematics, 2001.
  • [Kolda 01] Orthogonal Tensor Decompositions. T. G. Kolda. SIAM J. on Matrix Analysis and Applications, 2001.
  • [De Lathauwer-De Moor-Vandewalle 00] On the Best Rank-1 and Rank-(R1, R2,...,RN) Approximation of Higher-Order Tensors. L. De Lathauwer, B. De Moor, and J. Vandewalle. SIAM J. on Matrix Analysis and Applications, 2000.
  • [Pirolli-Pitkow 99] Distributions of surfers' paths through the World Wide Web: Empirical characterizations. P. L. T. Pirolli and J. E. Pitkow. World Wide Web, 1999.
  • [De Lathauwer 97] Signal processing based on multilinear algebra. L. De Lathauwer. PhD thesis, Katholieke Universiteit Leuven. 1997.
  • [Benaïm 97] Vertex-reinforced random walks and a conjecture of Pemantle. M. Benaïm. The Annalys of Probability, 1997.
  • [Borodovsky-McIninch 93] Recognition of genes in DNA sequence with ambiguities. M. Borodovsky and J. McIninch. BioSystems, 1993.
  • [Pemantle 92] Vertex-reinforced random walk. R. Pemantle. Probability Theory and Related Fields, 1992.
  • [Kemeny-Smell 76] Finite Markov Chains. J. G. Kemeny and J. L. Snell. Springer-Verlag New York, 1976.