Exact Recovery of Chaotic Systems from Highly Corrupted Data

Giang Tran; Rachel Ward

Source-linked AI summary

Exact Recovery of Chaotic Systems from Highly Corrupted Data

Giang Tran, Rachel Ward

arXiv:1607.01067v2Jul 4, 2016math.DS

TL;DR

Recovering governing equations from chaotic measurements is difficult when observations are heavily corrupted and sensitivity to initial conditions demands high precision. The paper combines statistical properties of Lorenz-like systems with partial sparse recovery to estimate sparse polynomial coefficients and outliers, solved numerically by alternating minimization. It provides recovery guarantees under stated assumptions and reports accurate coefficient recovery with exact outlier identification in several chaotic and hyperchaotic examples.

Problem
The paper asks how to recover governing equations accurately from time-varying chaotic measurements that may be corrupted over unknown intervals.
Method
The method combines Lorenz-like chaotic-system statistics with partial sparse recovery to jointly estimate sparse polynomial coefficients and corrupted measurement rows.
Results
The method recovers coefficients with high accuracy and exactly identifies outliers in numerical Lorenz and higher-dimensional chaotic-system examples.
Takeaways & Limitations
The results support exact or highly accurate recovery of sparse polynomial governing equations from highly corrupted chaotic data under the paper’s stated conditions.
Takeaways & Limitations
The theoretical guarantees are scoped to specified Lorenz-like systems, including the uniformly hyperbolic skew-product flow class and its assumptions.

Abstract

from arXiv · show

Learning the governing equations in dynamical systems from time-varying measurements is of great interest across different scientific fields. This task becomes prohibitive when such data is moreover highly corrupted, for example, due to the recording mechanism failing over unknown intervals of time. When the underlying system exhibits chaotic behavior, such as sensitivity to initial conditions, it is crucial to recover the governing equations with high precision. In this work, we consider continuous time dynamical systems $\dot{x} = f(x)$ where each component of $f: \mathbb{R}^{d} \rightarrow \mathbb{R}^d$ is a multivariate polynomial of maximal degree $p$; we aim to identify $f$ exactly from possibly highly corrupted measurements $x(t_1), x(t_2), \dots, x(t_m)$. As our main theoretical result, we show that if the system is sufficiently ergodic that this data satisfies a strong central limit theorem (as is known to hold for chaotic Lorenz systems), then the governing equations $f$ can be exactly recovered as the solution to an $\ell_1$ minimization problem -- even if a large percentage of the data is corrupted by outliers. Numerically, we apply the alternating minimization method to solve the corresponding constrained optimization problem. Through several examples of 3D chaotic systems and higher dimensional hyperchaotic systems, we illustrate the power, generality, and efficiency of the algorithm for recovering governing equations from noisy and highly corrupted measurement data.

1. Introduction

Recovering governing equations from chaotic, time-dependent data is difficult because simple nonlinear terms can generate highly complicated behavior, while existing approaches face reconstruction and identifiability challenges. The paper connects sparse representations, compressed sensing, and chaotic-system statistics to provide exact recovery guarantees under suitable conditions.

Simple nonlinearities can produce chaotic behavior: the Lorenz system has seven terms with one quadratic nonlinear term, while Rössler has six terms with one nonlinear term.
State-space reconstruction methods use time-delay and embedding-dimension estimates, but special parameter choices can make different systems produce the same scalar time series.
Prior coefficient-recovery methods formulate the problem as linear regression over a known basis and use thresholding to promote sparse governing equations.
Sparse representations are relevant because many chaotic systems have simple algebraic forms in high-dimensional nonlinear function spaces.
The paper provides exact recovery conditions for Lorenz-like chaotic systems with sparse polynomial equations and possibly highly corrupted measurements.

2. Problem Setting

The paper formulates recovery of sparse polynomial governing equations from time-varying state and derivative measurements corrupted over unknown intervals. It uses a dictionary of polynomial monomials and jointly estimates coefficients and sparse outliers, while chaotic-data conditions address uniqueness and recovery guarantees.

The target is a chaotic system ẋ = f(x), where f has polynomial components and measurements may be corrupted at unknown time intervals.
Sparse polynomial coefficients represent the assumption that many chaotic systems use only a few terms in a high-dimensional nonlinear function space.
The matrices X, Ẋ, and Φ(X) store state measurements, derivative data, and the polynomial dictionary built from the measurements.
For undamaged data, coefficient recovery becomes Ẋ = Φ(X)C, but regression methods lack guarantees when Φ(X) is not full-rank.
For chaotic data, the paper states conditions ensuring independent dictionary columns, full column rank, and unique polynomial coefficients despite potentially highly corrupted measurements.
Joint recovery models estimate polynomial coefficients and row-sparse corruption errors under Φ(X◦)C + E = Ẋ◦, then relax the intractable objective to a convex formulation.

3. Reconstruction Guarantee Analysis

The reconstruction analysis combines compressive-sensing recovery conditions with statistical properties of Lorenz-like chaotic systems. Under the stated ergodicity and polynomial assumptions, partial ℓ1 minimization exactly recovers governing coefficients and outliers with high probability.

Compressive-sensing foundations: Compressive sensing links exact recovery through ℓ1 minimization to null-space properties of the measurement matrix.The null-space property is necessary and sufficient for unique recovery of sparse vectors, while partial sparse recovery handles additional structured components.
Lorenz-like systems: The Lorenz equations are polynomial of degree p = 2, and the considered Lorenz-like class includes the classical Lorenz attractor.The analysis uses ergodic properties and an almost-sure statistical description of trajectories in this class.
Main recovery guarantee: Theorem 3.11 states that polynomial coefficients and outlier vectors can be exactly recovered as the unique solution of a partial ℓ1-minimization problem.For the stated polynomial flow and corrupted time-1-map observations, the recovery probability exceeds 1 − ε − e^−d3 log(3m).
Main recovery guarantee: The same exact-recovery guarantee extends to observations of a time-∆ map with ∆ < 1 under the corollary's sampling conditions.The corollary preserves the stated high-probability form for recovering both polynomial coefficients and outlier vectors.
Consequences for regression: The proof implies that the relevant measurement matrix has linearly independent columns and is full rank under sufficient sampling.This also theoretically justifies the noiseless regression algorithm of [BPK16].

4. Numerical Method

The numerical method solves the constrained recovery model with augmented Lagrangian/Bregman distance and alternating minimization, enforcing sparsity in both the error matrix and polynomial coefficient matrix. The coefficient update uses least squares followed by hard thresholding, while the method is reported as robust to noise.

The proposed model is solved numerically using augmented Lagrangian/Bregman distance and alternating minimization.
The constrained problem requires Φ(X◦)C + E = ˙X◦ while imposing sparsity on C.
The C-subproblem is an over-determined least-squares problem, followed by hard thresholding to enforce the system's coefficient sparsity.
The method is discussed as robust to noise when recovering the true coefficients C.
The algorithm iteratively updates variables from initial E0 and b0 using tolerance and parameters λ and µ.

5. Numerical Results

The numerical experiments recover chaotic-system coefficients accurately from corrupted measurements, including Lorenz, Rössler, and hyperchaotic systems. Performance remains strong under substantial corruption, while sufficient observation duration and data size are important.

Hyperchaotic systems: The numerical study also applies the reconstruction method to higher-dimensional hyperchaotic systems.The authors report this as evidence of numerical applicability beyond three-dimensional chaotic systems.
Numerical setup: The method uses second-order rate-of-change approximations to construct the optimization model from state-space measurements.The authors choose the second-order approximation for better accuracy.
Lorenz system: Lorenz experiments detect all outlier locations exactly and recover polynomial coefficients with very high accuracy across corruption levels.The experiments use 40,000 measurements over Tfinal = 20 and tolerate high corruption when the dataset is sufficiently large.
Lorenz system: 0.0096% coefficient error is achieved for Lorenz data with 19.19% and 49.53% corruption, with exact outlier detection after 22 and 31 iterations.These results correspond to Figures 1 and 2.
Lorenz system: 0.0317% and 0.0477% coefficient errors are obtained for Lorenz data with 22.55% and 71.89% corruption, respectively.Both experiments detect outlier locations exactly, but shorter observation intervals require a critical minimum duration.
Lorenz system: 0.0097% coefficient error is achieved for a Lorenz trajectory over Tfinal = 100 with 19.75% corruption, after 29 iterations.The experiment tests whether sensitivity to initial conditions interferes with recovery over a much longer interval.
Rössler system: Rössler experiments recover coefficients with 0.6%, 1.25%, and 2% error under 10.2%, 20%, and 40% corruption, respectively.Outlier locations are detected exactly; the 10.2% and 20% cases converge after 160 iterations, while the 40% case takes 314 iterations.

6. Conclusion and Discussion

The paper provides recovery conditions and a stable numerical scheme for identifying governing equations from highly corrupted data, including broader smooth systems through local polynomial approximations. Its examples recover coefficients and outlier locations in chaotic and hyperchaotic systems, while the current theory leaves associated dynamical-systems constants non-explicit.

The method combines Lorenz-like statistical properties with partial sparse-recovery guarantees to recover governing equations from highly corrupted data.The numerical scheme also identifies outliers exactly and recovers coefficients with high accuracy despite sensitivity to initial conditions.
The approach can extend beyond polynomial equations by locally approximating smooth governing equations with Taylor expansions and piecing those approximations together.
10.25% corrupted data: the Rössler hyperchaos example recovered the coefficients and exactly detected outlier locations after 201 iterations.
The current theory does not make the associated constants for dynamical systems explicit.The authors suggest this limitation may motivate making those constants more explicit.