A Sampling Complexity-aware Framework for Discrete-time Fractional-Order Dynamical System Identification

arXiv:2501.17499 · eess.SY, cs.LG, cs.SY · Submitted 2025-01-29 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.

Rosa: Today's paper: "A Sampling Complexity-aware Framework for Discrete-time Fractional-Order Dynamical System Identification".

Dev: The gist The proposed affine discrete-time fractional-order dynamical system (FoDS) identification algorithm provides a robust method for inferring system parameters in noisy data by reformulating the identification problem as a…

Rosa: First, who's behind it and why it matters.

Title and authors: Rosa: So we’re looking at "A Sampling Complexity-aware Framework for Discrete-time Fractional-Order Dynamical System Identification." It’s about how to identify systems with fractional orders when you have noisy measurements and you don't know the underlying functions driving the system.

Dev: Right, it addresses that gap. The core idea is to avoid those difficult polynomial equations by reformulating everything as a least squares problem, which lets us infer the system parameters directly.

Taro: From an autonomy standpoint, that’s important because if we can estimate the fractional order alpha reliably from noisy sensor data, it means we can build a model that better predicts how the world will behave under uncertainty.

Rosa: And they don't just stop there; they derive expectation and probabilistic bounds for the estimation error assuming you already have some prior knowledge about those unknown functions f and g.

Dev: They state that this estimation error decays at a rate of N = O(d/epsilon), where N is the number of samples you need, and epsilon is how accurate you want to be.

Taro: That scaling, that linear dependence on the dimension d, tells us how much data we actually need to get a decent estimate for high-dimensional systems.

Rosa: So, what they do in this paper is essentially provide a rigorous mathematical guarantee on how many samples you need before your identification estimate settles down to the accuracy you want.

Dev: It gives us concrete numbers on the required sample complexity for this specific method.

The paper's summary: Rosa: Now, let's look at what they actually did in "A Sampling Complexity-aware Framework for Discrete-time Fractional-Order Dynamical System Identification." They start by defining the Grunwald–Letnikov operator to discretize the fractional derivative into a finite difference.

Dev: That operator is defined using the Gamma function and a diagonal matrix psi(alpha, j), which essentially lets us represent that fractional order as a sum of past states in this discrete time setting.

Taro: It’s basically turning a continuous-time idea, like fractional calculus, into something we can actually compute on a computer with discrete data points.

Rosa: Then they describe how to write the entire system using this operator, leading to the affine discrete-time fractional order dynamical system form x k+one = f(x k) + g(u k) - k sum j=one d psi(alpha, j) x k+one-j <ref:2501.17499#pg1,affine discrete-time fractional order dynamical system>.

Dev: But the real move is how they handle the unknown functions f and g. They suggest approximating these functions using orthogonal basis functions like trigonometric or Chebyshev polynomials.

Rosa: By doing that, they transform this complex identification problem into a standard least squares problem where we just minimize the norm of the difference between our actual data and our model predictions.

Taro: So instead of solving an intractable equation, we’re minimizing a simple error function based on these basis function coefficients gamma(h) i and beta(l) i.

Dev: And that leads directly into the sample complexity analysis they provide, which tells us how to control the estimation error below a certain threshold.

The paper's improvements: Rosa: The authors suggest two key improvements in this work. First, they propose avoiding solving higher-order polynomial equations entirely for finding the fractional orders.

Dev: That’s a big deal because those polynomial solutions can sometimes give you multiple possible orders, which is messy when dealing with real experimental data that always has noise.

Taro: Avoiding that ambiguity simplifies things immensely for someone trying to build an autonomous system where you need a single, stable model to operate on.

Rosa: Second, they introduce the function approximation step using orthogonal basis functions to handle those unknown functions f and g. This makes the identification process much more flexible.

Dev: It lets us fit a wide variety of dynamics onto our data because we aren't stuck with a single, rigid model structure.

Taro: That flexibility is what you need when the real world misbehaves; you need a framework that can adapt its model structure based on what the data shows.

Rosa: And finally, they provide these rigorous sample complexity bounds, specifically showing that the error decays at a rate of N = O(d/epsilon). That’s the quantitative guarantee we were looking for.

Dev: It’s not just theoretical math; it gives us a practical idea of how much data we need to actually get a usable estimate for our system parameters.

Conclusion: Rosa: So, wrapping up "A Sampling Complexity-aware Framework for Discrete-time Fractional-Order Dynamical System Identification," this paper offers a way to identify fractional order systems robustly, even in the presence of noise and when the functions defining the system aren't fully known.

Dev: The main implication is that we can get reliable estimates for those fractional orders by treating it as a least squares problem guided by sample complexity theory.

Taro: For autonomy, this means we have a framework to handle uncertainties in our environment’s dynamics without getting bogged down in overly complex, brittle models.

Rosa: And they provide those bounds showing that the error rate depends directly on the dimension of the state space and how small you want that error to be.

Dev: They show that with enough data, specifically N = O(d/epsilon) samples, we can control the estimation error to a specific level epsilon.

Taro: It’s a solid tool for when the dynamics are non-Markovian and you need an adaptive way to estimate the order.

Rosa: We’ve seen how this framework works and what its theoretical limits are for estimating fractional order systems in noisy data with "A Sampling Complexity-aware Framework for Discrete-time Fractional-Order Dynamical System Identification."

Dev: It’s a solid piece of work that moves us toward more reliable system identification methods in complex dynamic environments.

Department of Electrical and Computer Engineering, University of Southern California · Elmore Family School of Electrical and Computer Engineering, Purdue University

eess.SY, cs.LG, cs.SY

Submitted: 2025-01-29

Updated: 2025-01-29

Journal ref: American Control Conference (ACC) 2025

Code: https://github.com/EricZhang0312/Fractional_Order_System_

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 79/100

The gist: The gist The proposed affine discrete-time fractional-order dynamical system (FoDS) identification algorithm provides a robust method for inferring system parameters in noisy data by reformulating

Key concepts

Fractional-Order Dynamical System (FoDS)
This is a mathematical model used to describe complex systems where dynamics depend on fractional derivatives. These are often used to model biological or natural processes that exhibit 'memory' or long-term dependencies, which standard integer-order models cannot capture effectively.
Grunwald-Letnikov Operator
This operator is a specific mathematical tool used to discretize the continuous fractional derivative into a form suitable for digital computation. It allows researchers to approximate the behavior of systems governed by fractional calculus using discrete steps, making them solvable in practical settings.
Sample Complexity Analysis
This analysis determines the minimum number of data points (samples) needed to reliably estimate system parameters within a certain error tolerance. The paper provides bounds showing that for a desired accuracy $\epsilon$, the required number of samples $N$ grows proportionally to $d/\epsilon$, where $d$ is the state dimension.

Terminology

Summary

The gist The proposed affine discrete-time fractional-order dynamical system (FoDS) identification algorithm provides a robust method for inferring system parameters in noisy data by reformulating the identification problem as a least squares estimation and deriving sample complexity bounds.

Problem Formulation

The paper begins by defining the Grunwald-Letnikov operator to discretize the fractional order derivative, which is represented as ∆αxk:= Xk j=0 ψ(α, j)xk−j The discrete-time FoDS is then expressed in state-space form as xk+1 = h(xk, uk), where the functions hi(·, ·): R d × R m → R are arbitrary functions Using the Grunwald–Letnikov difference operator, the system is written as xk+1 = h(xk, uk) − k X+1 j=1 ψ(α, j)xk+1−j The model to be estimated is an affine discrete-time FoDS: xk+1 = f(xk) + g(xk)uk − k X+1 j=1 ψ(α, j)xk+1−j

Parameter Estimation Algorithm

The proposed algorithm for Problem 2, where functions f and g are unknown and data is noisy, consists of two main steps: Data Generation and Function Approximation In the first step, data is generated by following a procedure involving initial conditions x i0 and white Gaussian noise w i0, resulting in equations like x 1 1 = f(x 1 0) + g(x 1 0)u 1 0 − ψ(α, 1)x 1 0 + w 1 0 In the second step, function approximation is used to transform the problem into a standard least squares problem The functions f(·) and g(·) are approximated using orthogonal basis functions, such as trigonometric or Chebyshev polynomials, with unknown coefficients γ(h) i and β(l) i This leads to a least squares problem where the solution is found by minimizing X − ξθ2 2

Sample Complexity Analysis

The sample complexity analysis focuses on determining the number of samples N required to control the estimation error below a specified threshold, providing both an expectation bound and a high-probability bound Assuming full knowledge of f and g, the state-space model related to the sample complexity problem is expressed as βk+1 = βk, where yk = Cβk + wk The solution for the parameter vector βˆ is given by βˆ = (C T C) −1C T Y, ¯

Theoretical Bounds and Results

The expectation bound for the estimation error is given by E h∥βˆ − β∥2 2 i ≤ d N λmax(C T C)λmax(Kw) λmin(CT C) 2 This shows that the sample complexity scales as N = O d/ϵ, where N is the number of samples, d is the dimension of the state variable, and ϵ represents the desired estimation accuracy The high-probability bound for t > λd 2 shows that P(∥βˆ − β∥2 2 ≥ t) ≤ exp−t λ + q 2tdλ − d squared 2 Simulation results demonstrate that the theoretical bounds are tight, validating the accuracy and robustness of this algorithm The empirical estimation error highly aligns with the theoretical error predictions across various fractional orders in simulations.

Conclusion

The proposed affine discrete-time fractional-order system identification algorithm is robust, effectively handling noisy data by avoiding higher-order polynomial equations and providing rigorous sample complexity guarantees under the assumption of known functions f and g The method successfully identifies the fractional order parameter even when the underlying functions are unknown through function approximation. Future work will explore sample complexity analysis when the functions f and g are unknown.

--- Page 6 ---

The key intuition behind the proof is as follows. To bound E h∥βˆ − β∥2 2 i, we first notice that the error, βˆ − β, follows a Gaussian distribution N(0, 1/N(C T C)−1C T KwC(C T C)−1 Then we use trace trick and Lemma 1 to derive an upper bound for E h∥βˆ − β∥2 2 i The detailed proof is provided in Appendix I.

--- Page 7 ---

The key intuition behind the proof is as follows. We begin by whitening the error covariance matrix, transforming the error into a multivariate standard Gaussian random variable This allows us to express the squared estimation error,∥βˆ − β∥2 2 as a weighted sum of independent, identically distributed standard normal random variables Then we use trace trick and Lemma 1 to derive the expectation bound

--- Page 8 ---

The detailed proof is provided in Appendix II. The key intuition behind the proof is as follows. We begin by whitening the error covariance matrix, transforming the error into a multivariate standard Gaussian random variable This allows us to express the squared estimation error,∥βˆ − β∥2 2 as a weighted sum of independent, identically distributed standard normal random variables Then we use trace trick and Lemma 1 to derive the high-probability bound.

--- Page 8 ---

The last step is derived by substituting λ(td + d) for t The last step is derived by substituting λ(td + d) for t

--- Page 8 ---

The last step is derived by substituting λ(td + d) for t <ref:2501.

Improvements for AI systems

  1. Bold header: Robust Fractional-Order System Identification for Noisy Data

This algorithm can identify system parameters, including fractional orders, even when measurements are subject to white Gaussian noise by reformulating the identification problem as a least squares estimation and avoiding solving higher-order polynomial equations.

  1. Bold header: Parameter Estimation with Known Functions

When the functions f and g are known, the system can be used to estimate the fractional order α using an algorithm where the error decays at a rate of N = O(d/ϵ), providing theoretical bounds for accuracy based on prior knowledge of the functions f and g in the FoDS model.

  1. Bold header: Basis Function Approximation for Unknown Dynamics

For systems where f and g are unknown, the system can be identified by approximating these functions using orthogonal basis functions, transforming the problem into a standard least squares framework to estimate all unknown parameters simultaneously.

Related papers