Georgia Institute of Technology
Speeding up nonnegative low-rank approximation: Parallelism and Randomization
Abstract
dc:description.abstractNonnegative Matrix Factorization (NMF) is a popular technique used in Machine Learning, Data mining, Computational Neuroscience, Image Segmentation, and more. As problem sizes grow larger the need for faster and more scalable algorithms becomes increasingly important. The topic of this thesis is to design, theoretically analyze, and implement fast methods for computing approximate NMF's and its variants. We approach this problem from two angles: scaling down and scaling out. When scaling down the amount of data or resources being used is reduced and when scaling out one incorporates distributed memory nodes via cluster or cloud computing. We scale down by applying techniques from Randomized Numerical Linear Algebra (RandNLA) to design efficient, randomized algorithms for NMF which allow us to down sample data in a principled way. These randomized methods achieve up to 7× speed up over nonrandomized methods and preserve solution quality in terms of relative error and downstream graph clustering tasks. We scale out by designing communication efficient distributed memory algorithms for execution on state-of-the-art super computing systems. Our distributed memory algorithms scale up to 16000 cores and achieve 2.2× speed up over existing parallel codes. We evaluate our methods on synthetic and real world data sets in terms of run time and various quality of solution metrics.
Degree
thesis:*- Level thesis:degree_level
- Doctoral
- Department dc:contributor.department
- Computational Science and Engineering
- Grantor dc:publisher
- Georgia Institute of Technology
- Year dc:date.issued
- 2024
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Hayashi, Koby Bruce
- Advisors dc:contributor.advisor
-
- Park, Haesun
- Vuduc, Richard
- Committee members dc:contributor.committeemember
-
- Ballard, Grey
- Kang, Sun Ha
- Buluç , Aydın
Subjects
dc:subject × 3Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1853/75711