- Stefano Massei (École Polytechnique Fédérale Lausanne)
Exploiting off-diagonal rank structures in the solution of linear matrix equations
Linear matrix equations, namely Sylvester and Lyapunov equations, play an important role in several applications arising in control theory and PDEs. In the large scale scenario, it is crucial to exploit the structure in the data in order to carry on the computations and store the final solution. We focus on the case in which the coefficients have off-diagonal blocks with low-rank and we study when this property is numerically preserved in the solution. Then, we propose a divide and conquer scheme able to exploit the structure, reaching a linear-polylogarithmic complexity in both time and memory consumption.
- José Henrique de Morais Goulart (GIPSA-lab, CNRS, Grenoble)
On minimal ranks and the approximate block-term tensor decomposition
The block-term tensor decomposition (BTD) is a generalization of the tensor rank (or canonical polyadic) decomposition which is well suited for certain source separation problems. In this talk, I will discuss the existence of a best approximate block-term tensor decomposition (BTD) consisting of a sum of low-rank matrix-vector tensor products. This investigation is motivated by the fact that a tensor might not admit an exact BTD with a given structure (number of blocks and their ranks).
After a brief introduction, we will proceed by exploring the isomorphism between third-order tensors and matrix polynomials. To every matrix polynomial one can associate a sequence of minimal ranks, which is unique up to permutation and invariant under the action of the general linear (or tensor equivalence) group. This notion is a key ingredient of our problem, since it induces a natural hierarchy of sets of third-order tensors corresponding to different choices of ranks for the blocks of the BTD.
In the particular case of matrix pencils, I will explain how the minimal ranks of a pencil can be directly determined from its Kronecker canonical form. By relying on this result, one can show that no real pencil of dimensions 2k x 2k having full minimal ranks admits a best approximation on the set of real pencils whose minimal ranks are bounded by 2k-1. From the tensor viewpoint, this means that there exist third-order tensors which do not have a best approximation on a certain set of two-block BTDs. These tensors form a non-empty open subset of the space of 2k x 2k x 2 tensors, which is therefore of positive volume. I shall sketch the proof of this result and then discuss some possible extensions of this work and open problems.
- Bernard Mourrain (Inria Sophia-Antipolis)
Tensor decomposition and structured matrices
Tensor decomposition problems appear in many areas such as Signal Processing, Quantum Information Theory, Algebraic Statistics, Biology, Complexity Analysis, … as a way to recover hidden structures from data. The decomposition is a representation of the tensor as a weighted sum of a minimal number of terms, which are tensor products of vectors. We present an algebraic approach to address this problem, which involves duality, Gorenstein Artinian algebras and Hankel operators. We show the connection with low rank decomposition of Hankel matrices, discuss algebraic and optimization techniques to solve it and illustrate the methods on some examples.
- Françoise Tisseur (University of Manchester)
Structured matrix polynomials and their sign characteristics: classical results and recent developments
The sign characteristic is an invariant associated with particular eigenvalues of structured matrices, matrix pencils, or matrix polynomials. The concept of sign characteristic arises in different forms in many scientific fields, and is essential for the stability analysis in Hamiltonian systems or the perturbation behaviour of eigenvalues under structured perturbations. We will start by discussing the sign characteristics of Hermitian matrix polynomials, and show how to extend its definition to eigenvalues at infinity. We will discuss applications of the sign characteristic in particular in control systems, in the solution of structured inverse polynomial eigenvalue problems and in the characterization of special structured matrix polynomials such as overdamped quadratics, hyperbolic and quasidefinite matrix polynomials.
- Lloyd N. Trefethen (University of Oxford and LIP - ENS de Lyon)
Axis-alignment in low rank and other structures
In two or more dimensions, various methods have been developed to represent matrices or functions more compactly. The efficacy of such methods often depends on alignment of the data with the axes. We shall discuss four cases: low-rank approximations, sparse grids, quasi-Monte Carlo, and multivariate polynomials.