Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

An order-3 tensor is an n-by-n-by-n array of real numbers. We consider the task of decomposing a given tensor as the sum of rank-1 tensors, using the minimal number of terms. This task has various applications in statistics and data science, such as learning the latent parameters of certain statistical models from the empirical third moment tensor. Under the standard assumption that the tensor components are "generic," a classical method called simultaneous diagonalization or "Jennrich's algorithm" can decompose tensors of rank up to r <= n in polynomial time. A recent result of Koiran (2024) improves this to r <= 4n/3, and we improve this further to r <= 2n. The algorithm is based on a non-trivial procedure for "flattening" tensors to matrices. We also give a matching impossibility result, showing that no flattening of the style we consider can surpass 2n. This may suggest a fundamental barrier for fast algorithms.