PaperlayerView exact revision on arXiv

Source-linked AI summary

Koopman-based lifting techniques for nonlinear systems identification

Alexandre Mauroy, Jorge Goncalves

arXiv:1709.02003v4math.OCeess.SYmath.DS

TL;DR

Nonlinear system identification is difficult when derivative estimates are unreliable for low-rate, noisy, or short time-series data. The paper lifts observations into a Koopman observable space, identifies linear finite-dimensional representations, and recovers vector fields through main and dual schemes. The methods are reported to recover several classes of systems, support high-dimensional network reconstruction, and converge under optimal conditions.

  • Problem

    Derivative-based nonlinear system identification is constrained by low sampling rates, measurement noise, and short time series, motivating methods that avoid estimating state derivatives.

  • Method

    The paper lifts data into observable space, identifies the linear Koopman operator using finite-dimensional schemes, and then recovers the vector field.

  • Results

    The methods recover vector fields for several system classes, while the dual method identifies high-dimensional systems and supports network reconstruction; convergence is proved under optimal conditions.

  • Takeaways & Limitations

    Koopman-based lifting provides a linear-method alternative for nonlinear identification that is suitable for small, low-rate time series and high-dimensional systems.

Abstract

from arXiv · show

We develop a novel lifting technique for nonlinear system identification based on the framework of the Koopman operator. The key idea is to identify the linear (infinitedimensional) Koopman operator in the lifted space of observables, instead of identifying the nonlinear system in the state space, a process which results in a linear method for nonlinear systems identification. The proposed lifting technique is an indirect method that does not require to compute time derivatives and is therefore well-suited to low-sampling rate datasets. Considering different finite-dimensional subspaces to approximate and identify the Koopman operator, we propose two numerical schemes: the main method and the dual method. The main method is a parametric identification technique that can accurately reconstruct the vector field of a broad class of systems (including unstable, chaotic, and system with inputs). The dual method provides estimates of the vector field at the data points and is well-suited to identify high-dimensional systems with small datasets. The present paper describes the two methods, provide theoretical convergence results, and illustrate the lifting techniques with several examples.

I. Introduction

The paper addresses nonlinear system identification from time-series data without requiring accurate state derivatives, which can be problematic for low-rate, noisy, or short datasets. It proposes lifting observations into a space where Koopman-operator identification is linear, followed by vector-field recovery.

  • Motivation: Derivative-based direct methods become difficult with low sampling rates, noisy measurements, or short time series, motivating indirect identification methods.These challenges are especially relevant when measurements are costly or sparse.
  • Approach: The proposed approach lifts data, identifies a linear Koopman operator in observable space, and then identifies the nonlinear system's vector field.The workflow connects data to vector-field recovery through three stages.
  • Contributions: The main method uses parametric identification and can handle a broad class of behaviors, including unstable and chaotic systems.The paper also considers extensions to non-polynomial vector fields and systems with inputs or process noise.
  • Contributions: The dual method is designed for high-dimensional systems and small datasets, including network-topology reconstruction when samples are fewer than unknown parameters.The paper presents theoretical convergence results and examples for both methods.
  • Problem formulation: The identification problem is formulated for polynomial vector fields represented as linear combinations of known library functions.The polynomial basis uses monomials up to a specified total degree.
  • Koopman framework: The lifted observable dynamics are infinite-dimensional but linear and are governed by a Koopman-operator semigroup.The paper uses this correspondence to move identification from state space to lifted space.

C. Linear identification in the lifted space

The main identification method approximates Koopman dynamics in a finite-dimensional basis of observables. It lifts snapshot pairs, fits a finite-rank Koopman representation by linear least squares, and obtains an infinitesimal-generator approximation whose finite-dimensional description is globally valid rather than locally linearized.

  • Overview: The method consists of lifting snapshot data, linearly identifying the Koopman operator, and recovering the vector field.The three stages are summarized explicitly in the paper's workflow.
  • Data lifting: Snapshot pairs are transformed from (xk, yk) into pairs of basis-function evaluations before operator identification.With monomial bases, the lifted vectors are p(xk) and p(yk).
  • Basis construction: A finite-dimensional subspace spanned by N basis functions makes the infinite-dimensional lifting numerically tractable.For polynomial vector fields, monomials up to total degree m are chosen, with m ≥ mF.
  • Operator identification: The finite-rank Koopman approximation is obtained by projecting the operator onto the chosen basis and fitting it at sampled points with least squares.The resulting coefficient computation uses the pseudoinverse of the data matrix.
  • Interpretation: The finite-dimensional representation provides a global linear description of the nonlinear system rather than a local linearization.The representation corresponds to a projection of the Koopman operator onto the selected observable subspace.
  • Generator recovery: The infinitesimal generator is approximated using the principal matrix logarithm of the identified finite-dimensional Koopman representation.The resulting matrix is an approximation of the generator representation on the selected basis.
  • Caveat: Even without measurement noise, the identified generator is generally only approximate and agrees with the target representation only as N →∞ under additional conditions.The caveat includes possible non-uniqueness of the matrix logarithm.

3) Third step - identification of the vector field:

The third step recovers the vector-field coefficients from the identified generator by using coordinate functions among the basis functions. The method can also evaluate vector-field values directly at sampled states, while an alternative sparse overdetermined fit did not improve numerical results in the reported experiments.

  • Coefficient recovery: Vector-field coefficients are recovered from generator columns associated with coordinate basis functions such as pl(x) = xj.The coordinate-function choice connects the generator representation to each component of the vector field.
  • Alternative formulation: Identifying the Koopman semigroup directly would require solving a nonconvex nonlinear least-squares problem.The paper contrasts this option with its linear identification procedure.
  • Alternative fit: Using all data columns creates an overdetermined system that can be solved with sparsity promotion, but numerical experiments did not show improved results.The alternative is described as similar to a Lasso-type fit.
  • Pointwise estimates: The method can directly estimate vector-field values F(xk) at the sampled states by evaluating the recovered representation at each xk.This procedure is similar to the dual method's pointwise estimates.

B. Algorithm

Algorithm 1 lifts snapshot data into observable space, identifies a finite-dimensional Koopman representation, and recovers the vector field through basis-function projections. Under optimal conditions, the estimates converge exactly, while larger bases can reduce errors at finite sampling periods.

  • Algorithm 1: Algorithm 1 constructs lifted snapshot matrices after ensuring the number of basis functions does not exceed the number of data pairs.The algorithm can add snapshots or reduce the lifting degree before forming the matrices used for identification.
  • Convergence: With infinitely many data points and basis functions and Ts → 0, Algorithm 1 recovers the vector field with probability one.The result follows from convergence of the discrete projection and the basis projection to the identity operator.
  • Theoretical conditions: The convergence analysis assumes a compact invariant set, an invertible nonsingular flow, uniformly random samples, and a complete basis in L2(X).The Koopman semigroup is strongly continuous under these assumptions, with nonsingularity ensuring boundedness.
  • Polynomial case: For polynomial vector fields represented within the selected basis, the coefficient estimates converge exactly without requiring the number of basis functions to diverge.When the polynomial degree is covered, the projection reproduces the vector field directly.
  • Finite sampling: Although the proof requires Ts → 0, simulations suggest small estimation errors at Ts = O(1) when the basis dimension is sufficiently large.Increasing the number of basis functions can improve approximation for larger sampling periods.
  • Limitations: Measurement noise makes the estimator biased and inconsistent, although the algorithm performs well at small noise levels and is robust to process noise.The theoretical convergence results therefore apply only in the absence of measurement noise.

IV. Extensions

The method extends Koopman-based identification to open systems with known inputs and to non-polynomial vector fields. Under a zero-order-hold assumption, inputs are incorporated as augmented state variables and their coefficients can also be identified.

  • IV. Extensions: The extensions cover systems with known inputs, process noise, and non-polynomial vector fields.The input extension is developed for open systems, while separate extensions address process noise and non-polynomial dynamics.
  • Open systems with inputs: For constant inputs between snapshots, the input can be treated as an additional state variable with dynamics ˙u = 0.This converts the open system into an augmented autonomous system for applying the Koopman framework.
  • Open systems with inputs: The augmented procedure identifies both the vector-field coefficients for the state x and those associated with the input u.Snapshot pairs use the augmented coordinates [x_k, u_k] and [y_k, u_k].

B. Process noise

The proposed method is extended to process-noisy systems through the Koopman generator associated with the stochastic dynamics. The numerical procedure remains largely unchanged, and the paper reports robustness to process noise and extensions to non-polynomial vector fields.

  • Process noise: Process noise enters the infinitesimal generator through a Laplacian term that accounts for diffusion.The generator is connected to the Kolmogorov backward equation.
  • Process noise: The numerical scheme does not need to be adapted in its first step to account for process noise.The second step uses the infinitesimal generator whose matrix representation includes the diffusion contribution.
  • Process noise: For coordinate identity functions, the Laplacian vanishes, so the vector-field coefficient computation can still use the original relation.The paper illustrates robustness against process noise in Section VI-B.
  • Non-polynomial vector fields: The method can be adapted to non-polynomial vector fields by replacing monomial libraries with general library functions, without requiring analyticity.An augmented subspace containing the library functions avoids an additional projection error.
  • Non-polynomial vector fields: A direct least-squares regression on vector-field values is simpler but is reported as less efficient than the proposed method.The comparison is based on numerical experiments.

V. A dual lifting method for large systems

The dual lifting method addresses the main method’s data and computational demands by working in sample space rather than functional space. It is designed for cases with more basis functions than data points and provides vector-field estimates at sampled states.

  • V. A dual lifting method for large systems: The dual method is introduced because the main method may require many data points and become computationally intractable for high-dimensional systems.The main method requires K ≥ N, whereas the dual method operates when N ≥ K.
  • Dual method: The dual method identifies a Koopman representation in the K-dimensional sample space and estimates the vector field at each data point.Its three stages are data lifting, Koopman-operator identification, and vector-field identification.
  • Basis functions: Gaussian radial basis functions make the number of basis functions equal to the number of samples, independently of system dimension.This keeps the associated matrices at a reasonable size for high-dimensional systems.
  • Relation to existing methods: The dual matrix representation is related to kernel EDMD and resembles the original Dynamic Mode Decomposition construction.The paper notes that the representation is slightly different from kernel EDMD.
  • Comparison with the main method: The dual formulation reverses the constraint regime: each test function yields a constraint with K unknowns, so it is suited to K ≤ N.By contrast, the main formulation has N unknowns and requires K ≥ N.

3) Third step - identification of the vector field:

The third step recovers the vector field from the identified Koopman generator, first estimating its values at data points and then regressing library functions to obtain coefficients. The dual method has convergence guarantees under sampling, basis, and projection conditions.

  • 3) Third step - identification of the vector field:: The dual procedure estimates the vector field at sampled points and then solves separate regression problems for each state component’s coefficients.The regressions can use sparsity-promoting Lasso when most coefficients are expected to be zero.
  • 3) Third step - identification of the vector field:: The vector-field estimate is obtained by applying the identified sample-space generator to identity functions.Using more functions creates an overconstrained problem that does not necessarily improve accuracy.
  • 3) Third step - identification of the vector field:: The dual method permits non-polynomial or non-analytic vector fields by using general library functions rather than assuming monomials.The coefficient regressions remain decoupled across state components.
  • C. Theoretical results: Under uniform random sampling, noiseless snapshots, and suitable basis conditions, Algorithm 2 provides exact vector-field estimates in the stated limiting regime.The theorem assumes a compact forward-invariant set and an invertible, nonsingular flow.
  • C. Theoretical results: With Gaussian radial basis functions and K = N, the projected identity functions converge uniformly together with their derivatives under the stated conditions.This basis also satisfies the required independence condition.
  • Comparison of frameworks: The main and dual frameworks differ in their finite-dimensional representations and data regimes, motivating the dual formulation for sample-limited problems.The paper summarizes these distinctions in Table I.

VI. Illustrative examples

The examples illustrate the proposed lifting methods under simulated conditions with measurement noise, while limiting the study of basis-function and parameter choices.

  • The paper presents these examples illustratively rather than as an extensive study of basis functions and parameter choices.
  • The examples use simulated data with Gaussian state-dependent measurement noise of standard deviation σmeas = 0.01.

A. Main method

The main lifting method identifies vector fields for systems with stable, unstable, and chaotic dynamics from snapshot data, including settings unfavorable to derivative estimation. Its error decreases with smaller sampling periods, while indirect lifting remains more accurate than finite differences at larger sampling periods.

  • Main method: The experiments use large sampling periods and only two or three data points per trajectory for the first two systems, challenging direct derivative estimation.
  • Main method: The lifting method achieves small RMSE and NRMSE while identifying three systems from fairly few samples.The systems include a Van der Pol oscillator, an unstable system, and a chaotic Lorenz system.
  • Main method: With measurement noise, the minimum nonzero NRMSE occurs at an intermediate sampling period because very small periods increase noise sensitivity.
  • Main method: In the noiseless case, NRMSE decreases exponentially as the sampling period decreases and tends to zero as Ts → 0.
  • Main method: The lifting method maintains acceptable vector-field error, such as NRMSEF < 0.1, for larger sampling periods than central finite differences.For the unstable system, the critical sampling-period transition lies beyond the maximal integration time.

B. Extensions

The extensions apply the lifting method to forced and stochastic systems, non-polynomial vector fields, and network reconstruction. Performance is strong for forcing and process noise, while the non-polynomial example is substantially more noise-sensitive with the main method.

  • Input and process noise: The method provides a good estimate of the forced Duffing vector field, including its forcing term.The experiment uses K = 250 snapshot pairs from five trajectories.
  • Input and process noise: The Duffing identification error remains small even with strong process noise, suggesting robustness to process noise.
  • Non-polynomial vector fields: For the non-polynomial toggle switch, the main method achieves NRMSE = 0.008 without measurement noise but 0.494 when σmeas = 0.001.
  • Dual method: The dual method targets high-dimensional datasets where the number of basis functions can greatly exceed the number of sample points.Its regression formulation uses Lasso variants depending on whether K is below or above NF.
  • Network reconstruction: Network reconstruction is formulated as detecting nonzero vector-field coefficients associated with interactions between states.

1) Kuramoto oscillators:

The dual method reconstructs networks from small datasets, covering Kuramoto oscillators and systems with quadratic and cubic interactions. The conclusion presents the lifting framework as effective across several settings while identifying robustness and generality as areas for further development.

  • Network with nonlinear couplings: For quadratic and cubic interaction networks, the dual method accurately estimates the vector field and reconstructs the network.The experiments use network sizes n ∈ {20, 50, 100} with only two data pairs per trajectory.
  • Conclusion: The proposed schemes use linear techniques and avoid estimating state time derivatives, supporting identification from small, low-sampling-rate time series.
  • Conclusion: The dual method extends the approach to high-dimensional systems and network reconstruction, while theoretical results establish convergence under optimal conditions.
  • Conclusion: Future work includes improving robustness to measurement noise, obtaining unbiased and consistent schemes, and extending identification beyond library-function settings.
Loading 1709.02003v4…