Estimation of Graphical Models through Structured Norm Minimization
arXiv:1609.09010
Abstract
Estimation of Markov Random Field and covariance models from high-dimensional data represents a canonical problem that has received a lot of attention in the literature. A key assumption, widely employed, is that of {\em sparsity} of the underlying model. In this paper, we study the problem of estimating such models exhibiting a more intricate structure comprising simultaneously of {\em sparse, structured sparse} and {\em dense} components. Such structures naturally arise in several scientific fields, including molecular biology, finance, and political science. We introduce a general framework based on a novel structured norm that enables us to estimate such complex structures from high-dimensional data. The resulting optimization problem is convex and we introduce a linearized multi-block alternating direction method of multipliers (ADMM) algorithm to solve it efficiently. We illustrate the superior performance of the proposed framework on a number of synthetic data sets generated from both random and structured networks. Further, we apply the method to a number of real data sets and discuss the results.
arXiv commentarXiv admin note: text overlap with arXiv:1402.7349 by other authors
References in corpus (14)
- Emergence of scaling in random networks
- Finding and evaluating community structure in networks
- Community detection in graphs
- Functional cartography of complex metabolic networks
- Robust Recovery of Subspace Structures by Low-Rank Representation
- Linearized Alternating Direction Method with Adaptive Penalty for Low-Rank Representation
- Latent variable graphical model selection via convex optimization
- Group Lasso with Overlaps: the Latent Group Lasso approach
- Solving Multiple-Block Separable Convex Minimization Problems Using Two-Block Alternating Direction Method of Multipliers
- Sparse Inverse Covariance Selection via Alternating Linearization Methods
- Learning Graphical Models With Hubs
- A Three-Operator Splitting Scheme and its Optimization Applications
- NESTT: A Nonconvex Primal-Dual Splitting Method for Distributed and Stochastic Optimization
- Estimating heterogeneous graphical models for discrete data with an application to roll call voting