Latent variable graphical model selection via convex optimization

Venkat Chandrasekaran; Pablo A. Parrilo; Alan S. Willsky

Source-linked AI summary

Latent variable graphical model selection via convex optimization

Venkat Chandrasekaran, Pablo A. Parrilo, Alan S. Willsky

arXiv:1008.1290v2Aug 6, 2010math.STmath.OC

TL;DR

The paper asks whether latent components and a model over all variables can be learned when only a subset is observed and latent structure is unspecified. It develops a sparse-plus-low-rank convex regularized maximum-likelihood method for jointly Gaussian variables, and proves consistent recovery of latent-component number and conditional observed-variable structure under identifiability conditions, including high-dimensional regimes.

Problem
When only some variables are observed, the number of latent variables and their relationships with observed variables may be unknown, complicating graphical model selection.
Method
The paper decomposes the observed marginal concentration matrix into sparse and low-rank components using ℓ1 and nuclear-norm regularized maximum likelihood.
Results
The convex program consistently estimates the number of latent components and the conditional graphical model structure among observed variables in high-dimensional settings under suitable conditions.
Takeaways & Limitations
The framework combines latent-component identification with graphical modeling of structure remaining among observed variables conditioned on those components.
Takeaways & Limitations
The framework is developed for jointly Gaussian variables, and more efficient solvers and extensions to non-Gaussian data remain open problems.

Abstract

from arXiv · show

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.

1. Introduction and setup.

The paper addresses latent-variable Gaussian graphical model selection from observed-variable marginals by separating sparse conditional structure from low-rank latent effects. It establishes identifiability conditions and proposes a convex regularized maximum-likelihood estimator with consistency guarantees in high-dimensional settings.

Motivation: High-dimensional model selection is difficult when sample sizes are comparable to or smaller than the number of variables, motivating covariance regularization.The sample covariance matrix is poorly behaved in this regime.
Latent variables: Unobserved variables complicate model selection because their number and relationships with observed variables may be unknown.Typical approaches fix these quantities and fit parameters with EM.
Model decomposition: Marginalizing latent variables yields an observed-variable concentration matrix that decomposes into a sparse conditional component and a low-rank latent-effect component.The low-rank term summarizes marginalization over latent variables, while the sparse term captures conditional graphical structure.
Identifiability: Identifiability is studied as unique sparse-plus-low-rank decomposition, using transversality between tangent spaces of the corresponding algebraic varieties.The conditions require sparse structure in the conditional model and a low-rank latent effect with suitable geometric separation.
Estimator: The proposed estimator uses ℓ1 and nuclear-norm penalties in a convex regularized maximum-likelihood framework.The ℓ1 norm promotes sparsity, the nuclear norm promotes low rank, and γ trades off the two terms.
Guarantees: With suitable regularization and identifiability conditions, the estimator consistently recovers the conditional graphical structure and latent-component rank in high-dimensional regimes.The guarantees allow observed variables, latent components, and samples to grow together, with appropriate signal-strength conditions.

Related previous work.

The paper is organized around formal setup, identifiability, consistency results, proofs, experiments, and discussion.

Sections 2–5 cover background, problem formulation, identifiability, main results, and proofs.
Section 6 evaluates the estimator on synthetic and real data, followed by discussion in Section 7.

2. Problem statement and background.

The paper formulates latent-variable Gaussian graphical model selection from marginal statistics of observed variables. It defines algebraic correctness through recovery of the sparse conditional structure, latent-component count, and a realizable latent-variable model.

The model-selection problem seeks to recover latent-variable structure from samples and marginal statistics of observed variables.
The latent-variable representation is nonunique, but the low-rank component induced by marginalization is invariant across equivalent latent configurations.
Algebraic correctness requires the estimated sparse matrix to match the true sign pattern, the estimated low-rank matrix to have the true rank, and their difference to define a realizable model.
The sparse estimate represents conditional graphical structure, while the low-rank estimate represents correlations induced by marginalizing latent variables.
The paper distinguishes algebraic correctness from bounded estimation error, because norm closeness does not generally guarantee matching support, sign pattern, or rank.

Goal.

The goal is to estimate sparse and low-rank components from observed-variable samples using a regularized likelihood convex program. The estimates should be algebraically correct and have bounded estimation error with high probability.

The target is to estimate sparse and low-rank matrices from samples of the observed variables.
The proposed regularized likelihood convex program produces the estimates (Ŝ_n, L̂_n).

Our approach.

The approach combines Gaussian likelihood modeling with the geometry of sparse and low-rank matrix varieties. A convex formulation estimates both components, while tangent-space conditions connect identifiability to consistency.

The convex formulation uses the Gaussian likelihood to learn a latent-variable model from the observed sample covariance.
The likelihood is jointly concave in the sparse and low-rank parameters whenever S − L ≻ 0.
The Fisher information supplies curvature information for analyzing the likelihood-based convex program.
The analysis studies sparse and low-rank matrices as algebraic varieties through their dimensions, smooth points, tangent spaces, and local curvature.

Curvature of rank variety.

The low-rank matrix variety has nonzero local curvature, so the analysis controls how its tangent space changes near the target matrix. Singular-value bounds provide the relevant curvature control.

The smallest nonzero singular value is used to control twisting between tangent spaces at nearby low-rank matrices.

3. Identifiability.

Identifiability requires separating sparse conditional graphical structure from diffuse low-rank effects induced by latent variables. The paper characterizes this separation geometrically through tangent-space transversality and connects it to consistent estimation by a convex program.

Without additional conditions, latent-variable model selection from observed marginal statistics is ill-posed, so identifiability conditions are required.The conditions target models identifiable from marginal statistics of only a subset of variables.
Latent effects must be diffuse or incoherent, because sparse low-rank effects can be confused with conditional graphical structure.Incoherence prevents the low-rank component’s support from concentrating in a few locations.
The observed-variable conditional graphical model must have small degree, preventing densely connected subgraphs from being mistaken for latent-induced correlations.A sparse matrix with bounded degree has a small tangent-space concentration measure µ(Ω).
Sparse-plus-low-rank decomposition is identifiable when the corresponding tangent spaces intersect transversely; this condition also supports local identifiability.The transversality level is measured through the restricted addition operator, with transverse intersection equivalent to positive minimum gain.
Under these tangent-space conditions, the regularized maximum-likelihood convex program consistently estimates the latent-variable graphical model without tangent-space side information.The analysis uses Fisher information to study optimality and its gain on the sparse, low-rank, and direct-sum tangent spaces.
The quantities µ(Ω) and ξ(T) control transversality: smaller values make the sparse and low-rank tangent spaces more transverse.A small χ(Ω,T,γ) makes the addition operator essentially isometric, and 1 − χ(Ω,T,γ) ≤ ε(Ω,T,gγ).

4. Consistency of regularized maximum-likelihood program.

The regularized maximum-likelihood estimator consistently separates sparse conditional structure from the low-rank effect of latent variables under identifiability and signal-strength conditions. The guarantees include algebraic correctness, estimation-error bounds, and several high-dimensional scaling regimes.

Main theorem: The theorem requires identifiability, a suitable trade-off parameter γ, and lower bounds on the minimum nonzero entry of S∗ and singular value of L∗.The minimum singular-value condition also controls curvature of the low-rank variety around L∗.
Parameter selection: Consistency holds for a range of γ values, while stability across that range helps choose γ when µ(Ω(S∗)) and ξ(T(L∗)) are unknown.The range is governed by quantities controlling the sparse and low-rank tangent spaces.
Scaling regimes: For bounded-degree conditional graphs, consistent estimation requires n ∼p samples even when h ∼p; polylogarithmic degree requires n ∼p polylog(p).These regimes concern models where the latent-variable effect is diffuse across almost all observed variables.
Estimator and assumptions: The convex program estimates the sparse and low-rank components of the observed marginal concentration matrix using observed-variable samples.The analysis uses tangent spaces associated with sparse and low-rank matrix varieties and a Fisher-information-based identifiability condition.
Estimation error: The results also provide covariance-matrix estimation guarantees for (ˆSn −ˆLn)−1 under the same conditions.The covariance estimate is compared with the true marginal covariance matrix Σ∗.

5. Proofs.

The proofs establish optimality and consistency of the sparse-plus-low-rank convex estimator by combining convex-analytic, algebraic, perturbation, and probabilistic arguments.

Optimality analysis: The analysis uses subgradient decompositions associated with sparse and low-rank tangent spaces to characterize optimality of the convex program.These decompositions separate components in the relevant tangent and normal spaces.
Optimality analysis: A variety-constrained optimization problem is used solely as an analysis tool to construct estimates satisfying the original convex program’s optimality conditions.The resulting solution inherits algebraic correctness from the sparse and low-rank variety constraints.
Algebraic guarantees: Under the proposition’s conditions, the estimated sparse component has the correct sign pattern and the estimated low-rank component has the correct rank and tangent space.The low-rank estimate is also positive semidefinite, and its tangent space remains close to the true tangent space.
Algebraic guarantees: When the stated tangent-space constraints become inactive, the constrained solution is the unique solution of the original convex program.This connects the algebraic construction to the estimator actually analyzed.
Probabilistic argument: The probabilistic proof controls sample-covariance error and combines deterministic propositions to establish the theorem’s high-dimensional consistency result.The argument conditions on a spectral-norm event for the sample-covariance deviation and then verifies the required bounds.

6. Simulation results.

Synthetic experiments evaluate algebraic recovery across sparse conditional graphs, while stock-return experiments compare the latent-variable model with standard sparse graphical modeling.

6.1. Synthetic data.: Algebraically correct estimation probabilities are evaluated over 50 random trials for each sample size in the synthetic experiments.Figure 1 reports these probabilities for the three specified graph structures.
6.1. Synthetic data.: The synthetic models use 36 observed variables with cycles or a 6 × 6 grid, one to three latent variables, and latent effects spread across 80% of observed variables.The spread-out effects make the low-rank latent component incoherent.
6.1. Synthetic data.: Standard graphical model selection is not useful on the synthetic marginal distributions because their concentration matrices are not well-approximated by sparse matrices.The experiments instead support the convex program’s algebraic consistency with observed-variable samples.
6.2. Stock returns: The stock-return model contains 5 latent variables and 135 conditional edges, totaling 639 parameters, with KL divergence 17.7 from the sample-covariance Gaussian.The data comprise monthly returns for 84 S&P 100 companies from 1990 to 2007, with 216 samples.

7. Discussion.

The discussion concludes that sparse-plus-latent Gaussian graphical modeling is identifiable and consistently estimable from observed variables, while highlighting computational and distributional extensions as open problems.

Contributions: The paper gives identifiability conditions and a convex ℓ1-plus-nuclear-norm estimator for latent-variable Gaussian graphical model selection.The estimator targets both latent components and the conditional graphical structure among observed variables.
Contributions: The estimator consistently estimates the number of latent components and the conditional graphical model structure in a high-dimensional regime.The conclusions are supported by theoretical results and synthetic-data experiments, with an additional stock-return application.
Open questions: Scaling the polynomial-time convex program to massive datasets and extending statistically consistent methods to non-Gaussian variables remain open directions.Categorical data are given as one example of a non-Gaussian setting requiring further development.

V. Chandrasekaran Department of Computing

The supplied passage contains affiliation fragments naming V. Chandrasekaran, P. A. Parrilo, and A. S. Wills, along with computing, electrical engineering, and information-systems departments.

It names P. A. Parrilo and A. S. Wills.
The affiliation fragments mention the Laboratory for Information and Decision Systems and the Department of Electrical Engineering.
The passage names V. Chandrasekaran in connection with the Department of Computing.