## High-Dimensional Covariance Decomposition into Sparse Markov and Independence Models

*Majid Janzamin, Animashree Anandkumar*; 15(Apr):1549−1591, 2014.

### Abstract

Fitting high-dimensional data involves a delicate tradeoff
between faithful representation and the use of sparse models.
Too often, sparsity assumptions on the fitted model are too
restrictive to provide a faithful representation of the observed
data. In this paper, we present a novel framework incorporating
sparsity in different domains. We decompose the observed
covariance matrix into a sparse Gaussian Markov model (with a
sparse precision matrix) and a sparse independence model (with a
sparse covariance matrix). Our framework incorporates sparse
covariance and sparse precision estimation as special cases and
thus introduces a richer class of high-dimensional models. %We
posit the observed data as generated from a linear combination
of a sparse Gaussian Markov model (with a sparse precision
matrix) and a sparse Gaussian independence model (with a sparse
covariance matrix). We characterize sufficient conditions for
identifiability of the two models, viz., Markov and independence
models. We propose an efficient decomposition method based on a
modification of the popular $\ell_1$-penalized maximum-
likelihood estimator ($\ell_1$-MLE). We establish that our
estimator is consistent in both the domains, i.e., it
successfully recovers the supports of both Markov and
independence models, when the number of samples $n$ scales as $n
= \Omega(d^2 \log p)$, where $p$ is the number of variables and
$d$ is the maximum node degree in the Markov model. Our
experiments validate these results and also demonstrate that our
models have better inference accuracy under simple algorithms
such as loopy belief propagation.

[abs][pdf][bib]