Open access
Datum
2022-05-06Typ
- Journal Article
Abstract
Semidefinite programming is an important tool to tackle several problems in data science and signal processing, including clustering and community detection. However, semidefinite programs are often slow in practice, so speed up techniques such as sketching are often considered. In the context of community detection in the stochastic block model, Mixon and Xie (IEEE Trans Inform Theory 67(10): 6832–6840, 2021) have recently proposed a sketching framework in which a semidefinite program is solved only on a subsampled subgraph of the network, giving rise to significant computational savings. In this short paper, we provide a positive answer to a conjecture of Mixon and Xie about the statistical limits of this technique for the stochastic block model with two balanced communities. Mehr anzeigen
Persistenter Link
https://doi.org/10.3929/ethz-b-000547746Publikationsstatus
publishedExterne Links
Zeitschrift / Serie
Sampling Theory, Signal Processing, and Data AnalysisBand
Seiten / Artikelnummer
Verlag
SpringerThema
Community detection; Clustering algorithms; Graph and network theory; Semidefinite programmingOrganisationseinheit
09679 - Bandeira, Afonso / Bandeira, Afonso