Latent variable graphical model selection via convex optimization

By Venkat Chandrasekaran, Pablo A. Parrilo, Alan S. Willsky. Allerton Conference on Communication, Control, and Computing, 2010

543 citations recorded by the source corpus.

Suppose we have 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 hidden 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 ℓ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 hidden 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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/5ed8e2207664dd7ac7d65e3130cbec91aef4d6f9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Statistics and Probability

Citations in the corpus

Analysis of elliptical copula correlation factor model with Kendall's tau (2013, methodology): “For instance, [9, 20] require nontrivial specification of an additional regularization parameter λ= λ(μ) for the element-wise l1 penalty of the sparse component.”
Training Complex Models with Multi-Task Weak Supervision (2018, methodology): “We can then write the covariance matrix of the indicator variables for O ∪ S , Cov [ψ(O ∪ S)], along with its inverse, in block form similar to [6] as:”
Exploratory graph analysis: A new approach for estimating the number of dimensions in psychological research (2016, background): “wo indicators should not be zero. In fact, network models can be shown to be mathematically equivalent under certain conditions to latent variable models in both binary [42, 49] and Gaussian datasets [50], in which case each latent variable is represented by a rank1 cluster. Thus, when defining a cl”
A Tutorial on Regularized Partial Correlation Networks (2016, background): “To overcome induced edges from latent variables, one can estimate a network structure after taking co- variation due to one or more common causes into account (termed a residual network; Pan et al. in press; Epskamp et al. 2017c; Chen et al. 2016; Chandrasekaran et al. 2012).”
Forward-Backward Splitting with Bregman Distances (2015, background): “Besides, the nearness matrix problem [20] and the log-determinant minimization problem [14] can be also regarded as special cases of (1.”
Structure Learning in Graphical Modeling (2016, methodology): “Chandrasekaran et al. (2012) show that under identiﬁability conditions the sparsity pattern of ˆ K sp and the rank of ˆ K lr consistently estimate the subgraph G O and the number of hidden variables.”
Detecting Confounding in Multivariate Linear Models via Spectral Analysis (2017, background): “We should also mention [21], which is remotely related to this paper.”
Learning Gaussian Graphical Models with Observed or Latent FVSs (2013, unknown): “In [16], a convex optimization framework is proposed to learn GGMs with latent variables, where conditioned on a small number of latent variables, the remaining nodes induce a sparse graph.”
Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset (2015, background): “[54] proposed to discover the number of latent components, and to learn a statistical model over the entire collection of variables by only observing samples of a subset of a collection of random variables.”
Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods (2017, background): “…that a wide class of probabilistic models can be trained consistently using a suite of different efficient algorithms: convex relaxation methods (Chandrasekaran et al., 2010), spectral and tensor methods (Anandkumar et al., 2014b), alternating minimization (Agarwal et al., 2014), and they…”
Parallel Direction Method of Multipliers (2014, background): “A variety of machine learning problems can be cast into the linearly-constrained optimization problem (1) [8, 4, 24, 5, 6, 21, 11].”
The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent (2014, methodology): “see the image alignment problem in [22], the robust principal component analysis model with noisy and incomplete data in [25], the latent variable Gaussian graphical model selection in [5, 21] and the quadratic discriminant analysis model in [20].”
Learning Latent Variable Gaussian Graphical Models (2014, methodology): “The work that is most relevant to ours is by Chandrasekaran et al. (2012), who study the LVGGM learning problem, but focus on the simultaneous model selection consistency of both the sparse and low-rank components.”