Linear Dynamical Systems (LDS) are the bread and butter of time-series analysis. They are widely used to model how hidden states evolve over time to produce observable data—for instance, tracking a planet's position based on noisy telescope images or predicting weather patterns from sensor grids. However, "identifying" the system (estimating the transition and observation matrices from data) is notoriously difficult.
Historically, researchers have had to choose between two sub-optimal paths:
- Maximum Likelihood Estimation (MLE): Statistically powerful but computationally a nightmare. Standard tools like Expectation-Maximization (EM) are slow, scale poorly, and often get stuck in local minima, yielding mediocre solutions.
- Subspace Identification (e.g., N4SID): Fast and based on simple linear algebra (like Singular Value Decomposition), but statistically weak. These methods often perform poorly when data is limited or high-dimensional.
This paper introduces a novel "third way": an approach to estimating LDS by reformulating the problem as a "two-view" matrix factorization task. By leveraging global optimization techniques, the authors achieve the statistical accuracy of maximum likelihood estimation with significantly better computational scaling and stability than traditional methods.
The Two-View Reformulation
The core innovation of this paper is transforming a sequential, temporal estimation problem into a static matrix factorization problem.
In a standard LDS, an observation $x_t$ is generated from a hidden state $\phi_t$. The authors realized that if you look at a pair of sequential observations $(x_t, x_{t+1})$, you can treat them as two different "views" of the same latent state $\phi_t$:
- View 1: $x_t \approx C\phi_t$
- View 2: $x_{t+1} \approx (CA)\phi_t$ (where $A$ is the transition matrix)
By defining a new matrix $E = CA$, the problem becomes a matrix factorization task: find $C$, $E$, and the states $\Phi$ that best reconstruct the data. This "aha moment" allows the use of powerful optimization tools originally developed for image processing and recommender systems.
Key Technical Contributions
To solve this new formulation effectively, the authors introduce several technical improvements:
- Convex Relaxation: They use a block norm ($\|\Phi\|_{2,1}$) to encourage row-wise sparsity in the latent states. This effectively performs "automatic rank selection," finding the simplest hidden state dimension that explains the data and preventing overfitting to noise.
- Novel Proximal Update: To solve the resulting optimization problem, they use the Generalized Conditional Gradient (GCG) algorithm. Crucially, they derive a closed-form solution for the proximal operator of their specific regularizer. This allows for a "local improvement" step that drastically speeds up convergence.
- Stability: Instead of deriving the transition matrix $A$ algebraically ($A = C^\dagger E$), which can be numerically unstable, they learn $A$ via simple linear regression on the recovered hidden states.
Experimental Results
The authors evaluated their algorithm (LDS-DV) against several baselines (N4SID, EM, PEM, HSE-HMM) using both synthetic datasets and real-world climate data (monthly surface temperatures for the Tropical Atlantic and Tropical Pacific oceans).
The results demonstrate significant improvements across the board:
- Superior Accuracy: On the climate datasets, LDS-DV consistently achieved lower Normalized Mean Square Error (NMSE) than all competitors. For example, on the "CAC (Short)" dataset, LDS-DV achieved an NMSE of 0.63, while N4SID trailed at 0.84.
- Dramatic Speedups: LDS-DV is significantly faster, especially as the data dimension grows. In the "ATL (Long)" test, LDS-DV finished in just 0.26 seconds, compared to 2.34 seconds for N4SID and 7.87 seconds for EM.
- Sample Efficiency: The proposed method maintains high accuracy even when the training sequence is very short. In contrast, traditional subspace methods like N4SID see their error spike significantly in small-sample regimes.
Limitations and Future Work
While highly effective, the authors note a few areas for future exploration. Currently, the noise covariance matrices are estimated from residuals after the states and transitions are found; joint estimation of noise parameters remains an open issue. Additionally, while the method performs well empirically, a formal proof of the "consistency" of the learned parameters (whether they converge to the true values as data goes to infinity) is left for future work. Finally, while the framework theoretically supports other exponential families (like Poisson for count data), the current experiments focused primarily on Gaussian noise.
Summary updated