The identifiability problem for tensors consist in determining which tensors have a unique minimal decomposition as a sum of tensors of rank 1 (up to scaling and reordering). It turns out that the problem, both for general tensors and for symmetric tensors, can be also attached with methods of projective Geometry, related with the study of tangent spaces to secant varieties. We will review briefly the geometric background and outline the construction of recent algorithms to detect the identifiability, together with a sketch of achievements in the topic, based on the geometric setting.

Equivariant local systems on orbits of a group action give rise via the Riemann-Hilbert correspondence to equivariant D-modules, which are typically hard to describe. I will explain how to compute explicitly the characters of the GL-equivariant D-modules supported on the Veronese cones. In particular, I will appeal to recent results of de Cataldo, Migliorini and Mustaţă on the Decomposition Theorem for toric maps, and show how representation theoretic stabilization results are used in a crucial way in the calculation. As an application, I'll show that the local cohomology with support on a Veronese cone is a simple equivariant D-module.

This talk will present a brief survey on an approach for designing matrix multiplication algorithms initiated by Coppersmith and Winograd which lead to the current best upper bound on the matrix multiplication exponent.

I will report on a recent project [Science 340, 6137] that combines methods from algebraic geometry with a problem that was motivated by theoretical physics, but is at its heart purely tensorial. Indeed, consider a tensor with n indices. There are n ways of associating a matrix with the tensor, by selecting one index and grouping the (n-1) remaining ones together. Each of these matrices comes with a list of singular values. The question now is: What sets of singular values can occur this way and how do they relate to more global properties of the tensor? The problem has applications in quantum mechanics, where every index is associated with a particle and the singular values measure the "degree of uncertainty" ascribed to it. We identify the compatible sets of singular values as a non-abelian moment polytope—an object that is studied in symplectic geometry, asymptotic representation theory, and algebraic geometry. These methods allow us to relate the spectra to the SL-orbit in which the tensor lies. For low-dimensional situations, we can compute the polytopes explicitly and apply them to physical problems.

We begin by describing the ideas behind the state-of-the-art bounds on omega, the exponent of matrix multiplication.

We then present the "group-theoretic" approach of Cohn and Umans as an alternative to these methods, and we generalize this approach from group algebras to general algebras. We identify adjacency algebras of coherent configurations as a promising family of algebras in the generalized framework. We prove a closure property involving symmetric powers of adjacency algebras, which enables us to prove nontrivial bounds on omega using commutative coherent configurations, and suggests that commutative coherent configurations may be sufficient to prove omega = 2.

Along the way, we introduce a relaxation of the notion of tensor rank, called s-rank, and show that upper bounds on the s-rank of the matrix multiplication tensor imply upper bounds on the ordinary rank. In particular, if the "s-rank exponent of matrix multiplication" equals 2, then the (ordinary) exponent of matrix multiplication, omega, equals 2.

Finally, we will mention connections between several conjectures implying omega=2, and variants of the classical sunflower conjecture of Erdos and Rado.

No special background is assumed.

Based on joint works with Noga Alon, Henry Cohn, Bobby Kleinberg, Amir Shpilka, and Balazs Szegedy.

Strassen's conjecture states that computational complexity is additive when the variables are independent. For example, there is no more efficient way to multiply two pairs of matrices than multiply each pair separately.

Strassen's conjecture is now stated in more general terms, using tensors and the notion of tensor rank and it is still open since the 70s.

In this talk, we will discuss some recent progress on the study of Strassen's conjecture. In particular, we will focus on the case of symmetric tensors which correspond to homogeneous polynomials.

The rank of a symmetric form is the length of its shortest decomposition as a sum of pure powers of linear forms, i.e. the shortest smooth apolar scheme.

The cactus rank of the form is the the length of the shortest apolar scheme.

The a-th cactus variety of cubic forms C_{a,n} is the closure of the family of cubic forms of cactus rank a in the projective space of cubic forms in n+1 variables.

Together with Ranestad I shall report on recent work with Jelisiejew and Marques giving the dimension and a geometric characterization of the general member of C_{a,n}, when 1\leq a\leq 2n+2.

The tensor decomposition problem can be seen as a special instance of the reconstruction problem of sum of exponential functions from truncated moment sequences. This sparse representation problem appears in many applications.

We recall an approach due to Prony for solving the problem in the univariate case, and describe an extension to the multivariate case. The method is illustrated on several examples coming from signal processing, magnetic resonance imaging, sparse interpolation, polynomial optimization, When few moments are known, we would like also to be able to find a sparse decomposition.

This problem corresponds to a flat extension property, which reduces either to a rank completion problem on structured matrices or to solving commutation constraints.

We analyze some of its geometric properties, describe some techniques to solve it and present some applications.

Learning mixture of Gaussians has been a classical problem in machine learning and theoretical computer science. Many different approaches were developed, including a line of work starting from [Dasgupta 99] that works for well-separated Gaussians, and an algorithm that does not depend on separation by Moitra and Valiant. However the running time of the latter is exponential in the number of Gaussians. Recently, [Hsu Kakade 13] developed an algorithm based on method of moments that can learn k spherical Gaussians in d dimensions when k<=d, without requiring any separation.

In this talk we show it is possible to learn k Gaussians with general covariance matrices, when the dimension d is at least k^2. This involves new observations on the structure of moment tensors for general Gaussians, and new ways of doing smoothed analysis for the condition number of structured matrices.

Low-rank tensor decompositions are a powerful tool that arise in machine learning, statistics and signal processing. However, tensors pose significant algorithmic challenges and tensors analogs of much of the matrix algebra toolkit are unlikely to exist because of hardness results. For instance, efficient tensor decompositions in the overcomplete case (where rank exceeds dimension) are particularly challenging.

I will introduce a smoothed analysis model for studying tensor decompositions. Smoothed analysis gives an appealing way to analyze non worst-case instances: the assumption here is that the model is not adversarially chosen, formalized by a perturbation of model parameters. We give efficient algorithms for decomposing tensors, even in the highly overcomplete case (rank being polynomial in the dimension) using smoothed analysis. This gives new polynomial time algorithms for learning probabilistic models like mixtures of axis-aligned gaussians and multi-view models even in highly overcomplete settings.

Based on joint work with Aditya Bhaskara, Moses Charikar and Ankur Moitra.