Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

The traffic distribution of an n-by-n matrix is a generalization of its spectral distribution which captures the values of all S_n-symmetric polynomial functions of the matrix. Therefore, the traffic distribution describes the universality class of all S_n-equivariant algorithms running on the matrix, including first-order iterative algorithms such as Approximate Message Passing and gradient descent-type optimization. We study random matrix ensembles and prove that only "treelike" polynomials are non-negligible in many cases, leading to a new Treelike Approximate Message Passing algorithm. We then show that some deterministic pseudorandom matrices such as the Walsh--Hadamard matrix also have the treelike property, obtaining the first computation of the traffic distribution for a nontrivial deterministic matrix and hence the first universality result for this class of algorithms with a deterministic input. This is based on joint work with Nicola Gorini, Tim Kunisky, and Lucas Pesenti.