Guaranteed clustering and biclustering via semidefinite programming
From MaRDI portal
(Redirected from Publication:463740)
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.
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
Cites work
- scientific article; zbMATH DE number 2089226 (Why is no real title available?)
- scientific article; zbMATH DE number 1266748 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- A limit theorem for the norm of random matrices
- A simpler approach to matrix completion
- Approximating K‐means‐type Clustering via Semidefinite Programming
- Biclustering in data mining
- Clustering partially observed graphs via convex optimization
- Compressed sensing
- Convex optimization for the planted \(k\)-disjoint-clique problem
- Correlation clustering
- Correlation clustering with noisy input
- Decoding by Linear Programming
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Ensemble clustering using semidefinite programming with applications
- Exact matrix completion via convex optimization
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- Multi-way clustering and biclustering by the ratio cut and normalized cut in graphs
- NP-hardness of Euclidean sum-of-squares clustering
- Nonmonotone Spectral Projected Gradient Methods on Convex Sets
- Nuclear norm minimization for the planted clique and biclique problems
- Null space conditions and thresholds for rank minimization
- On clusterings: good, bad and spectral
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- Polyhedral and semidefinite programming methods in combinatorial optimization
- Probability Inequalities for Sums of Bounded Random Variables
- Probing the Pareto frontier for basis pursuit solutions
- Recovering Low-Rank Matrices From Few Coefficients in Any Basis
- Remarks on the Notion of Order of Difference Equations
- Spectral clustering and the high-dimensional stochastic blockmodel
- Stable signal recovery from incomplete and inaccurate measurements
- The effectiveness of Lloyd-type methods for the \(k\)-means problem
- The eigenvalues of random symmetric matrices
- Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
Cited in
(21)- Convex optimization for the planted \(k\)-disjoint-clique problem
- Recovering nonuniform planted partitions via iterated projection
- Goodness-of-fit test for latent block models
- Efficient, certifiably optimal clustering with applications to latent variable graphical models
- Convex relaxation methods for community detection
- Robustification of the \(k\)-means clustering problem and tailored decomposition methods: when more conservative means more accurate
- Convex optimization for the densest subgraph and densest submatrix problems
- Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
- Profile likelihood biclustering
- Size matters: cardinality-constrained clustering and outlier detection via conic optimization
- \(k\)-median: exact recovery in the extended stochastic ball model
- Exact recovery in the hypergraph stochastic block model: a spectral algorithm
- A simple spectral algorithm for recovering planted partitions
- Exact clustering of weighted graphs via semidefinite programming
- Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
- Attainable accuracy guarantee for the \(k\)-medians clustering in [0, 1]
- scientific article; zbMATH DE number 7626745 (Why is no real title available?)
- Finding the largest low-rank clusters with Ky Fan \(2\)-\(k\)-norm and \(\ell_1\)-norm
- Approximating K‐means‐type Clustering via Semidefinite Programming
- Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
- Recovery guarantees for exemplar-based clustering
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)
