<p>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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\gamma \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>γ</mi> </math></EquationSource> </InlineEquation>-clique is a dense graph with the edge density of at least <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\gamma \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>γ</mi> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\gamma \in (0, 1]\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>γ</mi> <mo>∈</mo> <mo stretchy="false">(</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation>. 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 have derived a new bound on the norm of the dual matrix that certifies the recovery using <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(l_{\infty , 2}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>l</mi> <mrow> <mi>∞</mi> <mo>,</mo> <mn>2</mn> </mrow> </msub> </math></EquationSource> </InlineEquation> norm. We have showed that when certain conditions are met, our convex formulation recovers the planted quasi-clique exactly. The numerical experiments we have performed corroborate our theoretical findings.</p>