Compressive Sensing for Cut Improvement and Local Clustering
| Autor: | Ming-Jun Lai, Daniel Mckenzie |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Social and Information Networks (cs.SI)
FOS: Computer and information sciences Phrase Computer science Computer Science - Information Theory Information Theory (cs.IT) Computer Science - Social and Information Networks ComputerApplications_COMPUTERSINOTHERSYSTEMS Numerical Analysis (math.NA) Compressed sensing FOS: Mathematics Mathematics - Numerical Analysis Laplacian matrix Cluster analysis Algorithm 68Q25 68R10 68U05 94A12 |
| Zdroj: | SIAM Journal on Mathematics of Data Science. 2:368-395 |
| ISSN: | 2577-0187 |
| DOI: | 10.1137/19m1265971 |
| Popis: | We show how one can phrase the cut improvement problem for graphs as a sparse recovery problem, whence one can use algorithms originally developed for use in compressive sensing (such as SubspacePursuit or CoSaMP) 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. Using this new cut improvement approach, which we call ClusterPursuit, as an algorithmic primitive we then propose new methods for local clustering and semi-supervised clustering, which enjoy similar guarantees of success and speed. Finally, we verify the promise of our approach with extensive numerical benchmarking. Comment: 25 pages. Generalizes and improves upon the earlier versions arxiv: 1808.05780 and arXiv:1708.09477. To appear in SIMODS |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|