Please register for the CV & Online Identity Workshop below.

Suppose we observe a matrix of data with a low-rank “signal” obscured by noise. The standard way to find the signal, at least approximately, is PCA (principal component analysis): just look at the eigenvectors of the matrix. For Gaussian noise, random matrix theory tells us exactly how well this works: that is, the accuracy we can achieve as a function of the signal-to-noise ratio. For tensors, such as three-index tables A_{ijk}, the situation is much more complex. Here there seems to be a “statistical-computational gap,” namely a regime where finding the signal is possible but exponentially hard. Physically, this corresponds to a “glass transition,” where the optimum becomes hidden behind an energy barrier. Mathematically, it means that we believe no polynomial-time algorithm exists, and that exhaustive search is necessary. I’ll give evidence for this exponential hardness by showing that no algorithm remotely similar to PCA can work. Along the way, I’ll give an introduction to tensor networks — a generalization of matrix products and traces thaat everyone, including network theorists, should know about.