Optimal Centered Active Excitation in Linear System Identification

Optimal centered active excitation in linear system identification addresses how to design input sequences to estimate unknown system matrices efficiently, providing tight sample complexity bounds for algorithms that adapt their excitation based on observed data. This work establishes lower bounds for any algorithm using active excitation and proposes a computationally efficient algorithm based on the Least Squares Estimator (LSE) that matches these optimal bounds under specific assumptions.

The gist

We derive sample complexity lower bounds satisfied by any algorithm using active excitation and achieving prescribed accuracy and confidence levels, parameterized by (ε, δ).

Problem Setting and Lower Bounds

The paper considers a discrete-time linear system defined by state dynamics: xt+1 = Axt + But + wt. The central goal is to estimate the unknown system matrix A. The analysis focuses on algorithms with adaptive excitation, which involves a control policy defining the conditional distribution of the input, and an estimate of A. The core lower bound derived for any (ε, δ)-locally stable algorithm with centered excitation is: λmin τXA−1s=1Σs! ≥ 1/2ε2 log 1/3δ. This bound exhibits a tight dependence on the state dimension when considering power-constrained excitation.

Proposed Algorithm and Optimization Strategy

The authors propose an active learning algorithm based on the LSE, which is designed to be computationally efficient. The key steps involve:

1. An initial phase where A is estimated using a predetermined input covariance (e.g., (¯u/nx)I).

2. A projection step to ensure stability: A¯t0 ← Π(Abt0) if the estimate is unstable, ensuring the resulting matrix is stable and the error term kAbt0 − A¯t0 k is small as possible.

3. An adaptive phase where the input covariance Ub is updated to maximize a surrogate objective: Ub ∈ arg max U0,tr(U)≤u¯ λminΓ∞(A¯t0) + Ξ∞(A¯t0, U) under the constraint tr(Ub) ≤ u.

4. Resetting the state and continuing excitation using the designed covariance Ub for subsequent steps.

Sample Complexity Upper Bound and Performance Guarantee

The paper establishes a sample complexity upper bound for this proposed algorithm (Algorithm 1) under Assumption 8 (Sub-Gaussianity of the noise input). The resulting upper bound is given by Equation (15), which is structured to match the lower bound: the third term in (15) is minimized by t0 = Θ((t − 1)2/3), and its minimum value is Θ((t − 1)2/3). For small ε and δ, this upper bound coincides with the lower bound (10) up to multiplicative and additive factors.

Key Theoretical Results

The analysis relies on several theoretical results to bridge the gap between the general lower bounds and the specific algorithm:

Proposition 10 (LSE performance)

This proposition provides a performance guarantee for the LSE when using a fixed excitation covariance U, stating that error bounds are satisfied if λmin Xt−1s=1Σs! ≥ C max 1/ε2 kΓU k2 log 1/δ + nx.

Proposition 5 (Lower bound for stable A and small ε)

This theorem provides a tighter lower bound when the system matrix A is stable, showing explicit dependence on the state dimension nx in the form: λmin τXA−1s=1Σs! ≥ c (1 + kBk2u¯)ε2 log 1/δ + nx.

Corollary 7

This corollary provides a practical bound for the sample complexity of algorithms using centered power-constrained excitation, showing it satisfies: τA − 1 ≥ c (1 + kBk2u¯)ε2 max U0,tr(U)≤u¯ λmin(Γ∞(A) + Ξ∞(A, U)) × log 1/δ + nx.

Numerical Validation

The paper validates the algorithm through numerical experiments. Using a Jordan block as a typical example for A, simulations show that after an initial horizon of t0 = 850, the error of Algorithm 1 rapidly approaches that of the oracle method, and at time t = 25000, the mean and percentiles closely match those obtained by using an oracle noise input. This confirms that the proposed active learning algorithm achieves a nearly optimal sample complexity.

Conclusion

The work concludes by demonstrating that Algorithm 1 yields a sample complexity upper bound (15) that matches the lower bound (10) up to factors independent of (ε, δ), nx, and A in a regime where ε is small.

Based on the provided scientific paper, here are the specific improvements for AI systems and what those improved systems can achieve:

---

)Improved AI System Capabilities

The proposed framework enables a class of active learning algorithms for linear system identification that achieves minimal sample complexity while maintaining strong finite-time statistical guarantees. Specifically, these improvements apply to:

1. Online/Adaptive Control and System Tuning: The system can dynamically adapt its internal model (represented by the state-space matrix, A) in real-time as it processes incoming data streams, rather than relying on a fixed or passively excited input sequence.

2. Efficient Model Estimation under Constraints: The algorithm can accurately estimate the unknown system dynamics (parameters of the linear model) using significantly fewer samples than traditional methods that require passive excitation or non-convex optimization.

3. Guaranteed Performance in Finite Time: Unlike many identification methods that only provide asymptotic convergence guarantees, this system maintains a quantifiable error bound with high confidence levels within a finite time horizon, which is crucial for safety-critical applications.

)Specific System Improvements and Applications

The core improvements translate to the following specific capabilities for AI systems:

1. Autonomous Robotics and Control Systems:

Adaptive control policies in robots (e.g., drones, humanoid arms) can use this method to rapidly identify or compensate for unknown dynamics (like unexpected friction changes or payload variations) by actively designing the next input signal to maximize information gain about the system matrix A. This allows for on-the-fly tuning of the control law without requiring a full system re-identification phase.

2. Adaptive Machine Learning Models (System Identification in ML):

Adaptive identification methods can be used to quickly estimate the underlying dynamics of complex non-linear or high-dimensional models (when linearized) encountered during training, allowing the AI to adjust its learning rate or regularization based on how well the current input excites the system's latent space.

3. Resource-Constrained Data Collection: In scenarios where data collection is expensive or time-limited (e.g., rare event detection, satellite communication), this method ensures that every collected sample is optimally designed to reduce uncertainty about the system parameters A, leading to faster convergence of the AI's decision-making process with minimal required interaction with the physical environment.

4. Safety and Robustness in Dynamic Environments: For systems operating in uncertain environments (e.g., autonomous vehicles navigating unknown terrain), the ability to maintain a bounded estimation error while actively probing for system uncertainties ensures that critical safety guarantees are met even when the system dynamics are not perfectly known beforehand.