Research map / Learning theory and algorithms / Sample complexity
Learning Low-dimensional Latent Dynamics from High-dimensional Observations: Non-asymptotics and Lower Bounds
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 a two-stage (column-space PCA then Ho-Kalman) algorithm for LTI systems with high-dimensional observations achieving O~(n/eps^2) sample complexity, proves a matching lower bound, and extends to meta-learning across systems sharing an observer.
Problem
Learning partially observed linear time-invariant systems with low-dimensional latent states but high-dimensional noisy observations, where standard system identification has sample complexity scaling with the observation dimension n times a polynomial in latent and input dimensions.
Approach
Estimate the observer column space by PCA on a first trajectory, project a second trajectory to low dimension, run a standard SYSID oracle (Ho-Kalman) there, and lift the observer back; the analysis uses martingale tools and a tailored relative subspace perturbation bound, and a meta-version leaves one system out to estimate the shared column space.
Key results
- Col-Approx subspace error decreases with trajectory length for isotropic observation noise (n=40 to 320, T=10000), but fails to converge for non-isotropic noise.
- Col-Algo outperforms standard Ho-Kalman in the first Markov parameter error for n=320, T=10000 in simulation.
- Meta-Algo keeps average learning error below 0.2 across n in [80,320], while standard Ho-Kalman error grows significantly with n.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use COL-ALGO instead of applying the example oracle directly to high-dimensional observations | HDSYSID with r,m≪n · HDSYSID | sample complexity: \tilde{\calO}(nr^5/\epsilon^2) -> \tilde{\calO}(n/\epsilon^2) | Helped |
| Use COL-ALGO with observation noise | HDSYSID · HDSYSID with observation noise | sample complexity: \tilde{\calO}(n/\epsilon^2); lower bound \calO(n/\epsilon^2) | Mixed |
| Remove observation noise | COL-ALGO · HDSYSID without observation noise | sample complexity: \tilde{\calO}([n + \poly\b{r,m}]/\epsilon^2) -> \tilde{\calO}(\poly\b{r,m}/\epsilon^2) | Helped |
| Use metadata from other systems to estimate the shared observer column space | META-ALGO · Meta SYSID | samples required from system k₀: T_{k_0} = \tilde{\calO}(\poly\b{r,m}/\epsilon^2), T_{-k_0} = \tilde{\calO}(n/\epsilon^2) | Helped |
| Use isotropic rather than non-isotropic observation noise | Col-Approx · Column-space estimation | column-space error | Helped |
| Use non-isotropic observation noise with covariance \Phi_C\Phi_C^\t | Col-Approx · Column-space estimation | column-space error | Hurt |
| Use COL-ALGO rather than standard Ho-Kalman | HDSYSID simulation, n=320 · CB estimation | CB estimation error | Helped |
| Use META-ALGO rather than standard Ho-Kalman | Meta SYSID simulation · n∈[80, 320] | CB estimation error: average learning error always stays below 0.2 | Helped |
| Learn each system independently instead of sharing observer information across the meta-dataset | Standard Ho-Kalman · Meta SYSID simulation, n∈[80, 320] | CB estimation error | Hurt |
Surprising findings
- The column-space estimator fails under non-isotropic observation noise, showing that the isotropy assumption is essential.
Limitations
- Assumes isotropic observation noise; non-isotropic noise breaks the column-space estimator.
- Restricted to stable latent dynamics (spectral radius below 1).
- Requires two independent trajectories (or a dependent-noise oracle) for the projection step.
Experimental setup
Datasets: simulated LTI system trajectories
Benchmarks: simulated LTI systems
Metrics: subspace error ||Phi_hat_perp^T Phi_C|| Markov parameter error ||C_hat B_hat - C B||
Baselines: standard Ho-Kalman
Builds on: Ho-Kalman algorithm PCA subspace learning
Closest papers by meaning
- Modeling Latent Non-Linear Dynamical System over Time Series (AAAI 2025 · similarity 0.87)
- Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamics (ICLR 2025 · similarity 0.86)
- Learning Hybrid Dynamics Models with Simulator-Informed Latent States (AAAI 2024 · similarity 0.86)
- Extracting Governing Equations from Latent Dynamics via Multi-View Contrastive Learning (NeurIPS 2026 · similarity 0.86)
- Identifying latent state transitions in non-linear dynamical systems (ICLR 2025 · similarity 0.86)
- Probabilistic Decomposed Linear Dynamical Systems for Robust Discovery of Latent Neural Dynamics (NeurIPS 2024 · similarity 0.85)
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.