On the geometry of the
decompositions of tensors
In general, a decomposition of a given tensor T can be seen, from a geometrical point of view, as a discrete set of points in a projective variety (e.g. a Veronese variety, if one considers Waring decompositions of symmetric tensors). Thus, we can apply methods for the study of finite sets in projective or multiprojective spaces, in order to determine properties of the tensor T and its decompositions. In this optic, I will discuss recent applications of Algebraic Geometry to the analysis of tensors. I will also point out how, on the other hand, problems coming from tensor analysis suggest some new field of investigation in the Geometry of finite subsets of projective spaces. The main focus of the lectures concerns the analysis of the following question: assume we are given a specific decomposition of a specific tensor T. How can we determine if the decomposition is minimal, or unique?
The key to a numerical approach of tensors are suitable sparse representations. The classical representations (canonical, Tucker) will be mentioned and discussed. Here closedness properties are very important. The main topic is the hierarchical representation, which can be considered as a recursive generalisation of the Tucker format. Since we are interested in approximating multivariate functions, also infinite-dimensional tensors spaces are of interest. The corresponding discussion requires tools from functional analysis. The closedness of the hierarchical format also holds in the infinite-dimensional case as shown by means of the minimal subspaces. The numerical treatment of tensors includes the tensor operations. Various operations within the hierarchical format will be discussed.
Literature: W. Hackbusch, Tensor Spaces and Numerical Tensor Calculus. Springer 2012.
From moments to sparse
representations, a geometric, algebraic and algorithmic
The lecture will focus on the problem of finding sparse representations of functions from sequences of moments. This problem appears in many contexts, such as tensor decomposition, measure recovery from Fourier analysis, error decoding, etc. and has many applications. From a mathematical perspective, this raises the question of extending the concept of rank to non-linear algebra. After illustrating in several examples where this problem occurs, we will present an algebraic point of view to address it. Properties of apolarity, Catalecticant and Hankel operators will be detailed. We will show how duality on polynomials, properties of Artinian algebras and their dual can be used to find effectively such sparse representations. Examples of computation of low rank representations will be developed. Related algorithms will be analyzed. A classification of low rank symmetric tensors will be presented, based on these results. Finally, we will study higher rank decomposition problems and show their connection with structured matrix completion problems and flat extension properties. This will provide us a glimpse on the geometry of varieties of tensors of bounded rank.
Slides: Thursday Friday
Click here for a description of the tools that will be used and some material.
POEMA ITN network PhD positions
Spectral Theory of Tensors.
Results and problems by a geometric perspective.
Real tensor spaces are endowed with a natural scalar product induced by scalar products on each factor. This leads to best rank r-approximation of tensors, which is well understood only in the case r = 1. Even this special case shows several interesting features that we discuss, with similarities and differences with the basic case of matrices, where it reduces to the theory of eigenvectors and singular pairs. On the algebraic side, this setting leads to the Euclidean Distance degree (EDdegree) developed with Draisma, Horobet, Sturmfels and Thomas. We show its duality property and its geometrical meaning. Applications include offset surfaces and computer vision.
Varieties of Signature Tensors
The signature of a parametric curve is a sequence of tensors whose entries are iterated integrals. This construction is central to the theory of rough paths in stochastic analysis. In these lectures we offer a first introduction to this theory, as seen through the lens of algebraic geometry and tensor calculus. We discuss varieties of signature tensors for piecewise linear paths and on polynomial paths. These all live in universal varieties that are derived from free Lie algebras and their Lie groups. Our presentation is based on a joint article with Carlos Amendola and Peter Friz, but we shall also discuss ongoing work by other authors as well as open problems.
Slides: Monday Tuesday
Elena Angelini, Tensor
decomposition via Bertini software
Bertini is a software for Numerical Algebraic Geometry, created for solving polynomial systems (https://bertini.nd.edu/). After discussing about the meaning of solving polynomial equations, we introduce the key idea of homotopy continuation, on which Bertini is based. Then we describe a computational technique, related to homotopy continuation and monodromy loops, that can be implemented in Bertini and Matlab, for numerically decomposing tensors over the complex and real field. In particular, we focus on the classical and simultaneous Waring setting.
Tensor decomposition via
Tensorlab is a MATLAB toolbox for computing decompositions of tensors. It is actively developed and maintained at KU Leuven by Vervliet, Debals, Sorber, Van Barel and De Lathauwer. In this session I will explain how to use Tensorlab to compute the canonical polyadic decomposition, the multilinear singular value decomposition and the block term decomposition of a tensor. I will also show how to compute those decomposition with structured output (e.g., imposing non-negativity). Furthermore, I will discuss numerical issues.
Paul's introduction to Tensorlab page
Paul's github Tensorlab page
Tensor-based methods for
In this talk I will describe machine learning techniques based on tensor factorization to study temporal networks such as contact networks. Temporal networks are highly relevant in many fields of science, as they can be used to represent a great variety of systems in nature such as communication, social, infrastructural or neural networks. Considering the temporal dimension of these networks allows us to understand better and predict complex phenomena, by taking into account both the fact that the network edges are not continuously active and the potential relation between the spatial and temporal dimensions. A fundamental challenge in this area is the definition of mathematical models and tools apt to capture topological and dynamical characteristics and to reproduce properties observed on the real dynamics of networks.
I will here present techniques we have developed based on tensor factorization, that detect groups of links in networks that have correlated activities. I will first focus on the analysis of the topological structures that characterize time-varying networks, such as network communities (densely connected group of nodes). In particular, I will show how we can use tensor factorization to detect anomalies in temporal networks. I will then present a study on the interplay between the structures of time-varying networks and the dynamic processes unfolding over them, using the specific case of disease spreading. I will finally extend the framework of standard tensor factorization to infer missing data from a partial dataset and show how it enables us to reproduce the output of a dynamical process on the full temporal network.
Tensors with symmetries and the
complexity of matrix multiplication
The exponent of matrix multiplication omega is a fundamental constant that governs the complexity of several problems in computational linear algebra and it can be defined geometrically as the exponent of the asymptotic rate of growth of the tensor rank of the matrix multiplication tensor. Classically, it was known that omega is at most 3; in 1969, V. Strassen found an algorithm for 2x2 matrix multiplication which provided an upper bound of 2.81 on omega, starting a line of research which in the last 50 years lowered this upper bound up to the current omega < 2.372864. Today, it is conjectured that omega =2. Essentially all the improvements on upper bounds for the exponent since 1989 were based on the so-called “Strassen’s laser method” and the “Coppersmith-Winograd tensor” which relies on a geometric construction which ”extract” copies of the matrix multiplication tensor from copies of another tensor, the Coppersmith-Winograd tensor. A recent result by Ambainis-Filimus-LeGall showed that this method cannot improve the upper bounds on the exponent beyond 2.3. In this seminar, I will explain Strassen’s laser method and will present some recent work with Conner, Landsberg and Ventura in which we study geometric properties of isotropy groups of tensors aiming to determine tensors which can potentially be used in the laser method.
algorithms for tensor rank decomposition are unstable
We prove the existence of an open set of m x n x p tensors of rank r on which a popular and efficient class of algorithms for computing tensor rank decompositions based on a reduction to a linear matrix pencil, typically followed by a generalized eigendecomposition, is arbitrarily numerically forward unstable. Our analysis shows that this problem is caused by the fact that the condition number of the tensor rank decomposition can be much larger for m x n x 2 tensors than for the m x n x p input tensor. Moreover, we present a lower bound for the limiting distribution of the condition number of random tensor rank decompositions of third-order tensors. The numerical experiments illustrate that for random tensor rank decompositions one should anticipate a loss of precision of a few digits. This is joint work with C. Beltr´an and P. Breiding.
Real rank boundaries and loci of
Recently, classical geometric questions have been revitalized in the framework of ranks with respect to arbitrary projective varieties (tensor ranks being those with respect to Segre varieties). In this talk, we study ranks with respect to special embeddings of a smooth quadric and their forbidden loci. Some typical ranks for those varieties are derived, employing a characterization of real varieties of minimal degree due to Blekherman, Smith, and Velasco. Finally, we partially describe their real rank boundaries using maps arising from classical catalecticants.
The Rough Veronese Variety
Signature tensors of paths were born in the realm of stochastics, but they play a role in other branches of mathematics. There are interactions with non-commutative algebra, and of course with analysis, where they became central in the theory of rough paths. However, there is yet another interesting viewpoint. The signatures of a given class of paths parametrize an algebraic variety inside the space of tensors. The study of these signature varieties brings geometry into play, and provides both new tools to investigate paths and new challenging questions about their behavior. One important class of paths is given by rough paths. Their signature variety shows surprising analogies with the Veronese variety, and our aim is to give a full geometric description of this so-called Rough Veronese.
Kalantarova, On the
spectral structure of Jordan-Kronecker products of symmetric and
Kronecker products as well as interlacing properties are very commonly used in matrix theory, operator theory and in their applications. We address conjectures formulated by Tuncel and Wolkowicz in 2003, involving certain interlacing properties of eigenvalues of the JordanKronecker product for pairs of symmetric matrices A and B. We disprove these conjectures in general, but we also identify some special cases where the conjectures hold. In particular, we prove that for every pair of symmetric matrices (and skew-symmetric matrices) with one of them at most rank two, the odd spectrum (those eigenvalues determined by skew-symmetric eigenvectors) of their Jordan-Kronecker product interlace its even spectrum (those eigenvalues determined by symmetric eigenvectors). Moreover, we introduce Lie-Kronecker products and characterize their eigenvector/eigenvalue structure for symmetric and skew-symmetric matrices.
In 2017, Y. Shitov proved existence of the counter example for the Strassen's conjecture. This talk is about a joint work with J. Buczyński and E. Postinghel, where we investigate when the statement of Strassen's additivity conjecture holds. To be more precise: suppose A = A'⊕A'', B = B'⊕B'', and C = C'⊕C'', where all A', A'', ..., C'' are finitely dimensional vector spaces over complex numbers. Let p = p' + p'', where p' ∈ A'⊗B'⊗C' and p'' ∈ A''⊗B''⊗C''. What are dimensions of A', A'', ..., C'' such that we have the additivity of the ranks: R(p) = R(p') + R(p'') ? I will show conditions for tensors when the mentioned additivity of ranks holds.
Tropical tensor products
Tensors products of modules over semifields of characteristic one, like the Boolean or tropical semifields, have appeared recently, with motivations from arithmetics, in work by Connes and Consani (in their attemps to build an intersection theory for arithmetic and scaling sites (spaces they have built and which are close related to the zeroes of the Riemann zeta function); this intersection theory would be one important ingredient in their long-term approach to the Riemann hypothesis). Algebraic and topological tropical tensors products were constructed in a different way by Litvinov and collaborators: here, tropical tensors are sums of ”rank one” expressions, similar to the ones used in the approximation of large data sets or of functions of many parameters. We show, in a perhaps surprising way, that the canonical notion of tropical tensor product, defined in terms of the usual universal problem, differs from the definition arising from approximation theory, but that the latter can be recovered from the former by a certain ”reduction” operation. We illustrate these results by computing several basic examples of categorical tensors products, including spaces of convex sets and functions.
Tim Seynnaeve, A
higher dimensional version of the quantum Wielandt theorem
In , Sanz, Perez-Garcia, Wolf and Cirac proved a quantum version of the Wielandt inequality. This theorem was motivated by the study of Matrix Product States and conjectures stated in . It can be stated as follows. Let L be a linear space of D × D-matrices, and let L^k be the linear space spanned by all products of exactly k matrices in L. There is a constant C(D), only depending on D, such that if dim(L^k ) = D^2 for some k, then it also holds for all k ≤ C(D). Moreover, C(D) = O(D^4 ). The bound on C(D) was recently improved to O(D^2 log D) . The bounds were obtained using explicit methods from linear algebra. In this talk we discuss a generalization of the quantum Wielandt theorem, where the matrices are replaced by tensors on an n-dimensional grid. Our main new insight is the application of nonconstructive Noetherian arguments from non-linear algebra. For matrix product states, this gives an easy proof of Conjecture 1 in , first proved in . Our main motivations are applications to Projected Entangled Pair States (PEPS) . These are higher dimensional versions of Matrix Product States, for which none of the above bounds were known. This talk is based on work in progress with Frank Verstraete and Mateusz Michalek.
 M. Michalek and Y. Shitov. In progress, 2018.
 D. Perez-Garcia, F. Verstraete, M.M. Wolf, and J.I. Cirac. Matrix product state representations. Quantum Inf. Comput., 7(56):401430, 2007.
 D. Perez-Garcia, F. Verstraete, M.M. Wolf, and J.I. Cirac. Peps as unique ground states of local hamiltonians. Quantum Inf. Comput., 8(6-7):650663, 2008.
 M. Sanz, D. Perez-Garcia, M.M. Wolf, and J.I. Cirac, A quantum version of wielandts inequality. IEEE Transactions on Information Theory, 56(9):46684673, 2010.
A refinement of the symmetric
tensor decomposition algorithm
The most complete theoretical algorithm known for decomposing symmetric tensors as a sum of rank-1 symmetric tensors was devised by Brachat, Comon, Mourrain and Tsigaridas in 2010. It reformulates and solves the problem from a dual point of view by exploiting some properties of the Hankel matrices. We propose a slight variation of it in order to solve certain issues remained open. We also point out how to provide with the same algorithm the additional information about the cactus rank of the given polynomial and we present a way to fully recover the apolar scheme computing the cactus rank in certain particular cases.
Moment ideals of local mixtures
We study a special case of finite mixture models, the Dirac local mixtures, from an algebraic and geometric point of view, highlighting connections to algebraic statistics, symmetric tensor decomposition and signal processing. We focus on the moment varieties of first order local mixtures, providing generators for the ideals and showing a connection to moment ideals of Pareto distributions. Further, we consider mixture models of these distributions and investigate the problem of recovering the parameters of such a distribution from its moments. This is joint work with Alexandros Grosdos Koutsoumpelias (Osnabrück University).