Grothendieck Constant and Structured Matrix Computations

Wednesday, January 27, 2016 - 10:15am - 11:05am
Keller 3-180
Lek-Heng Lim (University of Chicago)
We show that in many instances, at the heart of a problem in numerical computation sits a special 3-tensor, the structure tensor of the problem that uniquely determines its underlying algebraic structure. Any decomposition of the structure tensor into rank-1 terms gives an explicit algorithm for solving the problem. The rank of the structure tensor measures the speed of the fastest possible algorithm for the problem, whereas the nuclear and spectral norms quantify the numerical stability of the stablest algorithm for the problem.

We illustrate with a few examples. We show that the mysterious Grothendieck constant that plays an important role in unique games conjecture and SDP relaxations of NP-hard problems arises as the spectral norm of such a structure tensor. We determine the fastest algorithms for the basic operation underlying Krylov subspace methods --- the structured matrix-vector products for sparse, banded, triangular, symmetric, circulant, Toeplitz, Hankel, Toeplitz-plus-Hankel, BTTB matrices --- by analyzing their structure tensors. The last part is joint work with Ke Ye.
MSC Code: