  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 $\gamma$-clique is a dense graph with the edge density of at
least $\gamma$, where $\gamma \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
that has been used successfully for similar problems in the literature. 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.
