Convex Biclustering

Abstract

In the biclustering problem, we seek to simultaneously group observations and features. While biclustering has applications in a wide array of domains, ranging from text mining to collaborative filtering, the problem of identifying structure in high dimensional genomic data motivates this work. In this context, biclustering enables us to identify subsets of genes that are co-expressed only within a subset of experimental conditions. We present a convex formulation of the biclustering problem that possesses a unique global minimizer and an iterative algorithm, COBRA, that is guaranteed to identify it. Our approach generates an entire solution path of possible biclusters as a single tuning parameter is varied. We also show how to reduce the problem of selecting this tuning parameter to solving a trivial modification of the convex biclustering problem. The key contributions of our work are its simplicity, interpretability, and algorithmic guarantees - features that arguably are lacking in the current alternative algorithms. We demonstrate the advantages of our approach, which includes stably and reproducibly identifying biclusterings, on simulated and real microarray data.

29 pages, 3 figures

References in corpus (7)

• Natural Scales in Geographical Patterns
• Pathwise coordinate optimization
• Proceedings of the 29th International Conference on Machine Learning (ICML-12)
• Coordinate descent algorithms for lasso penalized regression
• Lasso-type recovery of sparse representations for high-dimensional data
• Finding large average submatrices in high dimensional data
• Splitting Methods for Convex Clustering

Cited by in corpus (12)

• Nonparametric Density Estimation for High-Dimensional Data - Algorithms and Applications
• Convex Clustering: An Attractive Alternative to Hierarchical Clustering
• Hierarchical Coupled Geometry Analysis for Neuronal Structure and Activity Pattern Discovery
• Provable Convex Co-clustering of Tensors
• Dynamic Visualization and Fast Computation for Convex Clustering via Algorithmic Regularization
• Multi-way Graph Signal Processing on Tensors: Integrative analysis of irregular geometries
• Convex Subspace Clustering by Adaptive Block Diagonal Representation
• Splitting Methods for Convex Bi-Clustering and Co-Clustering
• Profile Likelihood Biclustering
• Automatic Registration and Clustering of Time Series
• Simultaneous Grouping and Denoising via Sparse Convex Wavelet Clustering
• Going off the Grid: Iterative Model Selection for Biclustered Matrix Completion