Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2208.03251 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929502385340416 |
|---|---|
| author | Abdulsalaam, Sakirudeen A. Ali, Montaz |
| author_facet | Abdulsalaam, Sakirudeen A. Ali, Montaz |
| contents | In this paper, we apply the Rank-Sparsity Matrix Decomposition to the planted Maximum Quasi-Clique Problem (MQCP). This problem has the planted Maximum Clique Problem (MCP) as a special case. The maximum clique problem is NP-hard. A Quasi-clique or $γ$-clique is a dense graph with the edge density of at least $γ$, where $γ\in (0, 1]$. The maximum quasi-clique problem seeks to find such a subgraph with the largest cardinality in a given graph. Our method of choice is the low-rank plus sparse matrix splitting technique. We present a theoretical basis for when our convex relaxation problem recovers the planted maximum quasi-clique. We derived a new bound on the norm of the dual matrix that certifies the recovery using $l_{\infty,2} norm. We showed that when certain conditions are met, our convex formulation recovers the planted quasi-clique exactly. The numerical experiments we performed corroborated our theory. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_03251 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Rank-sparsity decomposition for planted quasi clique recovery Abdulsalaam, Sakirudeen A. Ali, Montaz Optimization and Control In this paper, we apply the Rank-Sparsity Matrix Decomposition to the planted Maximum Quasi-Clique Problem (MQCP). This problem has the planted Maximum Clique Problem (MCP) as a special case. The maximum clique problem is NP-hard. A Quasi-clique or $γ$-clique is a dense graph with the edge density of at least $γ$, where $γ\in (0, 1]$. The maximum quasi-clique problem seeks to find such a subgraph with the largest cardinality in a given graph. Our method of choice is the low-rank plus sparse matrix splitting technique. We present a theoretical basis for when our convex relaxation problem recovers the planted maximum quasi-clique. We derived a new bound on the norm of the dual matrix that certifies the recovery using $l_{\infty,2} norm. We showed that when certain conditions are met, our convex formulation recovers the planted quasi-clique exactly. The numerical experiments we performed corroborated our theory. |
| title | Rank-sparsity decomposition for planted quasi clique recovery |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2208.03251 |