PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Xiaole Zhang, Vijay Gupta, Paul Bogdan

arXiv:2501.17499v1eess.SYcs.SY

TL;DR

Noisy-data identification of fractional-order systems remains challenging, and prior work cited here does not provide sample-complexity analysis. The paper proposes an affine discrete-time identification procedure based on generated data and least squares, and reports N = O(d/ϵ) sample scaling with empirical errors closely matching theoretical predictions.

  • Problem

    A prior discrete fractional-order identification method performs poorly with noisy data, particularly in high dimensions, and the cited work does not analyze sample complexity.

    Source: §I · p. 1

  • Method

    The algorithm generates equations from experiments and estimates unknown parameters with least squares, using basis-function approximations when f and g are unknown.

    Source: §III · p. 2, §VI · p. 6

  • Results

    N = O(d/ϵ) samples for the stated estimation-error scaling, and simulations show empirical estimation error closely aligns with theoretical predictions.

    Source: §I · p. 2, B. Numerical Results for Sample… · p. 6

  • Takeaways & Limitations

    The proposed algorithm is designed to identify fractional-order systems with noisy data while avoiding higher-order polynomial equations.

    Source: §I · pp. 1–2, §VI · p. 6

    The sample-complexity bounds assume prior knowledge of the functions f and g.

    Source: §I · p. 2

Abstract

from arXiv · show

A variety of complex biological, natural and man-made systems exhibit non-Markovian dynamics that can be modeled through fractional order differential equations, yet, we lack sample comlexity aware system identification strategies. Towards this end, we propose an affine discrete-time fractional order dynamical system (FoDS) identification algorithm and provide a detailed sample complexity analysis. The algorithm effectively addresses the challenges of FoDS identification in the presence of noisy data. The proposed algorithm consists of two key steps. Firstly, it avoids solving higher-order polynomial equations, which would otherwise result in multiple potential solutions for the fractional orders. Secondly, the identification problem is reformulated as a least squares estimation, allowing us to infer the system parameters. We derive the expectation and probabilistic bounds for the FoDS parameter estimation error, assuming prior knowledge of the functions \( f \) and \( g \) in the FoDS model. The error decays at a rate of \( N = O\left( \frac{d}{\epsilon} \right) \), where \( N \) is the number of samples, \( d \) is the dimension of the state variable, and \( \epsilon \) represents the desired estimation accuracy. Simulation results demonstrate that our theoretical bounds are tight, validating the accuracy and robustness of this algorithm.

I. INTRODUCTION

The paper proposes noisy-data identification for fractional-order dynamical systems, addressing prior methods’ difficulty with noise and high dimensionality. It also frames fractional-order modeling as a compact way to represent long-range dependence and develops the operator and system formulation used for identification.

I. INTRODUCTION

  • Fractional calculus models long-range, non-Markovian dependence compactly, motivating accurate FoDS parameter inference across biological, technological, and social systems.The cited applications include neural and brain-region networks, power grids, and social systems.Source: §I · p. 1
  • The proposed algorithm identifies unknown system orders with noisy data, addressing a prior polynomial-solving method that performs poorly under noise, especially in high dimensions.The prior method solves quadratic equations and checks candidate solutions against cubic polynomials.Source: §I · pp. 1–2
  • The paper derives expectation and probabilistic bounds for fractional-order estimation error, with sample complexity scaling as N = O(d/ϵ).The bounds assume prior knowledge of f and g.Source: §I · p. 2

A. Grunwald-Letnikov Operator

  • The Grunwald–Letnikov operator represents a fractional derivative as a finite difference whose order is a d-dimensional vector.Its coefficient matrix ψ(α, j) is diagonal.Source: A. Gr¨unwald-Letnikov Operator · p. 2

B. Discrete-time Fractional-Order Dynamical System

  • The FoDS state equation includes a term depending on past states, which makes the model suitable for non-Markovian and long-range-dependent processes.The state vector is x_k, and the equation includes f(x_k) and g(x_k)u_k.Source: B. Discrete-time Fractional-Order… · p. 2

C. FoDS Model Estimation

The estimation problem covers both known and unknown system functions under measurement noise, with the initial state noise-free. The proposed procedure generates data from designed experiments and estimates unknown parameters using least squares.

C. FoDS Model Estimation

  • The measurement-noise setup assumes a noise-free initial state x_0, with white Gaussian noise beginning at x_1.The unknown-functions problem also specifies estimation of the fractional order, f, and g.Source: C. FoDS Model Estimation · p. 2
  • Unlike the prior work cited as, this problem considers noisy data and includes sample-complexity analysis.The passage says the prior work neither considered noisy data nor analyzed sample complexity.Source: C. FoDS Model Estimation · p. 2

III. PARAMETER ESTIMATION

  • For unknown f and g, the proposed identification procedure generates experimental data and then estimates parameters by solving a least-squares problem.Problem 2 estimates the fractional order and both functions; it generalizes the known-functions Problem 1.Source: §III · p. 2, C. FoDS Model Estimation · p. 2

A. Data Generation

  • The data-generation description uses independent, identically distributed white Gaussian noise and a diagonal matrix A = diag(α_1, …, α_d).The generated state at the second time step corresponds to each initial condition.Source: A. Data Generation · pp. 2–3

B. Function Approximation

For unknown system functions, the paper approximates f and g with separate orthogonal basis sets and formulates coefficient estimation as least squares. The approach is illustrated for scalar input and can be generalized to higher input dimension; the known-functions case is handled by rearranging terms before least squares.

B. Function Approximation

C. System Identification with Unknown System Order

  • For unknown system order, the generated data are used to solve a least-squares problem over θ = [γ, β, α]^T and ξ = [π, ϕ, Ω].The passage defines Ω, π, and ϕ as matrices with dimensions determined by d, p, H, and L.Source: C. System Identification with Unknown… · p. 3
  • For known f and g, rearranging their terms to the left side of the data-generation equation reduces identification to least squares.This is the stated generalization of the proposed approach to Problem 1.Source: C. System Identification with Unknown… · p. 3

IV. SAMPLE COMPLEXITY ANALYSIS

The analysis asks how many noisy observations from a fixed initial condition are needed to bound estimation error, assuming known functions f and g. It formulates parameter estimation as least squares and leaves the corresponding analysis with unknown functions for future work.

IV. SAMPLE COMPLEXITY ANALYSIS

  • Sample-complexity analysis for the problem with unknown f and g, including function-approximation errors, is left for future work.Source: §IV · p. 3
  • With full knowledge of f and g, their terms are rearranged to the left side of the data-generation equation.Source: §IV · p. 3
  • The sample-complexity question is how many observations from a fixed initial condition are needed to keep estimation error below a specified threshold.Source: §IV · pp. 3–4
  • The model assumes white Gaussian noise with a diagonal covariance matrix.Source: §IV · p. 4
  • The parameter solution is obtained by least squares, using a matrix A containing N repetitions of C.Source: §IV · p. 4

A. Expectation Bound

The expectation-bound analysis considers the least-squares estimate of the fractional-order vector. It relates sample complexity to the order dimension, with the bound’s constant depending on noise covariance and the measurement matrix.

A. Expectation Bound

  • Theorem 1 gives an expectation bound for the least-squares solution β̂ = (C^T C)^-1 C^T Ȳ.Source: A. Expectation Bound · p. 4
  • The proof uses the Gaussian distribution of the estimation error, then applies a trace argument and Lemma 1 to obtain the expectation bound.Source: A. Expectation Bound · p. 4
  • Sample complexity scales with the fractional-order dimension, which is also the state-vector dimension; the constant depends on noise covariance K_w and measurement matrix C.Source: A. Expectation Bound · p. 4

B. High-probability Bound

The high-probability bound indicates that estimation errors above a threshold become exponentially less likely as the threshold increases, with decay shaped by noise, the measurement matrix, and fractional-order dimension. Simulations also report fractional-order estimates close to their target values using 100 samples.

B. High-probability Bound

  • The high-probability error bound’s decay rate depends on the noise level, measurement matrix, and fractional-order dimension.The proof whitens the error covariance and bounds a weighted sum of standard normal variables using a chi-squared distribution with d degrees of freedom.Source: B. High-probability Bound · p. 4
  • As the threshold increases, the probability that estimation error exceeds it becomes exponentially small.Source: B. High-probability Bound · p. 4
  • The appendix also gives a sub-exponential-based high-probability bound, but it is less tight than the Theorem 2 bound.Source: B. High-probability Bound · p. 4

V. SIMULATION

  • The simulations examine known and unknown f and g and show estimation error decreasing as the number of samples N increases.Source: §V · p. 4

A. Model Parameters Estimation

B. Numerical Results for Sample Complexity Analysis

The numerical results report close alignment between empirical estimation error and theoretical predictions. The conclusions describe an affine discrete-time identification method and note limits in sample-complexity analysis and basis selection.

B. Numerical Results for Sample Complexity Analysis

VI. CONCLUSIONS

  • The algorithm handles noisy data and known or unknown f and g, using least squares or basis-function approximations, respectively.It avoids solving higher-order polynomial equations by generating equations from different initial conditions.Source: §VI · p. 6
  • Expectation and high-probability bounds are provided for fractional-order identification when f and g are known.The sample-complexity analysis for unknown f and g is left to future work.Source: §VI · p. 6
  • Selecting appropriate basis functions can be risky and time-consuming in practice.The authors identify this challenge as a focus of continued research.Source: §VI · p. 6

APPENDIX I

The appendix derives an expectation bound for the least-squares parameter estimate using its error distribution, a trace inequality, and the repeated-design-matrix structure.

APPENDIX I

  • In the proof, the estimation error ˆβ − β is said to follow a Gaussian distribution, and the trace trick with Lemma 1 is used to derive an upper bound for E.Source: Appendix I · p. 6
  • In the least-squares setup, Y = [Y1, . . . , YN]T, A = [CT, CT, . . . , CT]T, and β = [α1, . . . , αd]T; A contains N repetitions of C.Source: Appendix I · p. 6

APPENDIX II

The appendix derives high-probability error bounds by whitening the Gaussian estimation error and relating its squared norm to a chi-squared variable.

APPENDIX II

  • The proof uses whitening to upper-bound the estimation error and applies chi-squared and sub-exponential concentration results.The appendix introduces lemmas for Gaussian and sub-exponential variables in deriving the high-probability bounds.Source: APPENDIX II · p. 7
  • Whitening the estimation error yields a standard normal vector whose squared norm follows a chi-squared distribution with d degrees of freedom.The error covariance is denoted Σ, and the whitened vector is V = Σ^-1/2 Z.Source: APPENDIX II · p. 7
Loading 2501.17499v1…