On the minimal ranks of matrix pencils and the existence of a best approximate block-term tensor decomposition

José Henrique de Morais Goulart, Pierre Comon

TL;DR

This paper introduces the concept of "minimal ranks" for matrix pencils to study the mathematical properties of Block-Term Tensor Decompositions (BTD). The authors prove a striking negative result: for certain real tensors, finding a best approximate BTD is an fundamentally ill-posed problem. Crucially, unlike previous edge-case examples of tensor ill-posedness, this impossibility occurs over a positive-volume set of tensors, meaning you could randomly encounter this issue in practice.

What Problem Does This Paper Address?

In linear algebra, the Eckart-Young-Mirsky theorem guarantees that every matrix has a "best" low-rank approximation, which we can easily find using the Singular Value Decomposition (SVD). However, when we move to higher-order arrays (tensors), this guarantee breaks down. It is a known, frustrating phenomenon that a tensor might not have a best low-rank approximation—you can get infinitely close to the target tensor with a sequence of low-rank tensors, but the limit of that sequence jumps to a higher rank.

This paper investigates whether this ill-posedness also plagues a specific, highly useful type of tensor factorization called the Block-Term Decomposition (BTD), which decomposes a tensor into a sum of matrix-vector tensor products. To tackle this, the authors look at $m \times n \times 2$ tensors, which can be mathematically represented as matrix pencils (polynomials of the form $A + \lambda B$). The core question is: if we classify these pencils by their intrinsic complexity (their "minimal ranks"), is the set of lower-complexity pencils topologically closed? If it isn't, best approximations don't exist.

Methods

The authors approach the problem through the lens of algebraic geometry and matrix theory:

  1. Defining Minimal Ranks: They formalize the "minimal ranks" $\rho(A,B) = (r,s)$ of a matrix pencil under the action of the general linear group. This provides a natural hierarchy of complexity that is complementary to standard tensor rank.
  2. Kronecker Canonical Forms: They leverage the Kronecker-Weierstrass theory of matrix pencils. By breaking a pencil down into its Kronecker canonical form (which isolates its regular and singular parts), they derive a direct method to compute its minimal ranks.
  3. Topological Analysis: To prove ill-posedness, they analyze the norm topology of the space of real pencils. They construct sequences of pencils with lower minimal ranks that converge to a pencil with higher minimal ranks, proving that the set of lower-rank pencils is not closed.
  4. Generalization: They extend the definition of minimal ranks from matrix pencils (degree-1 polynomials) to matrix polynomials of arbitrary finite degree, which correspond to $m \times n \times d$ tensors.

Datasets

Not discussed in the paper. This is a purely theoretical mathematical paper, so no empirical datasets or benchmarks were used.

Key Insights and Ideas

  • Minimal Ranks vs. Tensor Rank: The tensor rank of a pencil quantifies the minimal number of rank-one matrices needed to express it. Minimal ranks, however, quantify the minimal ranks of the actual matrices $A'$ and $B'$ in any equivalent pencil $A' + \lambda B'$. Two pencils can have the same tensor rank but different minimal ranks, making minimal ranks a distinct and powerful tool for characterizing tensor complexity.
  • Kronecker Forms are the Key: You don't need to guess or run an optimization algorithm to find the minimal ranks of a pencil. The authors prove that the minimal ranks can be deterministically calculated by looking at the sizes of the blocks and elementary divisors in the pencil's Kronecker canonical form.
  • Positive-Volume Ill-Posedness: It was already known that some tensors lack a best approximate BTD. However, previous examples were isolated edge cases. The biggest "aha" moment of this paper is the proof that for real tensors, this non-existence happens over an open set (a positive-volume set). If you are working with real $2k \times 2k \times 2$ tensors, there is a non-zero probability that a randomly drawn tensor simply will not have a best approximation of a specific lower BTD structure.

Key Results

  • Exact Computation Formula: The authors provide a concrete theorem (Theorem 13) that exactly computes the minimal ranks of any $m \times n$ pencil based on the minimal indices of its singular part and the elementary divisors of its regular part.
  • Complete Classification for Small Dimensions: Using their new framework, they provide a complete classification of the orbits of all real $m \times n$ pencils for dimensions up to $4 \times 4$ based on their minimal ranks.
  • The Impossibility Theorem: They rigorously prove that the set of real $2k \times 2k$ pencils with minimal ranks bounded by $2k-1$ is not closed in the norm topology. Consequently, any regular $2k \times 2k$ pencil with only complex-valued eigenvalues (which form an open, positive-volume set) does not admit a best approximation among pencils with strictly lower minimal ranks.

Limitations and Future Work

  • Focus on $d=2$: The most concrete results, including the Kronecker canonical form computations and the classification tables, are restricted to matrix pencils (which correspond to tensors with a 3rd dimension of exactly 2).
  • Future Work: While the authors successfully define minimal ranks for arbitrary matrix polynomials (corresponding to $m \times n \times d$ tensors), they note that finding a way to easily compute these minimal ranks for $d > 2$ remains an open challenge. Developing tools to compute the minimal ranks of general matrix polynomials would be highly valuable for the broader study of third-order block-term decompositions.

Summary updated

Abstract

Under the action of the general linear group with tensor structure, the ranks of matrices $A$ and $B$ forming an $m \times n$ pencil $A + \lambda B$ can change, but in a restricted manner. Specifically, with every pencil one can associate a pair of minimal ranks, which is unique up to a permutation. This notion can be defined for matrix pencils and, more generally, also for matrix polynomials of arbitrary degree. In this paper, we provide a formal definition of the minimal ranks, discuss its properties and the natural hierarchy it induces in a pencil space. Then, we show how the minimal ranks of a pencil can be determined from its Kronecker canonical form. For illustration, we classify the orbits according to their minimal ranks (under the action of the general linear group) in the case of real pencils with $m, n \le 4$. Subsequently, we show that real regular $2k \times 2k$ pencils having only complex-valued eigenvalues, which form an open positive-volume set, do not admit a best approximation (in the norm topology) on the set of real pencils whose minimal ranks are bounded by $2k-1$. Our results can be interpreted from a tensor viewpoint, where the minimal ranks of a degree-$(d-1)$ matrix polynomial characterize the minimal ranks of matrices constituting a block-term decomposition of an $m \times n \times d$ tensor into a sum of matrix-vector tensor products.
BibTeX
@inproceedings{goulart2018minimal,
  author = {José Henrique de Morais Goulart and Pierre Comon},
  title = {{On the minimal ranks of matrix pencils and the existence of a best approximate block-term tensor decomposition}},
  booktitle = {Linear},
  year = {2018},
  doi = {10.1016/j.laa.2018.09.031},
}
Figure