One Day Meeting in Discrete Structures 3

An Introduction to Tensor Methods, Lieven De Lathauwer (KU Leuven)
We give an introduction to tensor decompositions and applications, highlighting some recent trends. We discuss basics such as higher-order variants of "rank" and fundamental decompositions such as the canonical polyadic decomposition and the Tucker decomposition. The uniqueness of CPD, under mild conditions which do not have a matrix counterpart, makes it a powerful tool for signal separation and data analysis. Block term decompositions allow us to retrieve components that are more general and possibly more realistic than rank-1 terms. Multilinear singular value decomposition and low multilinear rank approximation are key in multilinear extensions of subspace techniques. Coupled decompositions express complicated tasks as combinations of pieces that are manageable. We briefly explain why numerical multilinear algebra is very different from numerical linear algebra. Tensor trains and hierarchical Tucker decompositions allow one to break the curse of dimensionality in a numerically reliable manner and show promise for big data analysis in combination with compressed sensing.
[1] A. CICHOCKI, D. MANDIC, A.-H. PHAN, C. CAIAFA, G. ZHOU, Q. ZHAO AND L. DE LATHAUWER, Tensor decompositions for signal processing applications. From two-way to multiway component analysis, IEEE Signal Processing Magazine 32(2) (2015), pp. 145-163.
[2] N.D. SIDIROPOULOS, L. DE LATHAUWER, X. FU, K. HUANG, E. E. PAPALEXAKIS AND C. FALOUTSOS. Tensor decomposition for signal processing and machine learning, IEEE Transactions on Signal Processing, to appear (2017). URL: http://ieeexplore.ieee.org/document/7891546/.
[3] N. VERVLIET, O. DEBALS, L. SORBER, M. VAN BAREL AND L. DE LATHAUWER, Tensorlab v3.0, Available online, March 2016. URL: http://www.tensorlab.net/.

Tensor network representations of quantum many-body ground states, Nick Bultinck (U Ghent)
A wide variety of interesting quantum mechanical systems can be modeled by placing particles on a lattice and letting them interact in a local way. Since the total Hilbert space dimension scales exponentially in the number of particles, very methods are known that can deal with strong interactions. In this talk I will explain how locality of the interactions implies that the ground state of such systems has special entanglement properties, which allow it to be efficiently represented as a tensor network state. This provides new possibilities for studying the low-energy properties of quantum many-body systems, both numerically and analytically.

Tensors and The Complexity of Matrix Multiplication: An Introduction, Thomas Sibut-Pinote
The optimal complexity of multiplying two matrices of size n may seem at first like a deceptively simple problem, but it has remained an unsolved problem despite numerous impressive improvements on the lowest known bound. The first nontrivial algorithm by Strassen proved O(n^2.81), and the latest improvement by Le Gall gives O(n^2.3728639). This presentation will concern the ideas linked to tensor rank and tensor "degenerate rank" which allow for these improvements, it will review Strassen's algorithm in that light and will attempt to give a notion of how the more recent improvements are obtained.

Slice rank of tensors and its applications, Wenjie Fang (ENS Lyon)
In additive combinatorics, the recent work of Croot, Lev and Pach introduces a powerful and simple method called the ``polynomial method'', which led to breakthroughs in upper bounds of several problems in additive and extremal combinatorics. In this talk, we present an analysis of the polynomial method by Sawin and Tao, which is centered around a new notion called ``slice rank'' on tensors. Through two examples, cap set and sunflower-free families, we will see a general scheme of the polynomial method and how it can be applied to various problems. We will also see some limits of this method.