This paper, published in 2018, provides a significant theoretical bridge between classical matrix theory and the burgeoning field of multilinear algebra (tensor analysis). It addresses a specific technical gap in how we define "P-tensors"—a class of tensors that are essential for solving complex optimization problems.
TL;DR
The authors introduce a new, "homogeneous" definition for P-tensors and $P_0$-tensors that works for both even and odd orders, fixing a major deficiency in previous definitions. They prove that this new class of tensors encompasses many important structures (like Laplacian and M-tensors) and guarantees that the Tensor Complementarity Problem (TCP) has a well-behaved solution set.
What Problem Does This Paper Address?
In matrix theory, P-matrices are those where all principal minors are positive. They are famous because they guarantee that a "Linear Complementarity Problem" (a type of optimization problem used in economics and engineering) has a unique solution.
As researchers moved from matrices (2D arrays) to tensors (multi-dimensional arrays), they tried to generalize this concept. However, previous definitions of "P-tensors" had a glaring flaw: they didn't work for tensors of odd order (e.g., a 3x3x3 tensor). Under the old rules, no odd-order P-tensors could exist. This paper aims to fix that "odd-order gap" by proposing a definition that is mathematically consistent regardless of the tensor's dimensions or order.
Methods
The authors employ a homogeneous formula to redefine P-tensors.
Specifically, while previous definitions looked at the sign of the product $x_i(Ax^{m-1})_i$, this paper proposes looking at $x_i^{m-1}(Ax^{m-1})_i$. By raising the $x_i$ term to the power of $m-1$ (where $m$ is the order of the tensor), they ensure the formula behaves predictably whether $m$ is even or odd.
The paper is primarily a theoretical proof-based work. The authors use tools from:
- Spectral Theory of Tensors: Analyzing H-eigenvalues (real eigenvalues).
- Complementarity Theory: Using fixed-point theorems and degree theory to analyze solution sets.
- Structured Tensor Analysis: Testing their definition against known classes like M-tensors, H-tensors, and Cauchy tensors.
Datasets
Not discussed in the paper. As a theoretical mathematics paper, it relies on formal proofs and counterexamples rather than empirical datasets or benchmarks.
Key Insights and Ideas
- The Homogeneity Fix: The simple act of changing the exponent in the definition allows P-tensors to exist in odd orders. This isn't just a neat trick; it allows the theory of tensors to align more closely with the behavior of multivariate polynomials.
- Spectral Characterization: A P-tensor (under this new definition) is shown to have no non-positive H-eigenvalues. This provides a bridge between the algebraic structure of the tensor and its geometric/spectral properties.
- Unification of Classes: The authors show that their definition is "broad" enough to include many important structured tensors, such as:
- Nonsingular M-tensors (important in probability and physics).
- Laplacian tensors of uniform hypergraphs (crucial for network science).
- Strictly diagonally dominant tensors.
- Counterpart to PSD: For odd-order tensors, $P_0$-tensors can be viewed as the natural extension of Positive Semidefinite (PSD) tensors, which are usually only defined for even orders.
Key Results
- TCP Solvability: The most significant application is the Tensor Complementarity Problem (TCP). The authors prove that if a tensor $A$ is a P-tensor, the TCP is guaranteed to have a solution set that is both non-empty and compact.
- Inheritance: They prove that every principal subtensor of a P-tensor is also a P-tensor, maintaining consistency with matrix theory.
- Topological Properties: They demonstrate that the set of $P_0$-tensors is the "closure" of the set of P-tensors, meaning you can approximate any $P_0$-tensor with a sequence of P-tensors.
Limitations and Future Work
- Uniqueness: Unlike the matrix case (where P-matrices guarantee a unique solution), P-tensors only guarantee that a solution exists and is bounded. The solutions are not necessarily unique, which remains a challenge for certain optimization algorithms.
- Non-Convexity: The authors acknowledge that the set (cone) of $P_0$-tensors is not convex. This makes certain types of global optimization more difficult.
- Computational Complexity: While the paper defines these tensors, checking if a general tensor is a P-tensor is likely NP-hard (though the authors don't explicitly prove the complexity class here, it is a known trait of similar tensor properties). Future work could involve finding more "easily checkable" sufficient conditions for the P-property.
Summary updated