Identifiability of an X-Rank Decomposition of Polynomial Maps

Pierre Comon, Yang Qi, Konstantin Usevich

TL;DR

This paper introduces the concept of "X-rank decomposition" as a powerful generalization of tensor decomposition, enabling a deeper understanding of polynomial map representations. The authors establish new theoretical results on the identifiability (uniqueness) of these decompositions, particularly for non-homogeneous polynomial maps, which are crucial in fields like system identification and signal processing.

What Problem Does This Paper Address?

Many real-world problems in system identification, signal processing, and machine learning involve modeling complex systems using multivariate polynomial maps. A common approach is to decompose these maps into a sum of simpler, "decoupled" representations. This paper focuses on a specific type of decomposition, $f(u) = \sum_{i=1}^r w_i g_i(v_i^T u)$, where $f$ is the polynomial map, $w_i$ are vectors, $g_i$ are univariate polynomials, and $v_i$ are vectors. The core questions are: when is this decomposition unique (identifiable)? What is the maximum number of terms ($r$) needed to represent any polynomial map of a certain degree? And what is the typical number of terms for a "random" map? While these questions have been studied for homogeneous polynomials, the non-homogeneous case, which is more general and practical, remains less understood.

Methods

The paper's central contribution is framing the polynomial decomposition problem within the novel concept of "X-rank decomposition." X-rank generalizes various existing notions of rank (matrix, tensor, symmetric tensor) by considering the rank with respect to a specific algebraic variety. This geometric perspective allows the authors to leverage tools from algebraic geometry to analyze the identifiability and rank properties of polynomial maps. They introduce and analyze Veronese and Segre-Veronese varieties, which are directly related to these polynomial decompositions. The proofs rely heavily on concepts like Zariski closure, generic properties, secant varieties, and defectivity of varieties.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • X-rank as a Unifying Framework: The paper elegantly shows how various polynomial decomposition problems (like Waring decomposition for homogeneous polynomials) are special cases of X-rank decomposition. This provides a unified theoretical lens.
  • Geometric Interpretation of Identifiability: By connecting polynomial decomposition to algebraic varieties, the authors translate the problem of uniqueness into geometric properties like the dimension and defectivity of secant varieties.
  • New Bounds for Non-Homogeneous Polynomials: The paper derives new, tighter bounds on the identifiability of polynomial maps, particularly for the more general non-homogeneous case, improving upon existing results.
  • Veronese Scrolls as Key Structures: The analysis highlights the importance of Veronese scrolls (a generalization of rational normal scrolls) in understanding the structure and identifiability of these polynomial decompositions.

Key Results

  • The paper establishes new results on the identifiability (uniqueness) of polynomial decompositions, providing conditions under which a decomposition is unique up to permutation of terms.
  • New bounds are derived for the maximum rank ($r$) required for decomposition, which are shown to be better than previous bounds, especially for certain parameter ranges.
  • The paper analyzes the generic rank of Veronese scrolls, providing insights into the typical number of terms needed for decomposition.
  • Specific examples and tables are provided to illustrate the derived bounds and compare them with existing results, particularly for cases with $d=3$ and $d=4$.

Limitations and Future Work

The paper focuses on theoretical aspects and does not develop decomposition algorithms, although it suggests that the insights gained might lead to new algorithmic approaches. The authors acknowledge that for certain specific cases (e.g., specific values of $m$ and $d$ for Veronese varieties), the identifiability bounds might not be tight. Future work could involve exploring these tighter bounds and developing practical algorithms based on the X-rank framework. The paper also notes that for Segre-Veronese varieties, explicit results on identifiability are not readily available, suggesting this as an area for further research.

Summary updated

Abstract

In this paper, we study a polynomial decomposition model that arises in problems of system identification, signal processing and machine learning. We show that this decomposition is a special case of the X-rank decomposition --- a powerful novel concept in algebraic geometry that generalizes the tensor CP decomposition. We prove new results on generic/maximal rank and on identifiability of a particular polynomial decomposition model. In the paper, we try to make results and basic tools accessible for general audience (assuming no knowledge of algebraic geometry or its prerequisites).
BibTeX
@article{comon2017identifiability,
  author = {Pierre Comon and Yang Qi and Konstantin Usevich},
  title = {{Identifiability of an X-Rank Decomposition of Polynomial Maps}},
  journal = {SIAM J. Appl. Algebra Geom},
  year = {2017},
  doi = {10.1137/16m1108388},
}
Figure