Estimating Tree-Structured Covariance Matrices via Mixed-Integer Programming

Hector Corrada Bravo, Stephen Wright, Kevin Eng, Sunduz Keles, Grace Wahba
Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, PMLR 5:41-48, 2009.

Abstract

We present a novel method for estimating tree-structured covariance matrices directly from observed continuous data. 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 expression in yeast gene families and a comparison using simulated data to distance-based tree estimating procedures.

Cite this Paper

BibTeX
@InProceedings{pmlr-v5-bravo09a, title = {Estimating Tree-Structured Covariance Matrices via Mixed-Integer Programming}, author = {Bravo, Hector Corrada and Wright, Stephen and Eng, Kevin and Keles, Sunduz and Wahba, Grace}, booktitle = {Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics}, pages = {41--48}, year = {2009}, editor = {van Dyk, David and Welling, Max}, volume = {5}, series = {Proceedings of Machine Learning Research}, address = {Hilton Clearwater Beach Resort, Clearwater Beach, Florida USA}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v5/bravo09a/bravo09a.pdf}, url = {https://proceedings.mlr.press/v5/bravo09a.html}, abstract = {We present a novel method for estimating tree-structured covariance matrices directly from observed continuous data. 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 expression in yeast gene families and a comparison using simulated data to distance-based tree estimating procedures.} }
Endnote
%0 Conference Paper %T Estimating Tree-Structured Covariance Matrices via Mixed-Integer Programming %A Hector Corrada Bravo %A Stephen Wright %A Kevin Eng %A Sunduz Keles %A Grace Wahba %B Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2009 %E David van Dyk %E Max Welling %F pmlr-v5-bravo09a %I PMLR %P 41--48 %U https://proceedings.mlr.press/v5/bravo09a.html %V 5 %X We present a novel method for estimating tree-structured covariance matrices directly from observed continuous data. 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 expression in yeast gene families and a comparison using simulated data to distance-based tree estimating procedures.
RIS
TY - CPAPER TI - Estimating Tree-Structured Covariance Matrices via Mixed-Integer Programming AU - Hector Corrada Bravo AU - Stephen Wright AU - Kevin Eng AU - Sunduz Keles AU - Grace Wahba BT - Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics DA - 2009/04/15 ED - David van Dyk ED - Max Welling ID - pmlr-v5-bravo09a PB - PMLR DP - Proceedings of Machine Learning Research VL - 5 SP - 41 EP - 48 L1 - http://proceedings.mlr.press/v5/bravo09a/bravo09a.pdf UR - https://proceedings.mlr.press/v5/bravo09a.html AB - We present a novel method for estimating tree-structured covariance matrices directly from observed continuous data. 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 expression in yeast gene families and a comparison using simulated data to distance-based tree estimating procedures. ER -
APA
Bravo, H.C., Wright, S., Eng, K., Keles, S. & Wahba, G.. (2009). Estimating Tree-Structured Covariance Matrices via Mixed-Integer Programming. Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 5:41-48 Available from https://proceedings.mlr.press/v5/bravo09a.html.

Related Material