Latent variable graphical model selection via convex optimization

Venkat Chandrasekaran, Pablo A. Parrilo, Alan S. WillskyThe Annals of Statistics 2012 · DOI · arXiv

Abstract

Suppose we observe samples of a subset of a collection of random variables. No additional information is provided about the number of latent variables, nor of the relationship between the latent and observed variables. Is it possible to discover the number of latent components, and to learn a statistical model over the entire collection of variables? We address this question in the setting in which the latent and observed variables are jointly Gaussian, with the conditional statistics of the observed variables conditioned on the latent variables being specified by a graphical model. As a first step we give natural conditions under which such latent-variable Gaussian graphical models are identifiable given marginal statistics of only the observed variables. Essentially these conditions require that the conditional graphical model among the observed variables is sparse, while the effect of the latent variables is “spread out” over most of the observed variables. Next we propose a tractable convex program based on regularized maximum-likelihood for model selection in this latent-variable setting; the regularizer uses both the $\ell_{1}$ norm and the nuclear norm. Our modeling framework can be viewed as a combination of dimensionality reduction (to identify latent variables) and graphical modeling (to capture remaining statistical structure not attributable to the latent variables), and it consistently estimates both the number of latent components and the conditional graphical model structure among the observed variables. These results are applicable in the high-dimensional setting in which the number of latent/observed variables grows with the number of samples of the observed variables. The geometric properties of the algebraic varieties of sparse matrices and of low-rank matrices play an important role in our analysis.

Introduction

In modern data science, the assumption that all relevant variables have been measured is often a luxury. In fields ranging from finance to psychology, observed correlations are frequently driven by unmeasured "latent" factors—such as market sentiment or general intelligence. When these hidden variables are ignored, standard statistical tools like the Graphical Lasso (GLasso) often fail, producing dense and uninterpretable networks.

This paper by Chandrasekaran et al. (2012) provides a rigorous theoretical and algorithmic foundation for addressing this challenge. By framing model selection as a convex optimization problem, the authors demonstrate how to simultaneously identify the number of hidden factors and the underlying sparse network structure among observed variables.

The Problem: Spurious Correlations and the Schur Complement

In a standard Gaussian Graphical Model (GGM), the concentration matrix (the inverse of the covariance matrix) reveals conditional dependencies. An entry of zero signifies that two variables are conditionally independent. However, when latent variables are present, the marginal concentration matrix of the observed variables ($\tilde{K}_O$) is transformed via the Schur complement:

$$\tilde{K}_O = K_O - K_{OH} K_H^{-1} K_{HO}$$

This marginalization "spreads" the influence of hidden variables across the entire observed network. Consequently, a graph that is sparse in the full variable space appears dense in the observed space, filled with spurious correlations. The challenge is to distinguish between a direct dependency (a link in the sparse graph) and a correlation induced by a shared hidden factor.

The Sparse-plus-Low-Rank Framework

The authors propose that the observed concentration matrix can be decomposed into two distinct components:

  1. $S$ (Sparse): This matrix represents the conditional dependencies between observed variables. If the underlying model is a graphical model, $S$ should be sparse.
  2. $L$ (Low-Rank): This matrix summarizes the effect of the $h$ latent variables. If the number of latent variables is small relative to the number of observed variables, $L$ will have a low rank.

By expressing the observed precision as $\tilde{K}_O = S - L$, the problem of model selection becomes a matrix decomposition task.

Optimization via Convex Programming

To recover $S$ and $L$ from empirical data, the authors introduce a regularized maximum-likelihood approach. Unlike traditional Expectation-Maximization (EM) methods, which are non-convex and prone to local optima, this formulation is a tractable convex program:

$$\min_{S, L} -\ell(S - L; \Sigma^n_O) + \lambda_n (\gamma \|S\|_1 + \text{tr}(L))$$

In this objective function:

  • $-\ell$ is the Gaussian log-likelihood.
  • $\|S\|_1$ (the $\ell_1$ norm) encourages sparsity in the conditional dependency graph.
  • $\text{tr}(L)$ (the nuclear norm or trace) encourages $L$ to be low-rank.
  • $\gamma$ serves as a trade-off parameter between the sparsity of the graph and the rank of the latent space.

Geometric Identifiability and Consistency

A significant contribution of this work is the rigorous proof of algebraic consistency. The authors use the geometry of algebraic varieties to define when $S$ and $L$ can be uniquely separated. They identify two key conditions for identifiability:

  1. Bounded Degree: The sparse graph must not be too "bunched up" or locally dense.
  2. Incoherence: The effect of latent variables must be "diffuse," meaning they influence many observed variables rather than being concentrated on a small subset.

If these conditions are met, the algorithm is guaranteed to find the exact number of latent variables and the correct edge structure as the sample size increases, even in high-dimensional settings where the number of variables grows with the number of samples.

Empirical Results

Synthetic Validation

The authors tested the framework on 36-node Gaussian models (including cycles and grids) with 1 to 3 latent variables. The results confirmed that the algorithm consistently recovers the correct model structure and latent count as the sample size $n$ increases.

Financial Modeling: S&P 100

The method was applied to monthly return data for 84 companies in the S&P 100 (1990–2007).

  • Latent Discovery: The model identified 5 latent variables and 135 conditional edges.
  • Performance: The latent-variable model achieved a KL divergence of 17.7, significantly outperforming a standard sparse model (no latents), which had a divergence of 44.4.
  • Interpretation: This suggests that global market factors are far more efficient at explaining stock correlations than a complex web of direct company-to-company dependencies.

Discussion and Limitations

While the paper provides a powerful framework for dimensionality reduction and graphical modeling, it has limitations. The assumption of joint Gaussianity is central to the math; extending this to discrete or non-Gaussian data remains an open challenge. Furthermore, while the optimization is convex, solving "max-det" problems for thousands of variables is computationally expensive, requiring specialized first-order algorithms for scale.

Ultimately, this work popularized the "Sparse + Low-Rank" paradigm, influencing subsequent developments in robust PCA and signal processing by demonstrating that latent structures are not just nuisances, but identifiable components of statistical models.

Summary updated

Abstract

Suppose we observe samples of a subset of a collection of random variables. No additional information is provided about the number of latent variables, nor of the relationship between the latent and observed variables. Is it possible to discover the number of latent components, and to learn a statistical model over the entire collection of variables? We address this question in the setting in which the latent and observed variables are jointly Gaussian, with the conditional statistics of the observed variables conditioned on the latent variables being specified by a graphical model. As a first step we give natural conditions under which such latent-variable Gaussian graphical models are identifiable given marginal statistics of only the observed variables. Essentially these conditions require that the conditional graphical model among the observed variables is sparse, while the effect of the latent variables is “spread out” over most of the observed variables. Next we propose a tractable convex program based on regularized maximum-likelihood for model selection in this latent-variable setting; the regularizer uses both the $\ell_{1}$ norm and the nuclear norm. Our modeling framework can be viewed as a combination of dimensionality reduction (to identify latent variables) and graphical modeling (to capture remaining statistical structure not attributable to the latent variables), and it consistently estimates both the number of latent components and the conditional graphical model structure among the observed variables. These results are applicable in the high-dimensional setting in which the number of latent/observed variables grows with the number of samples of the observed variables. The geometric properties of the algebraic varieties of sparse matrices and of low-rank matrices play an important role in our analysis.
BibTeX
@article{chandrasekaran2012latent,
  author = {Venkat Chandrasekaran and Pablo A. Parrilo and Alan S. Willsky},
  title = {{Latent variable graphical model selection via convex optimization}},
  journal = {The Annals of Statistics},
  year = {2012},
  doi = {10.1214/11-aos949},
}
Figure