Show simple item record

dc.contributor.advisorPark, Haesun
dc.contributor.authorKannan, Ramakrishnan
dc.date.accessioned2016-05-27T13:12:26Z
dc.date.available2016-05-27T13:12:26Z
dc.date.created2016-05
dc.date.issued2016-04-15
dc.date.submittedMay 2016
dc.identifier.urihttp://hdl.handle.net/1853/54962
dc.description.abstractLow rank approximation is the problem of finding two low rank factors W and H such that the rank(WH) << rank(A) and A ≈ WH. These low rank factors W and H can be constrained for meaningful physical interpretation and referred as Constrained Low Rank Approximation (CLRA). Like most of the constrained optimization problem, performing CLRA can be computationally expensive than its unconstrained counterpart. A widely used CLRA is the Non-negative Matrix Factorization (NMF) which enforces non-negativity constraints in each of its low rank factors W and H. In this thesis, I focus on scalable/distributed CLRA algorithms for constraints such as boundedness and non-negativity for large real world matrices that includes text, High Definition (HD) video, social networks and recommender systems. First, I begin with the Bounded Matrix Low Rank Approximation (BMA) which imposes a lower and an upper bound on every element of the lower rank matrix. BMA is more challenging than NMF as it imposes bounds on the product WH rather than on each of the low rank factors W and H. For very large input matrices, we extend our BMA algorithm to Block BMA that can scale to a large number of processors. In applications, such as HD video, where the input matrix to be factored is extremely large, distributed computation is inevitable and the network communication becomes a major performance bottleneck. Towards this end, we propose a novel distributed Communication Avoiding NMF (CANMF) algorithm that communicates only the right low rank factor to its neighboring machine. Finally, a general distributed HPC- NMF framework that uses HPC techniques in communication intensive NMF operations and suitable for broader class of NMF algorithms.
dc.format.mimetypeapplication/pdf
dc.publisherGeorgia Institute of Technology
dc.subjectDistributed
dc.subjectScalable
dc.subjectNMF
dc.subjectCommunication avoiding
dc.subjectHPC
dc.subjectLow rank approximation
dc.titleScalable and distributed constrained low rank approximations
dc.typeDissertation
dc.description.degreePh.D.
dc.contributor.departmentComputational Science and Engineering
thesis.degree.levelDoctoral
dc.contributor.committeeMemberChau, Duen Horng (Polo)
dc.contributor.committeeMemberBallard, Grey
dc.contributor.committeeMemberAggarwal, Charu
dc.contributor.committeeMemberVuduc, Richard
dc.date.updated2016-05-27T13:12:26Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record