Multi-view Matrix Factorization for Linear Dynamical System Estimation

Mahdi Karami, Martha White, Dale Schuurmans, Csaba SzepesváriNeurIPS 2017 · OpenReview

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:

  1. 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.
  2. 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)
Two-view graphical model of a Linear Dynamical System

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).

Performance comparison on real-world climate datasets

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

Abstract

We consider maximum likelihood estimation of linear dynamical systems with generalized-linear observation models. Maximum likelihood is typically considered to be hard in this setting since latent states and transition parameters must be inferred jointly. Given that expectation-maximization does not scale and is prone to local minima, moment-matching approaches from the subspace identification literature have become standard, despite known statistical efficiency issues. In this paper, we instead reconsider likelihood maximization and develop an optimization based strategy for recovering the latent states and transition parameters. Key to the approach is a two-view reformulation of maximum likelihood estimation for linear dynamical systems that enables the use of global optimization algorithms for matrix factorization. We show that the proposed estimation strategy outperforms widely-used identification algorithms such as subspace identification methods, both in terms of accuracy and runtime.
BibTeX
@inproceedings{karami2017multi,
  author = {Mahdi Karami and Martha White and Dale Schuurmans and Csaba Szepesvári},
  title = {{Multi-view Matrix Factorization for Linear Dynamical System Estimation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=r1-DNP-d-r},
}
Figure