3. Electronic Theses and Dissertations (ETDs) - All submissions
Permanent URI for this communityhttps://wiredspace.wits.ac.za/handle/10539/45
Browse
1 results
Search Results
Item Convex optimization for rank-sparsity decomposition, with application to the planted quasi-clique problem(2020) Abdulsalaam, Sakirudeen AWe consider the rank-sparsity decomposition problem with its application to the planted quasi-clique recovery in this thesis. Given a matrix which is a superposition of a low rank and a sparse matrix, the rank sparsity decomposition problem answers the question, “when is it possible to decompose the matrix into its low rank and sparse components?”. The common convex formulation for this problem is to minimize a weighted combination of the nuclear norm and thel1-norm. To prove optimality of solutions with this formulation, it is customary to derive a bound on the dual matrix which certifies the optimality of the solution. Among the methodological contributions of this thesis is the sharp theoretical bounds obtained for the dual matrix. We have improved the results on low rank matrix decomposition by deriving the bound on our dual matrix, using the matrix l∞,2 norm. Moreover, we established conditions under which recovery is achievable by deriving a dual matrix, certifying the optimality of our solution. We adapt the convex formulation for the rank-sparstity decomposition to the planted quasi-clique problem. This problem is a generalization of the planted clique problem which is known to be NP-hard. This problem has applications in areas such as com-munity detection, data mining, bioinformatics, and criminal network analysis. We have considered mathematical modelling, theoretical framework, and computational aspects of the problem. We showed that the planted quasi-clique can be recovered using con-vex programming. We have achieved this by adapting techniques from low rank matrix decomposition to the planted quasi-clique problem. Our numerical results show that when the input graph contains the desired single large dense subgraph and a moderate number of diversionary vertices and edges, the relaxation is exact. We have shown, numerically, the superiority of our formulation over the only existing Mixed Integer Programming (MIP) formulations. Further, we present a simplified proof to show that quasi-cliques also posses what is known as quasi-hereditary property. This property can be exploited to develop enumerative algorithm for the problem