⚡ electrical engineering

Data-Driven Tensor Decomposition Identification of Homogeneous Polynomial Dynamical Systems

This paper proposes a data-driven framework that leverages low-rank tensor decompositions to efficiently identify homogeneous polynomial dynamical systems from time-series data by directly learning compact factor structures, thereby overcoming the curse of dimensionality while ensuring accuracy and robustness against noise.

Original authors: Xin Mao, Joshua Pickard, Can Chen

Published 2026-04-07

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Xin Mao, Joshua Pickard, Can Chen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to understand how a complex ecosystem works. Maybe it's a forest with thousands of trees, or a city with millions of people, or a swarm of drones flying together. In these systems, things don't just react to one neighbor; they react to groups. A tree might grow differently if three specific neighbors are present, not just one.

In math, we call these "Homogeneous Polynomial Dynamical Systems" (HPDSs). They are powerful tools for modeling these complex, group-based interactions. But here's the problem: They are incredibly hard to figure out.

The Problem: The "Library of Babel"

Imagine trying to write down the rules for how every single tree in a forest interacts with every other tree. If you have 10 trees, the list of rules is manageable. But if you have 1,000 trees, the number of possible interactions explodes. It's like trying to read every book in a library that grows so fast it fills the universe before you can finish the first shelf.

This is the "Curse of Dimensionality." Traditional methods try to write down every single rule (every number in a giant mathematical table called a "tensor"). For large systems, this table is so huge that your computer runs out of memory, or it takes longer than the age of the universe to calculate.

The Solution: The "Lego" Approach

The authors of this paper, Xin Mao, Joshua Pickard, and Can Chen, came up with a clever trick. Instead of trying to write down the entire giant library of rules, they realized that most real-world systems have hidden patterns. They aren't random chaos; they are built from simpler, repeating blocks.

They used Tensor Decomposition. Think of this like taking a giant, complex Lego castle apart. Instead of trying to describe the whole castle as one massive, unbreakable block, you realize it's actually built from just a few types of small Lego bricks arranged in a specific way.

They used three different ways to break the system down into these "bricks":

Tensor Train (TT): Like a train of cars, where each car connects to the next.
Hierarchical Tucker (HT): Like a family tree, grouping relatives together before connecting to the main trunk.
Canonical Polyadic (CP): Like a stack of transparent sheets, where the whole image is just the sum of a few simple layers.

How It Works: The "Guess and Check" Game

The paper proposes a method to find these "bricks" (the factors) directly from data, without ever trying to build the giant, impossible castle first.

The Data: You watch the system over time (like recording the movement of the drones).
The Guess: You start with a random guess of what the "bricks" look like.
The Refinement (ALS): This is the magic step. The algorithm uses a technique called Alternating Least Squares.
- Imagine you are trying to solve a giant jigsaw puzzle, but the pieces are moving.
- The algorithm says: "Okay, let's freeze all the pieces except this one. Now, what is the perfect shape for this single piece to make the picture fit?"
- It solves that easy math problem, fixes that piece, and then moves to the next piece.
- It goes back and forth, piece by piece, getting closer to the perfect picture every time.

Because it only solves for one small "brick" at a time, the math is easy and fast. It never has to hold the whole giant library in its head at once.

Why This Matters

Speed: It turns a problem that would take a supercomputer years to solve into one that a laptop can solve in minutes.
Accuracy: Even if the data is noisy (like a blurry photo or a shaky video), this method is very good at finding the true underlying rules. It acts like a smart filter that ignores the static.
Scalability: It works for small systems and massive ones (like a city-wide traffic grid or a global climate model) without breaking a sweat.

The Big Picture

Think of this paper as a new way to learn the rules of a complex game. Instead of trying to memorize every possible move in the game (which is impossible), the authors teach us how to identify the basic moves and how they combine.

By breaking complex systems down into their fundamental, low-rank components, they allow scientists and engineers to model, predict, and control the world's most complex networks—from the spread of diseases to the behavior of robot swarms—using data we can actually collect.

1. Problem Statement

The paper addresses the challenge of System Identification (SI) for Homogeneous Polynomial Dynamical Systems (HPDSs). HPDSs are used to model complex networked systems with higher-order interactions, such as ecological networks, chemical reactions, and multi-agent robotics.

The Core Challenge: Traditional SI methods for HPDSs require estimating a "dynamic tensor" $A$ that governs the system dynamics ( $\dot{x} = Ax^{k-1}$ ). The number of parameters in this tensor grows combinatorially (exponentially) with the system dimension ( $n$ ) and the polynomial degree ( $k$ ).
Consequences: This "curse of dimensionality" leads to:
- Computational intractability for high-dimensional systems.
- Severe overfitting when data is limited.
- Inability to scale to real-world large-scale networks.
Goal: Develop a scalable, data-driven framework to identify HPDSs from time-series data without reconstructing the full high-dimensional tensor, leveraging the intrinsic low-rank structure of many real-world systems.

2. Methodology

The authors propose a Data-Driven Tensor Decomposition Identification Framework. Instead of estimating the full tensor $A$ , the method assumes $A$ admits a low-rank tensor decomposition and directly learns the underlying factor tensors/matrices from data.

A. Mathematical Formulation

The system dynamics are modeled as:
$\dot{x}(t) = A x(t)^{k-1}$
where $A \in \mathbb{R}^{n \times \dots \times n}$ is an almost symmetric $k$ -th order tensor. The identification problem is formulated as a nonlinear least-squares optimization using observed state trajectories ( $X_0$ ) and their derivatives ( $X_1$ ):
$\min \left\| X_1 - \hat{X}_1 \right\|_F^2$

B. Low-Rank Decomposition Strategies

The paper investigates three specific tensor decompositions to parameterize $A$ :

Tensor Train Decomposition (TTD): Decomposes the tensor into a sequence of 3rd-order factor tensors. It offers numerical stability and linear scaling in the tensor order.
Hierarchical Tucker Decomposition (HTD): Uses a binary tree structure to group modes recursively. It allows flexible grouping and is a generalization of TTD.
Canonical Polyadic Decomposition (CPD): Represents the tensor as a sum of rank-one components. It provides the most compact parameterization (linear in $n, k, r$ ).

C. Algorithm: Alternating Least Squares (ALS)

Since the optimization problem is non-convex, the authors develop Alternating Least Squares (ALS) algorithms tailored to each decomposition:

Mechanism: The algorithm iteratively fixes all factor tensors/matrices except one and solves for the remaining one.
Subproblem Reduction: Crucially, fixing all but one factor reduces the nonlinear problem into a standard linear least-squares problem.
Efficiency: The regression matrices are constructed using tensor contractions (involving Kronecker and Khatri-Rao products), ensuring the subproblem dimensions depend only on the system size and tensor ranks, not the full tensor dimension.
Parallelization: The HTD algorithm specifically supports level-wise parallel updates of factor matrices.

3. Key Contributions

Theoretical Contributions

Convergence Analysis: The authors prove that the proposed ALS algorithms generate a sequence of objective values that is monotonically non-increasing and convergent. Under mild regularity conditions (e.g., full rank of regression matrices), the algorithms converge locally linearly to a first-order stationary point.
Robustness to Noise: The framework is analyzed under additive measurement noise. Theoretical bounds show that the estimation error remains within a neighborhood of the true solution, with the error size scaling linearly with the noise level.
Identifiability Conditions: The paper establishes sufficient and necessary conditions for system identifiability.
- Sufficient: A rank condition on the "lifted" data matrix (related to the number of unique monomials).
- Necessary: The stacked regression matrices for each subproblem must have full column rank.

Algorithmic Contributions

Scalable ALS Schemes: Development of specific ALS algorithms (Algorithms 1, 2, and 3) for TTD, HTD, and CPD, respectively.
Complexity Reduction: The computational complexity is reduced from exponential (in $n$ and $k$ ) to polynomial scaling (linear or quadratic in $n$ and $k$ , depending on the rank), making large-scale identification feasible.

4. Numerical Results

The authors validate the framework using synthetic HPDSs with $n=9$ and $k=4$ (and larger scales for scalability tests).

Convergence: All three methods (TTD, HTD, CPD) demonstrated reliable convergence and accurate recovery of the underlying factors when the assumed low-rank structure matched the ground truth.
Accuracy vs. Lifting Methods: When applied to general sparse HPDSs (where the ground truth is not strictly low-rank), the proposed low-rank methods achieved lower identification errors (approx. $5 \times 10^{-4}$ ) compared to standard "lifting" methods that attempt to recover the full tensor (approx. $4 \times 10^{-3}$ ). This suggests low-rank parameterization acts as an effective regularizer.
Noise Robustness: The proposed methods maintained lower error rates than lifting-based methods across increasing noise levels (1% to 5%).
Computational Scalability:
- Small Scale: Both methods work, but low-rank methods are faster.
- Large Scale: As dimension $n$ increased (up to 400), lifting-based methods failed due to Out-of-Memory (OOM) errors. The proposed ALS methods remained computationally feasible, demonstrating polynomial scaling in time and memory.

5. Significance and Impact

Overcoming the Curse of Dimensionality: This work provides a principled mathematical framework to identify high-order nonlinear systems that were previously computationally impossible to model due to parameter explosion.
Interpretability: By recovering factor tensors rather than a dense black-box tensor, the method offers insights into the latent interaction structures (e.g., specific multi-species interaction patterns in ecology).
Broad Applicability: The framework is applicable to diverse fields including ecology (species interaction networks), biology (gene regulatory networks), robotics (multi-agent coordination), and control theory.
Future Directions: The paper outlines paths for extending the method to partially observed data, discrete-time systems, and adaptive rank selection strategies.

In summary, the paper successfully bridges the gap between high-dimensional nonlinear system identification and scalable tensor algebra, offering a robust, efficient, and theoretically grounded solution for modeling complex higher-order dynamical systems.