Show simple item record

dc.contributor.advisorKirby, Michael
dc.contributor.advisorPeterson, Chris
dc.contributor.authorOsnaga, Silvia Monica
dc.contributor.committeememberBates, Dan
dc.contributor.committeememberWang, Haonan
dc.date.accessioned2007-01-03T06:32:52Z
dc.date.available2007-01-03T06:32:52Z
dc.date.issued2014
dc.description2014 Summer.
dc.description.abstractThe pursuit of low dimensional structure from high dimensional data leads in many instances to the finding the lowest rank matrix among a parameterized family of matrices. In its most general setting, this problem is NP-hard. Different heuristics have been introduced for approaching the problem. Among them is the nuclear norm heuristic for rank minimization. One aspect of this thesis is the application of the nuclear norm heuristic to the Euclidean distance matrix completion problem. As a special case, the approach is applied to the graph embedding problem. More generally, semi-definite programming, convex optimization, and the nuclear norm heuristic are applied to the graph embedding problem in order to extract invariants such as the chromatic number, Rn embeddability, and Borsuk-embeddability. In addition, we apply related techniques to decompose a matrix into components which simultaneously minimize a linear combination of the nuclear norm and the spectral norm. In the case when the Euclidean distance matrix is the distance matrix for a complete k-partite graph it is shown that the nuclear norm of the associated positive semidefinite matrix can be evaluated in terms of the second elementary symmetric polynomial evaluated at the partition. We prove that for k-partite graphs the maximum value of the nuclear norm of the associated positive semidefinite matrix is attained in the situation when we have equal number of vertices in each set of the partition. We use this result to determine a lower bound on the chromatic number of the graph. Finally, we describe a convex optimization approach to decomposition of a matrix into two components using the nuclear norm and spectral norm.
dc.format.mediumborn digital
dc.format.mediumdoctoral dissertations
dc.identifierOsnaga_colostate_0053A_12616.pdf
dc.identifier.urihttp://hdl.handle.net/10217/83799
dc.languageEnglish
dc.publisherColorado State University. Libraries
dc.relation.ispartof2000-2019 - CSU Theses and Dissertations
dc.rightsCopyright of the original work is retained by the author.
dc.subjectchromatic number
dc.subjectconvex optimization
dc.subjectEuclidean distance matrix completion
dc.subjectgraph realizability
dc.subjectpositive semidefinite cone
dc.titleLow rank representations of matrices using nuclear norm heuristics
dc.typeText
dcterms.rights.dplaThe copyright and related rights status of this item has not been evaluated (https://rightsstatements.org/vocab/CNE/1.0/). Please refer to the organization that has made the Item available for more information.
thesis.degree.disciplineMathematics
thesis.degree.grantorColorado State University
thesis.degree.levelDoctoral
thesis.degree.nameDoctor of Philosophy (Ph.D.)


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record