Sketching Semidefinite Programs for Faster Clustering

DOI10.1109/TIT.2021.3103711MaRDI QIDQ5032540zbMATH OpenOpenAlexFDO

Authors Dustin G. Mixon, Kaiying Xie

Publication date 17 February 2022

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Semidefinite programming (90C22) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: Many clustering problems enjoy solutions by semidefinite programming. Theoretical results in this vein frequently consider data with a planted clustering and a notion of signal strength such that the semidefinite program exactly recovers the planted clustering when the signal strength is sufficiently large. In practice, semidefinite programs are notoriously slow, and so speedups are welcome. In this paper, we show how to sketch a popular semidefinite relaxation of a graph clustering problem known as minimum bisection, and our analysis supports a meta-claim that the clustering task is less computationally burdensome when there is more signal.

Cited in

(2)

• Community detection with a subsampled semidefinite program
• scientific article; zbMATH DE number 5957371 (Why is no real title available?)

This page was built for publication: Sketching Semidefinite Programs for Faster Clustering

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