Guaranteed clustering and biclustering via semidefinite programming

Details Guaranteed clustering and biclustering via semidefinite programming Guaranteed clustering and biclustering via semidefinite programming

2012-02-16

arxiv.org/abs/1202.3663v2

Mathematics

Optimization and Control

Scientific paper

Identifying clusters of similar objects in data plays a significant role in a wide range of applications. As a model problem for clustering, we consider the densest k-disjoint-clique problem, whose goal is to identify the collection of k disjoint cliques of a given weighted complete graph maximizing the sum of the densities of the complete subgraphs induced by these cliques. In this paper, we establish conditions ensuring exact recovery of the densest k cliques of a given graph from the optimal solution of a particular semidefinite program. In particular, the semidefinite relaxation is exact for input graphs corresponding to data consisting of k large, distinct clusters and a smaller number of outliers. This approach also yields a semidefinite relaxation for the biclustering problem with similar recovery guarantees. Given a set of objects and a set of features exhibited by these objects, biclustering seeks to simultaneously group the objects and features according to their expression levels. This problem may be posed as partitioning the nodes of a weighted bipartite complete graph such that sum of the densities of the resulting bipartite complete subgraphs is maximized. As in our analysis of the densest k-disjoint-clique problem, we show that the correct partition of the objects and features can be recovered from the optimal solution of a semidefinite program in the case that the given data consists of several disjoint sets of objects exhibiting similar features.

Affiliated with

Also associated with

No associations

Rating

Guaranteed clustering and biclustering via semidefinite programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Guaranteed clustering and biclustering via semidefinite programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Guaranteed clustering and biclustering via semidefinite programming will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-126047