Show simple item record

dc.contributor.advisorRaichel, Benjamin
dc.creatorVan Buskirk, Gregory
dc.date.accessioned2018-04-02T19:19:41Z
dc.date.available2018-04-02T19:19:41Z
dc.date.created2017-12
dc.date.issued2017-12
dc.date.submittedDecember 2017
dc.identifier.urihttp://hdl.handle.net/10735.1/5688
dc.description.abstractWe consider the problem of computing a restricted nonnegative matrix factorization (NMF) of an m x n matrix X. Specifically, we seek a factorization X ≈ BC, where the k columns of B are a subset of those from X and C ∈ Re_{≥ 0}^{k x n}. Equivalently, given the matrix X, consider the problem of finding a small subset, S, of the columns of X such that the conic hull of S ε-approximates the conic hull of the columns of X, i.e., the distance of every column of X to the conic hull of the columns of S should be at most an ε-fraction of the angular diameter of X. If k is the size of the smallest ε-approximation, then we produce an O(k/ε^{2/3}) sized O(ε^{1/3})-approximation, yielding the first provable, polynomial time ε-approximation for this class of NMF problems, where also desirably the approximation is independent of n and m. Furthermore, we prove an approximate conic Carathéodory theorem, a general sparsity result, that shows that any column of X can be ε-approximated with an O(1/ε^2) sparse combination from S. Our results are facilitated by a reduction to the problem of approximating convex hulls, and we prove that both the convex and conic hull variants are d-SUM-hard, resolving an open problem. Finally, we provide experimental results for the convex and conic algorithms on a variety of feature selection tasks.
dc.format.mimetypeapplication/pdf
dc.language.isoen
dc.rightsCopyright ©2017 is held by the author. Digital access to this material is made possible by the Eugene McDermott Library. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
dc.subjectNon-negative matrices
dc.subjectFactorization (Mathematics)
dc.subjectApproximation algorithms
dc.subjectConic sections
dc.titleSparse Approximate Conic Hulls
dc.typeThesis
dc.date.updated2018-04-02T19:19:42Z
dc.type.materialtext
thesis.degree.grantorThe University of Texas at Dallas
thesis.degree.departmentComputer Science
thesis.degree.levelMasters
thesis.degree.nameMSCS


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record