Imagine trying to map out the internal gears of a black box. You can feed inputs into the box and measure its outputs, but the internal state transitions remain completely hidden. In control theory and machine learning, this is the classic problem of system identification for a State-Space Linear Dynamical System (LDS):
$$x_{t+1} = Ax_t + Bu_t$$ $$y_t = Cx_t + Du_t$$
If we could directly observe the hidden states $x_t$, finding the matrices $A, B, C,$ and $D$ would be a straightforward linear regression problem. However, because $x_t$ is latent, optimizing these matrices directly from input-output data is highly non-convex and plagued by local minima. Furthermore, the internal state representation is never unique; any arbitrary coordinate transformation ($x_t \to Tx_t$) yields the exact same input-output behavior.
To solve this, a powerful paradigm bypasses the hidden states entirely during the initial learning phase. By focusing on purely observable input-output relationships—known as Markov parameters—and arranging them into a structured Hankel matrix, researchers can exploit fundamental rank conditions to uniquely recover the underlying state-space model.
Bypassing Hidden States with Markov Parameters
How do we bypass the non-convexity of latent states? The key insight is to look at the system's impulse response. If we unroll the state equations starting from an empty initial state ($x_0 = 0$), we can express any future output $y_t$ purely as a linear combination of past inputs:
$$y_t = D u_t + C B u_{t-1} + C A B u_{t-2} + C A^2 B u_{t-3} + \dots$$
We can rewrite this cleanly as:
$$y_t = \sum_{k=0}^\infty G_k u_{t-k}$$
where $G_0 = D$, and $G_k = CA^{k-1}B$ for $k \ge 1$. These matrix products $G_k$ are the Markov parameters of the system.
Because Markov parameters define a direct, linear mapping from observed history to future outputs, they can be estimated without ever worrying about the hidden state coordinate system. As shown by Lale et al., parameterizing a system this way allows practitioners to use regularized least-squares regression to achieve optimal learning rates, completely sidestepping the non-convexity of direct state-space identification.
Focusing on these finite-horizon input-output relationships yields massive computational advantages. Salar Fattahi demonstrates that by leveraging the inherent stability of physical systems, one can identify parameters with a sample size that scales logarithmically rather than linearly with the system's dimension. To make this process even more robust, Bakshi et al. leverage a method-of-moments approach on these parameters to provide the first polynomial-time algorithm for learning linear dynamical systems under nearly optimal conditions.
The Hankel Matrix and Realization Theory
Once we have estimated the Markov parameters $G_k$, how do we extract the actual internal state-space matrices $A, B,$ and $C$? This is the core question of realization theory. The magic happens when we arrange the estimated Markov parameters into a block-matrix called a Hankel matrix ($H$), where each anti-diagonal contains identical parameters:
$$H = \begin{bmatrix} G_1 & G_2 & G_3 & \dots \\ G_2 & G_3 & G_4 & \dots \\ G_3 & G_4 & G_5 & \dots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix}$$
To see why this matrix is so special, substitute the definition $G_k = CA^{k-1}B$ back into the grid. The entire matrix beautifully factorizes into the product of two massive structures—the extended observability matrix ($\mathcal{O}$) and the extended controllability matrix ($\mathcal{C}$):
$$H = \begin{bmatrix} C \\ CA \\ CA^2 \\ \vdots \end{bmatrix} \begin{bmatrix} B & AB & A^2B & \dots \end{bmatrix} = \mathcal{O}\mathcal{C}$$
If the true hidden state $x_t$ has a physical dimension of $n$, then $\mathcal{O}$ has exactly $n$ columns and $\mathcal{C}$ has exactly $n$ rows. By fundamental linear algebra, the rank of their product can never exceed $n$.
This factorization provides a definitive bridge between external observations and internal complexity. In foundational work on system structure, Mihaly Petreczky proved that the finite rank of this Hankel matrix serves as a necessary and sufficient condition for the existence of a finite-dimensional state-space realization. If the Hankel matrix derived from data has a finite rank $n$, it mathematically guarantees that the observed behavior can be perfectly captured by an $n$-dimensional state-space model, and that this model achieves minimal internal complexity.
Subspace Identification via Singular Value Decomposition
To turn this geometric insight into a practical algorithm, researchers use subspace system identification (SIM). As reviewed by Qin et al., subspace methods project observed data directly onto specific state subspaces to extract models, offering a more direct and reliable alternative to traditional iterative prediction error methods.
The standard algorithmic pipeline works by applying Singular Value Decomposition (SVD) to the Hankel matrix constructed from data:
$$H = U \Sigma V^T$$
By inspecting the singular values along the diagonal of $\Sigma$, we can immediately determine the true order of the system $n$ by looking for where the singular values drop close to zero. We then truncate the decomposition to retain only the top $n$ components, allowing us to isolate the observability matrix:
$$\mathcal{O} = U_n \Sigma_n^{1/2}$$
Once $\mathcal{O}$ is isolated, extracting the transition matrix $A$ becomes a simple linear shift-invariance problem: because the bottom rows of $\mathcal{O}$ are simply the top rows multiplied by $A$, we can solve for $A$ using standard least-squares.
This data-driven pipeline is backed by strong statistical guarantees. Tsiamis et al. provide a finite-sample analysis of this exact process for stochastic systems, proving that performing linear regression on past and future outputs followed by an SVD-based balanced realization allows parameter recovery errors to decay at a sharp $1/\sqrt{N}$ rate.
The framework is also highly versatile. For instance, Isufi et al. adapt subspace identification to graph signal processing, constructing Hankel-like matrices from signal trajectories to uncover the hidden topological "wiring" of networks from partial node observations.
Generalizing to Hybrid and Non-Linear Dynamics
The elegance of the Markov-Hankel framework is that its underlying realization logic survives even when systems exhibit switching behaviors or multiplicative non-linearities:
- Switched and Hybrid Systems: For systems that flip between different discrete linear modes over time, Mihaly Petreczky extended classical realization theory by defining generalized Hankel matrices derived from formal power series. The rank of these generalized matrices dictates whether a hybrid system can represent the data and determines the minimal number of continuous states required. When the discrete mode switches themselves are completely hidden, Sarkar et al. show that constructing stochastic Hankel matrices from the expectations of multi-run outputs still successfully reveals the minimal continuous state dimension.
- Bilinear Dynamics: When measurements or control inputs interact multiplicatively with the state, the system becomes bilinear. Sattar et al. demonstrate that bilinear systems can be identified by regressing on Kronecker products of past inputs. This extracts "Markov-like" parameters from a single trajectory, which are then passed to a realization algorithm to recover the state-space matrices, successfully decoupling input-output estimation from internal state representation.
- Linear Parameter-Varying (LPV) Systems: For systems whose dynamics evolve based on an external time-varying parameter, Mejari et al. use correlation analysis to estimate sub-Markov parameters—the time-varying equivalent of impulse responses. Petreczky et al. proved that arranging these sub-Markov parameters into a Hankel matrix yields the exact same necessary and sufficient finite-rank conditions needed to guarantee a minimal LPV realization.
Rank Conditions as the Ultimate Test for Identifiability
Ultimately, this entire line of research frames the question of identifiability—whether a model can be uniquely recovered from data—as a question of matrix rank. If a dataset lacks sufficient variation, or if a system is underdetermined, the corresponding matrices lose rank, signaling an information deficit.
[Raw Time-Series Data]
│
▼
[Estimate Markov Parameters] ───► Bypasses non-convex hidden states
│
▼
[Construct Hankel Matrix]
│
▼
[Evaluate Rank Conditions] ───► Verifies if system is uniquely identifiable
│
▼
[SVD / Subspace Extraction] ───► Uniquely recovers internal state-space matrices
This rank-based diagnostic tool applies across diverse domains:
- Behavioral Systems: Ivan Markovsky provides a precise behavioral threshold, showing that a linear system is uniquely identifiable if and only if the rank of its data's Hankel matrix matches a specific function of the system's order, inputs, and lag.
- Network Monitoring: Qing-Guo Wang demonstrates that a specific hidden variable in a network is uniquely identifiable if and only if the rank of the system matrix drops by exactly one when its corresponding column is removed.
- Stochastic and Continuous Models: Similar rank conditions govern the unique recovery of generators for stochastic differential equations (Wang et al.), continuous Lyapunov models (Dettling et al.), and even hidden reward functions in inverse reinforcement learning (Rolland et al.).
By shifting the problem from non-convex optimization over hidden states to rank evaluations of structured input-output matrices, this paradigm provides both the mathematical guarantees and the practical algorithms needed to look inside the black box.
Key Foundational Work
Realization theory for linear and bilinear switched systems: a formal power series approach (2005) — contributed 2 concept elements to this direction.
Realization theory for linear and bilinear hybrid systems (2005) — contributed 2 concept elements to this direction.
Realization theory for linear switched systems (2004) — contributed 2 concept elements to this direction.