Academy of Mathematics and Systems Science, CAS Colloquia & Seminars
Speaker:
Prof. Ming-Jun Lai, Department of Mathematics, University of Georgia, Athens, GA 30602
Inviter:
Title:
Compressive Sensing for Graph Clustering
Time & Venue:
2019.12.13 10:00-11:00 Z311
Abstract:
This talk is based on a joint work with Daniel Mckenzie. We will explain how to phrase the cut improvement for graphs as a sparse recovery problem, whence one can use algorithms originally developed for compressive sensing (such as SubspacePursuit to solve it. We show that this approach to cut improvement is fast, both in theory and practice and moreover enjoys statistical guarantees of success when applied to graphs drawn from probabilistic models such as the Stochastic Block Model. We then propose new methods for local clustering and semi-supervised clustering, which enjoy similar guarantees of success and speed. Finally, we demonstrate our approach with extensive numerical benchmarking.
Appendix：
Copyright@2008, All Rights Reserved, Academy of Mathematics and Systems Science, CAS
Tel: 86-10-82541777 Fax: 86-10-82541972 E-mail: contact@amss.ac.cn
