Estimating Tree-Structured Covariance Matrices via Mixed-Integer Programming.

Héctor Corrada Bravo, Stephen J. Wright, Kevin H. Eng, Sündüz Keleş, Grace Wahba

Abstract

We present a novel method for estimating tree-structured covariance matrices directly from observed continuous data. Specifically, we estimate a covariance matrix from observations of p continuous random variables encoding a stochastic process over a tree with p leaves. A representation of these classes of matrices as linear combinations of rank-one matrices indicating object partitions is used to formulate estimation as instances of well-studied numerical optimization problems.In particular, our estimates are based on projection, where the covariance estimate is the nearest tree-structured covariance matrix to an observed sample covariance matrix. The problem is posed as a linear or quadratic mixed-integer program (MIP) where a setting of the integer variables in the MIP specifies a set of tree topologies of the structured covariance matrix. We solve these problems to optimality using efficient and robust existing MIP solvers.We present a case study in phylogenetic analysis of gene expression and a simulation study comparing our method to distance-based tree estimating procedures.
BibTeX
@article{bravo2009estimating,
  author = {Héctor Corrada Bravo and Stephen J. Wright and Kevin H. Eng and Sündüz Keleş and Grace Wahba},
  title = {{Estimating Tree-Structured Covariance Matrices via Mixed-Integer Programming.}},
  journal = {AISTATS},
  year = {2009},
}

Loading related content...

Figure