Repository logo
 

Low rank representations of matrices using nuclear norm heuristics

Simple item page
dc.contributor.authorOsnaga, Silvia Monica, author
dc.contributor.authorKirby, Michael, advisor
dc.contributor.authorPeterson, Chris, advisor
dc.contributor.authorBates, Dan, committee member
dc.contributor.authorWang, Haonan, committee member
dc.date.accessioned2007-01-03T06:32:52Z
dc.date.available2007-01-03T06:32:52Z
dc.date.issued2014
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.language.isoeng
dc.publisherColorado State University. Libraries
dc.relation.ispartof2000-2019
dc.rightsCopyright and other restrictions may apply. User is responsible for compliance with all applicable laws. For information about copyright law, please see https://libguides.colostate.edu/copyright.
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.dplaThis Item is protected by copyright and/or related rights (https://rightsstatements.org/vocab/InC/1.0/). You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).
thesis.degree.disciplineMathematics
thesis.degree.grantorColorado State University
thesis.degree.levelDoctoral
thesis.degree.nameDoctor of Philosophy (Ph.D.)

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Osnaga_colostate_0053A_12616.pdf
Size:
1.01 MB
Format:
Adobe Portable Document Format
Description:
Download

Collections

2000-2019
Theses and Dissertations