Luca Chiantini,
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?
Wolfgang
Hackbusch, Numerical
Tensor Calculus
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.
Slides
Bernard Mourrain,
From moments to sparse
representations, a geometric, algebraic and algorithmic
viewpoint
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
Giorgio Ottaviani,
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.
Bernd Sturmfels,
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.
Slides
Exercises
Paul Breiding,
Tensor decomposition via
Tensorlab software
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
Exercises
Laetitia Gauvin,
Tensor-based methods for
temporal networks
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.
Fulvio Gesmundo,
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.
Nick
Vannieuwenhoven, Pencil-based
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.
Slides
Emanuele Ventura,
Real rank boundaries and loci of
forms
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.
Slides
Francesco Galuppi,
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.
Nargiz
Kalantarova, On the
spectral structure of Jordan-Kronecker products of symmetric and
skew-symmetric matrices
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.
Filip Rupniewski,
Strassens additivity
problem
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.
Aurélien Sagnier,
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 [4], 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 [2]. 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) [1]. 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
[2], first proved in [4]. Our main motivations are applications to
Projected Entangled Pair States (PEPS) [3]. 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.
References:
[1] M. Michalek and Y. Shitov. In progress, 2018.
[2] D. Perez-Garcia, F. Verstraete, M.M. Wolf, and J.I. Cirac.
Matrix product state representations. Quantum Inf. Comput.,
7(56):401430, 2007.
[3] 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.
[4] 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.
Daniele Taufer,
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.
Slides
Markus Wageringel,
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).