Department of Statistics
University of Chicago
"The Role of Tensors in Numerical Mathematics"
A tensor of order d or d-tensor is a multilinear map. It extends linear operators and bilinear forms, which are 2-tensors. We discuss how studies of higher-order tensors (i.e., d > 2) can shed light on questions in numerical linear algebra and optimization.
We start from a classical result: The arithmetic complexity of matrix multiplication is determined by the rank of a 3-tensor. This insight of Strassen, when further developed, permits us to answer more "modern" questions: (i) Can one extend the popular techniques of L^1-norm sparse vector recovery and nuclear norm low-rank matrix completion to tensors of order 3 or higher? (ii) Can one multiply two 3-tensors in a way that generalizes the usual matrix-matrix multiplication? The answer to both questions is no.
Our next question comes from nonlinear optimization. Can one extend the 1st (KKT) and 2nd order conditions for optimality of constrained optimization problems to higher orders? We will derive 3rd and 4th order conditions, involving 3- and 4-tensors, for constrained optimality and show that 5th and higher order conditions do not in general exist. One might notice the parallel to results on algebraic expressions for polynomial roots but they are unrelated.
We end with a curious nugget from convex optimization. Nesterov and Nemirovskii famously showed that conic programming problems with self-concordant barriers may be solved in polynomial time. Casting self-concordance as a statement about 6-tensors, we deduce that deciding self-concordance is itself an NP-hard problem.