Source-linked AI summary
Extracting Sparse High-Dimensional Dynamics from Limited Data
Hayden Schaeffer, Giang Tran, Rachel Ward
TL;DR
The paper addresses recovery of sparse governing equations from under-sampled dynamical data, where the equation form is not known in advance. It develops three sampling strategies combined with compressive-sensing optimization, and shows exact recovery for sparse quadratic systems, including noisy velocity estimates. The approach is constrained by trajectory-boundedness assumptions and can become costly for higher-order systems with many basis elements.
Problem
Recovering governing equations from dynamic data is difficult when the equation form is unknown and fewer samples than candidate functions are available.
Method
The paper combines sparse optimization with three sampling strategies for learning quadratic differential equations from under-sampled trajectory bursts.
Results
Sparse quadratic governing equations are recovered exactly with high probability from randomly initialized bursts, and the formulation accommodates approximate velocity measurements.
Takeaways & Limitations
Sampling requirements can be reduced by using prior structure in the governing equation or chaotic behavior in the observed data.
Takeaways & Limitations
The guarantees assume bounded measurement matrices and short-time trajectories, while higher-order systems can make the basis extremely large and reconstruction costly.
Abstract
from arXiv · showhide
Extracting governing equations from dynamic data is an essential task in model selection and parameter estimation. The form of the governing equation is rarely known a priori; however, based on the sparsity-of-effect principle one may assume that the number of candidate functions needed to represent the dynamics is very small. In this work, we leverage the sparse structure of the governing equations along with recent results from random sampling theory to develop methods for selecting dynamical systems from under-sampled data. In particular, we detail three sampling strategies that lead to the exact recovery of first-order dynamical systems when we are given fewer samples than unknowns. The first method makes no assumptions on the behavior of the data, and requires a certain number of random initial samples. The second method utilizes the structure of the governing equation to limit the number of random initializations needed. The third method leverages chaotic behavior in the data to construct a nearly deterministic sampling strategy. Using results from compressive sensing, we show that the strategies lead to exact recovery, which is stable to the sparse structure of the governing equations and robust to noise in the estimation of the velocity. Computational results validate each of the sampling strategies and highlight potential applications.
1 Introduction
The paper develops sparse model-selection methods for identifying high-dimensional quadratic differential equations from under-sampled data. Compressive sensing and sampling theory support exact recovery despite fewer samples than unknowns.
- High-dimensional dynamical systems are difficult to model manually because data analysis becomes time-consuming, expensive, and infeasible as system dimension grows.
- Sparse quadratic governing equations allow recovery from roughly as many samples as the system’s sparsity level.The method solves a sparse optimization problem over many candidate functions.
- The proposed method learns quadratic differential equations from under-sampled data using compressive sensing and sampling theory.
- Three sampling strategies differ according to prior knowledge of the data or governing equation, with additional assumptions reducing the required samples.
- The approach extends beyond quadratic systems to higher-order polynomials and equations sparse in bounded orthogonal systems.
2 Problem Statement
The problem is to recover unknown quadratic governing equations from short trajectory bursts and corresponding velocities. The resulting underdetermined inverse problem is regularized by sparse optimization in monomial or Legendre polynomial bases.
- The goal is to learn unknown functions f_1, ..., f_n from measured states x and velocities ẋ.
- A burst consists of a small number of discrete measurements along one trajectory, obtained from simulations or observations.
- Each burst supplies state snapshots, corresponding velocities, and trial-function evaluations used to construct measurement and velocity matrices.
- Combining bursts yields the linear inverse problem V = AC, where A has mK rows and N quadratic monomial columns.
- Because mK < N, sparse coefficient recovery uses ℓ1 basis pursuit with a tolerance for velocity-estimation error.The non-convex ℓ0 problem is replaced by a convex relaxation.
- The same procedure can use monomial basis pursuit or Legendre basis pursuit, with the latter potentially increasing sparsity by one.
3 Reconstruction Guarantee
Compressive-sensing guarantees show that sparse quadratic systems can be recovered from randomly initialized bursts even when the inverse problem is underdetermined. The guarantees depend on sparsity, sampling structure, and boundedness assumptions, with extensions to broader bases and polynomial degrees.
- Underdetermined linear systems can recover sparse coefficients when the measurement matrix has suitable incoherence properties.
- Independent random initializations produce Legendre measurement rows with isotropic structure supporting sparse-recovery guarantees.
- With probability 1 − ε, each sparse quadratic governing component is recovered exactly as the unique solution to Legendre basis pursuit.
- The recovery guarantee remains applicable when measured gradients are approximate, using a noise-tolerant formulation.
- At least 9c*s log(N) log(nε^-1) random bursts provide uniform error guarantees across n equations under the stated assumptions.The initial data can be uniformly random on [−1, 1]^n, while trajectories are expected to exist for only a short time because polynomial systems may become unbounded.
- The framework extends to higher-order polynomials and other bounded orthogonal bases, but cubic systems can make N extremely large and ℓ1 reconstruction costly.
4 Ergodicity and the Number of Bursts
Chaotic behavior can reduce the number of bursts needed for exact recovery. When observations have weak temporal correlations, a single burst may provide sampling conditions close to those required by compressive sensing.
- A worst-case theorem guarantees exact recovery from randomly initialized bursts, with burst count scaling sparsity-wise and logarithmically with ambient dimension.The guarantee does not depend on trajectory behavior along the bursts.
- Chaotic trajectories can make the observed sequence resemble random samples, so numerical evidence indicates that one burst often suffices.
- For chaotic systems, smooth observables satisfy a deterministic law of large numbers through the Birkhoff Ergodic Theorem.Time averages converge to space averages under an underlying invariant measure.
- Fast decay of correlations makes rows of the sampling matrix weakly correlated, bringing a single-burst design closer to compressive-sensing requirements.
5 Sampling Strategies and Computational Results
The paper presents three sampling strategies for exact recovery from under-sampled dynamical data, differing in whether they use no trajectory assumptions, localized equation structure, or chaotic trajectories. Computational tests on Lorenz 96 and Fisher’s equation validate recovery, localization gains, and noise behavior.
- Sampling strategies: Three strategies provide exact recovery with high probability: unrestricted random initialization, localized sampling, and chaotic-trajectory sampling.The first uses no trajectory or support assumptions; the second exploits local support; the third uses chaotic trajectories to reduce random initializations.
- Strategy 1: K = 80 achieves 90% recovery probability for Lorenz 96 at dt = 0.001 with m = 5 or m = 10, whereas K = 130 is needed at dt = 0.01 with m = 5.Larger time steps produce less accurate derivative estimates, and recovery can degrade as burst size and time-step propagation increase.
- Strategy 1: Fisher’s equation recovery selects the correct basis terms and accurately estimates parameters across γ values using n = 200, K = 159, and burst size m = 5.The results remain relatively stable even as decreasing γ increases the relative scale between the largest and smallest coefficients.
- Measurement noise: For state-space noise under 5%, recovery is stable; after 5% the ℓ2 error jumps, and after 6% the support set is not reliably recovered.The support check compares the four largest learned coefficients with the true four-term support.
6 Conclusion and Discussion
The paper develops compressive-sensing-based sampling strategies for recovering high-dimensional governing equations from under-sampled data. Recovery requirements depend on prior knowledge of the dynamics, locality in the governing equations, or chaotic temporal behavior.
- The proposed strategies recover governing equations when the number of measurements is smaller than the number of unknowns.
- With no assumptions about trajectory evolution, randomizing the initial data is sufficient for recovery.
- Locality in the governing equations reduces the required random initial data to a number nearly independent of system dimension.
- Chaotic or weakly temporally correlated data can reduce the number of initial samples to a fixed number.
Appendix
The appendix connects random sampling of bounded orthonormal systems with sparse recovery guarantees and applies these results to the Legendre-basis representation of quadratic dynamical systems. The stated noise experiment reports stability below 5% noise and degradation at 5%.
- At 5% noise, the relative ℓ2 error jumps and the recovered coefficient vector becomes polluted by noise-induced inaccuracies.
- Random sampling matrices permit stable recovery of sufficiently sparse vectors from highly underdetermined systems using ℓ1 minimization.
- The recovery proposition bounds reconstruction error for noisy measurements using the noise level and the best s-sparse approximation error.
- Legendre polynomials up to degree 2 form a bounded orthonormal system with constant B = 3 over the sampling domain.
- If each coefficient column has at most s nonzero terms, its Legendre-basis representation has at most s′ = s + 1 nonzero terms.
- The noiseless recovery guarantee extends from burst-specific constraints to the full measurement set through the inclusion of feasible domains.