Yale Institute for Foundations of Data Science, Kline Tower 13th Floor, Room 1327, New Haven, CT 06511
Speaker: Christopher Moore,
Santa Fe Institute
Title: Tensor Networks, phase transitions, and algorithms
Wednesday, December 13, 2023
Tea & Reception: 3:30 pm (Kitchen)
Talk: 4:00 pm (Room #1327)
at the Yale institute for Foundations of Data Science, Kline Tower, 13th Floor
Abstract: Statistical physics and statistical inference have a deep connection, and ideas continue to flow between the two fields. Consider the following problem in high-dimensional statistics: there is a hidden vector v, and we observe v’s p-th outer product with itself, giving a tensor of arity p, with Gaussian noise in every entry. Given this observed tensor, our goal is to reconstruct v, as well as to reject the null hypothesis that the tensor consists only of noise. To a physicist, this is a planted p-spin model, where p is the arity of the tensor, and where the coupling matrix is correlated with the hidden vector. To a computer scientist, it is a tensor version of PCA (principal component analysis). But we lack a theory of linear algebra for tensors, so we can’t simply look at the dominant eigenvector and hope it is correlated with v. What should we do instead? What is the “spectrum” of a tensor anyway?
Many algorithms approach problems like this by “flattening” the tensor into a matrix, and then looking at the spectrum of the resulting matrix. But a more natural approach is to form a tensor network with copies of the observed tensor, and contract it to obtain a scalar or vector. I’ll describe how this picture helps us understand a conjectured phase transition where this problem becomes exponentially hard, and provides algorithms that work all the way up to that transition.
This is joint work with Tim Kunisky (Yale) and Alex Wein (UC Davis).
Bio: Cristopher Moore received his B.A. in Physics, Mathematics, and Integrated Science from Northwestern University, and his Ph.D. in Physics from Cornell. From 2000 to 2012 he was a professor at the University of New Mexico, with joint appointments in Computer Science and Physics. Since 2012, Moore has been a resident professor at the Santa Fe Institute; he has also held visiting positions at École Normale Superieure, École Polytechnique, Université Paris 7, École Normale Superieure de Lyon, Northeastern University, the University of Michigan, and Microsoft Research. He has written 160 papers at the boundary between mathematics, physics, and computer science, ranging from quantum computing, social networks, and phase transitions in NP-complete problems and Bayesian inference, to risk assessment in criminal justice. He is an elected Fellow of the American Physical Society, the American Mathematical Society, and the American Association for the Advancement of Science. With Stephan Mertens, he is the author of The Nature of Computation from Oxford University Press.
Website: https://sites.santafe.edu/~moore/