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:
- 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.
- 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.
- 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.
- 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