Back to search

Georgia Institute of Technology

Speeding up nonnegative low-rank approximation: Parallelism and Randomization

Abstract

dc:description.abstract

Nonnegative 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 × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/75711

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Hayashi, Koby Bruce. Speeding up nonnegative low-rank approximation: Parallelism and Randomization. Doctoral thesis, Georgia Institute of Technology, 2024. https://hdl.handle.net/1853/75711