Research map / Learning theory and algorithms / Sample complexity
Stabilizing LTI Systems under Partial Observability: Sample Complexity and Fundamental Limits
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes LTS-P, which estimates the unstable component of an unknown partially observable LTI system via compressed SVD of a lifted Hankel matrix and designs an H-infinity controller, giving dimension-free sample complexity that scales with the number of unstable modes.
Problem
Stabilizing an unknown, partially observable, unstable LTI system without an initial stabilizing controller, with sample complexity independent of the state dimension n (ideally depending only on the number of unstable modes k).
Approach
Define the unstable component as the low-rank transfer function retaining only unstable eigenvalues; estimate it from a lifted Hankel matrix via rank-k SVD, recover a realization up to a similarity transform, and synthesize an H-infinity robust controller that stabilizes the full system via the small-gain theorem under an H-infinity-norm condition on the stable component.
Key results
- Theorem gives sample complexity MT = (3m+2)M = O(alpha^2)=O(k^2) with m, M set by unstable-mode gaps and system-theoretic parameters, independent of state dimension n.
- In simulations with k=5 unstable modes, LTS-P requires the shortest rollouts and fewest rollouts compared to nuclear norm regularization and Ho-Kalman across dimensions n, under noise levels 0.4, 0.6, 0.8.
- Non-diagonalizable N_1 with largest Jordan block size k worsens the bound to tilde O(k^4), still independent of n.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Estimate and stabilize only the unstable component instead of identifying the full system | LTS-P · Partially observable LTI stabilization | sample complexity: O(k^2), independent from system state dimension n | Helped |
| Use LTS-P rather than nuclear norm regularization or Ho-Kalman | LTS-P · Simulation: rollout length needed for stabilization | rollout length | Helped |
| Use LTS-P rather than nuclear norm regularization or Ho-Kalman | LTS-P · Simulation: number of rollouts needed for stabilization | number of rollouts | Helped |
Limitations
- Requires a small-gain assumption on the H-infinity norm of the stable component, which is necessary for the approach that treats the stable part as unknown.
- Fails to offer improvement when k approaches n.
- Non-diagonalizable unstable dynamics incur extra factors in the sample complexity (up to k^4).
Experimental setup
Metrics: rollout length needed to stabilize number of rollouts needed to stabilize
Baselines: nuclear norm regularization Ho-Kalman algorithm
Builds on: unstable/stable subspace decomposition for fully observable LTI stabilization Ho-Kalman algorithm small gain theorem
Closest papers by meaning
- On the Sample Complexity of Stabilizing LTI Systems on a Single Trajectory (NeurIPS 2022 · similarity 0.91)
- Just Few States Are Enough: Randomized Sparse Feedback for Stability of Dynamical Systems (AAAI 2026 · similarity 0.86)
- Near optimal finite time identification of arbitrary linear dynamical systems (ICML 2019 · similarity 0.86)
- Stabilizing Dynamical Systems via Policy Gradient Methods (NeurIPS 2021 · similarity 0.84)
- A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems (NeurIPS 2026 · similarity 0.84)
- FESSNC: Fast Exponentially Stable and Safe Neural Controller (ICML 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.