Convex optimization for rank-sparsity decomposition, with application to the planted quasi-clique problem

Simple item page
dc.contributor.authorAbdulsalaam, Sakirudeen A
dc.date.accessioned2021-04-24T13:00:32Z
dc.date.available2021-04-24T13:00:32Z
dc.date.issued2020
dc.descriptionA thesis submitted in fulfillment of the requirements for the degree of Doctor of Philosophy, University of the Witwatersrand, Faculty of Science, Johannesburg, 2020en_ZA
dc.description.abstractWe 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 problemen_ZA
dc.description.librarianCK2021en_ZA
dc.facultyFaculty of Scienceen_ZA
dc.format.extentOnline resource (151 leaves)
dc.identifier.citationAbdulsalaam, Sakirudeen Akinkunmi (2020) Convex optimization for rank-sparsity decomposition, with application for the planted quasi-clique problem, University of the Witwatersrand, Johannesburg, <http://hdl.handle.net/10539/30982>
dc.identifier.urihttps://hdl.handle.net/10539/30982
dc.language.isoenen_ZA
dc.phd.titlePhDen_ZA
dc.schoolSchool of Computer Science and Applied Mathematicsen_ZA
dc.subject.lcshData mining
dc.subject.lcshGraph theory
dc.subject.lcshLinear systems
dc.titleConvex optimization for rank-sparsity decomposition, with application to the planted quasi-clique problemen_ZA
dc.typeThesisen_ZA
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
abdulsalaam_thesis_final.pdf
Size:
1.27 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
ETD Collection