Consider hypothesis testing random matrices: given a draw from one of two matrix distributions, an algorithm must try to deduce which distribution it came from. If these distributions are orthogonally invariant—unchanged by conjugation by an orthogonal matrix—then a natural class of test statistics is the polynomials of a matrix that are themselves invariant under orthogonal conjugation. As is well-known, those polynomials are generated by traces of matrix powers. Classical invariant theory describes a similar situation for tensors: a canonical collection of polynomials given by evaluating “tensor networks” generates all invariant polynomials. Moreover, recent investigations in theoretical computer science suggest that, for many invariant matrix- and tensor-valued statistical problems, some such polynomial statistic should perform optimally for a given computational budget. It is then natural to ask: for specific invariant statistical problems, what is the performance of algorithms computing low-degree invariant polynomials?
I will present new results on a remarkable collection of polynomials of a matrix or tensor that allow this question to be addressed in several cases. On the one hand, these polynomials provide an approximately orthonormal basis of the space of invariant polynomials with respect to an invariant Gaussian measure, the natural “null hypothesis” for many testing problems. On the other hand, they obey an additive free convolution rule analogous to the free cumulants (more precisely, their non-asymptotic analogs in finite free cumulants) of matrix-valued free probability theory. I will show how these properties, taken together, allow us to understand the cost of testing for exceptional principal components and for latent geometric structure in a random tensor. Finally, I will discuss how these results might pave the way to a fuller extension of free probability from random matrices to random tensors.
Based on joint work with Cris Moore and Alex Wein.
