Back to search

University of Waterloo

On Initializations for NMF

Abstract

dc:description.abstract

In Ward and Kolda (2023) and Xu et al. (2024), the authors proposed a sketching based initialization for unconstrained two block matrix factorization (MF) with provable guarantee. The purpose of this thesis is to examine the limits of extending these two proof frameworks in the context of Non-negative Matrix Factorization (NMF), as well as its numerical implications. The first chapter deals with fundamentals of NMF: its formulation, the identifiability issue and guarantees, a survey of iterative methods to solve it, and finally some complexity results. In the second chapter, I will quickly go over spectral initialization techniques for matrix optimization problems, and introduce sketching, a family of randomization techniques for numerical linear algebra, with a particular focus on its uses in iterative methods. The core focus of this chapter lies at the intersection of these two topics: a sketching-based initialization for the unconstrained two-block MF problem, using either non-alternating or alternating gradient descent (GD). We will go over the proof frameworks. In the third chapter, I will present my attempts to generalize the proof frameworks to NMF and the conclusions based on the partial progress. The fourth chapter deals with numerics. We will compare the performance of different base methods in different data regimes using all of the initializations mentioned in this thesis.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2026

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Shi, Sammy

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10012/23609

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Shi, Sammy. On Initializations for NMF. University of Waterloo, 2026. https://hdl.handle.net/10012/23609