Guaranteed clustering and biclustering via semidefinite programming

DOI10.1007/S10107-013-0729-XzbMATH Open1297.90107arXiv1202.3663OpenAlexW1965656937MaRDI QIDQ463740FDOQ463740

Authors: Brendan P. W. Ames 

Publication date: 17 October 2014

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: 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 the 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. Empirical evidence from numerical experiments supporting these theoretical guarantees is also provided.

Full work available at URL: https://arxiv.org/abs/1202.3663

Recommendations

• Exact clustering of weighted graphs via semidefinite programming
• Approximating K‐means‐type Clustering via Semidefinite Programming
• Semidefinite spectral clustering
• Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
• Convex optimization for the planted \(k\)-disjoint-clique problem

zbMATH Keywords

clusteringco-clusteringsemidefinite programmingbiclusteringplanted clique

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms and problem complexity (68Q25) Clustering in the social and behavioral sciences (91C20) Semidefinite programming (90C22)

Cites Work

• Probing the Pareto frontier for basis pursuit solutions
• Title not available (Why is that?)
• Spectral clustering and the high-dimensional stochastic blockmodel
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• Title not available (Why is that?)
• NP-hardness of Euclidean sum-of-squares clustering
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• Nonmonotone Spectral Projected Gradient Methods on Convex Sets
• Probability Inequalities for Sums of Bounded Random Variables
• Exact matrix completion via convex optimization
• The effectiveness of Lloyd-type methods for the \(k\)-means problem
• Decoding by Linear Programming
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
• Stable signal recovery from incomplete and inaccurate measurements
• The eigenvalues of random symmetric matrices
• Convex optimization for the planted \(k\)-disjoint-clique problem
• Clustering partially observed graphs via convex optimization
• Correlation clustering with noisy input
• Compressed sensing
• Nuclear norm minimization for the planted clique and biclique problems
• Title not available (Why is that?)
• Correlation clustering
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• A simpler approach to matrix completion
• On clusterings: good, bad and spectral
• Polyhedral and semidefinite programming methods in combinatorial optimization
• A limit theorem for the norm of random matrices
• Remarks on the Notion of Order of Difference Equations
• Null space conditions and thresholds for rank minimization
• Biclustering in data mining
• Multi-way clustering and biclustering by the ratio cut and normalized cut in graphs
• Ensemble clustering using semidefinite programming with applications
• Title not available (Why is that?)
• Approximating K‐means‐type Clustering via Semidefinite Programming

Cited In (21)

• Recovering nonuniform planted partitions via iterated projection
• Goodness-of-fit test for latent block models
• Finding the largest low-rank clusters with Ky Fan \(2\)-\(k\)-norm and \(\ell_1\)-norm
• Attainable accuracy guarantee for the \(k\)-medians clustering in [0, 1]
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Convex optimization for the planted \(k\)-disjoint-clique problem
• Robustification of the \(k\)-means clustering problem and tailored decomposition methods: when more conservative means more accurate
• Profile likelihood biclustering
• Exact recovery in the hypergraph stochastic block model: a spectral algorithm
• Convex relaxation methods for community detection
• Approximating K‐means‐type Clustering via Semidefinite Programming
• A simple spectral algorithm for recovering planted partitions
• Size Matters: Cardinality-Constrained Clustering and Outlier Detection via Conic Optimization
• Title not available (Why is that?)
• Exact clustering of weighted graphs via semidefinite programming
• Convex optimization for the densest subgraph and densest submatrix problems
• \(k\)-median: exact recovery in the extended stochastic ball model
• Efficient, certifiably optimal clustering with applications to latent variable graphical models
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
• Recovery guarantees for exemplar-based clustering

Uses Software

• SPGL1

This page was built for publication: Guaranteed clustering and biclustering via semidefinite programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q463740)