Technical Summary: Adaptive Symmetry Discovery for Dynamical System Identification

1. Problem Statement

The paper addresses the problem of dynamical system identification from a single trajectory of observed state transitions. Specifically, it focuses on systems that are equivariant with respect to a symmetry group $G$, where the group $G$ itself is unknown to the learner.

The authors consider a class of feature-lifted linear dynamical systems, where the state evolution $x_{t+1} = f(x_t)$ is governed by a linear map $W$ acting on a lifted feature space $\Phi(x_t)$, such that $x_{t+1} = W\Phi(x_t)$. The dynamics are assumed to be $G$-equivariant, meaning the parameter matrix $W$ satisfies the intertwining condition $\rho(g)W = W\rho_\Phi(g)$ for all $g \in G$, where $\rho$ and $\rho_\Phi$ are representations of $G$ on the state and feature spaces, respectively.

The core challenge is twofold:

1. Identifiability: Determine the minimum trajectory length $T$ required to uniquely identify the system parameters $W$ when the symmetry group $G$ is known.
2. Adaptive Discovery: Develop a method to simultaneously identify the unknown symmetry group $G$ and the system parameters $W$ from a single trajectory, achieving the same sample efficiency (trajectory length) as if $G$ were known a priori.

2. Methodology

The paper employs tools from group representation theory and the theory of Cayley graph expanders to derive theoretical guarantees and algorithms.

2.1 Known Symmetry: Sample Complexity Characterization

When $G$ is known, the authors characterize the minimal trajectory length $T_\Phi(G)$ required for generic identifiability.

• Isotypic Decomposition: Using the decomposition of the state and feature spaces into irreducible representations (irreps) of $G$, the equivariant matrix $W$ decomposes into independent blocks corresponding to each irrep $\pi$.
• Rank Condition: Identifiability reduces to ensuring that the "feature design matrix" for each active irrep block has full row rank. Specifically, for each irrep $\pi$ with multiplicity $m_\pi$ in the feature space, the trajectory must excite the system sufficiently such that the generic rank of the stacked feature vectors equals $m_\pi$.
• Lower Bound: The authors establish a representation-theoretic lower bound: $T_\Phi(G) \ge \max_{\pi: n_\pi > 0} \lceil m_\pi / d_\pi \rceil$, where $d_\pi$ is the dimension of the irrep and $n_\pi$ is its multiplicity in the state space.
• Key Insight: For specific symmetries (e.g., permutation equivariance in polynomial systems), this bound can be significantly lower than the generic case (where $T \approx$ total feature dimension), often reducing the required trajectory length to a constant independent of the state dimension.

2.2 Adaptive Symmetry Discovery

When $G$ is unknown, the paper proposes Algorithm 1, which iterates through a known family of candidate groups $\mathcal{G}$.

• Generating Sets: Instead of testing equivariance against the entire group (which may be exponentially large), the algorithm samples a small set of random elements $S_G$ from each candidate group $G \in \mathcal{G}$.
• Random Generators: Leveraging the fact that $O(\log |G|)$ random elements generate a finite group with high probability (based on subgroup growth arguments and properties of Cayley graphs), the algorithm imposes equivariance constraints only on these sampled generators.
• Feasibility Testing: For each candidate group, the algorithm checks if there exists a parameter matrix $W$ satisfying the trajectory constraints and the equivariance constraints for the sampled generators.
• Selection: The algorithm selects the candidate group with the maximum cardinality among those that admit a feasible solution.
• Theoretical Guarantee: Under the condition of generic candidate separation (where distinct candidate groups can be distinguished by short trajectories), the algorithm recovers the true dynamics and the true symmetry group with high probability, using a trajectory length no longer than $T_\Phi(G_{true})$.

2.3 Bounded-Index Subgroup Discovery

For scenarios where the unknown group is a subgroup of a known ambient group $\Gamma$ with bounded index $B$, the paper proposes Algorithm 2.

• Rejection Sampling: Instead of enumerating candidate subgroups, the algorithm samples elements uniformly from the ambient group $\Gamma$.
• Elementwise Testing: Each sampled element is tested for feasibility (i.e., does there exist a $W$ consistent with the trajectory that is equivariant to this specific element?).
• Generation: Accepted elements are collected until a generating set for the unknown subgroup is formed. The expected number of ambient samples required is proportional to the index bound $B$.

3. Key Contributions

1. Sample Complexity Reduction: The paper proves that knowing a symmetry group allows for system identification from significantly shorter trajectories compared to the generic setting. It precisely characterizes this reduction via the multiplicities of irreducible representations in the feature space.
2. Adaptive Discovery with Optimal Efficiency: The authors propose a method to discover the unknown symmetry group directly from a single trajectory. Crucially, they show that this adaptive discovery incurs negligible overhead in terms of trajectory length; the system can be identified from a trajectory of length $T_\Phi(G)$ even when $G$ is unknown, provided the candidate family is generically separating.
3. Computational Efficiency: The proposed algorithms avoid iterating over the full group elements. By utilizing random generating sets (of size logarithmic in the group size), the computational complexity remains polynomial in the state dimension and logarithmic in the group size, making it feasible for large groups (e.g., permutation groups).
4. Theoretical Framework: The work introduces a novel application of group representation theory and Cayley graph expansion properties to the problem of dynamical system identification, providing provable guarantees for symmetry discovery.

4. Results

• Theoretical Bounds: The paper derives exact formulas for the minimal trajectory length $T_\Phi(G)$ for various symmetry groups, including linear systems, polynomial systems, and permutation-equivariant systems. For example, for quadratic systems with full permutation symmetry ($S_d$), the required trajectory length is a constant (4) independent of the state dimension $d$, whereas the generic case requires $O(d^2)$.
• Algorithmic Performance:
  • Algorithm 1 successfully recovers the true dynamics and symmetry group with probability at least $1-\delta$ using $O(\log |G|)$ samples per candidate group.
  • Algorithm 2 recovers bounded-index subgroups without enumerating candidates, with an expected sampling overhead of $O(B \log |\Gamma|)$.
• Empirical Validation: A proof-of-concept experiment on linear dynamics with permutation symmetries confirms the theoretical predictions. The dimension of the feasible solution set drops to zero exactly at the predicted trajectory lengths for trivial, single-transposition, and full-symmetric groups.

5. Significance and Claims

The paper claims to address a fundamental gap in the literature: while symmetries are known to improve learning, provable quantitative guarantees for symmetry discovery in dynamical systems have been lacking. Most existing methods are heuristic or model-specific.

The authors emphasize that their work provides:

• Foundational Limits: A theoretical understanding of how much sample efficiency can be gained from symmetries and under what conditions this gain can be achieved without prior knowledge of the symmetry.
• Optimal Adaptation: The demonstration that one can achieve the same optimal trajectory length as the "known-symmetry" case even when the symmetry is unknown, effectively removing the cost of discovery in terms of data requirements.
• New Tools: The integration of representation theory and expander graph properties into system identification, which the authors suggest may be of independent interest for studying symmetries in dynamical systems.

The paper remains modest regarding its scope, noting that the current results are for noiseless settings and finite groups. It identifies extending these results to noisy systems and infinite (Lie) groups as important directions for future work.