A nonnegative least squares solver for multiple right-hand sides for approximating the nonnegative matrix factorization

• Κύριος συγγραφέας: Κολώνιας, Λεωνίδας
• Άλλοι συγγραφείς: Kolonias, Leonidas
• Γλώσσα: English
• Έκδοση: 2022
• Θέματα: Nonneggative Least Squares (NNLS); Nonnegative Matrix Factorization (NMF); Multiple right-hand sides; Block Krylov subspaces; Numerical linear algebra; Μη αρνητικά ελάχιστα τετράγωνα; Μη αρνητική παραγοντοποίηση μητρώων; Πολλά δεξιά μέλη; Μπλοκ υπόχωροι Krylov

Nonnegative Least Squares (NNLS) problems, where the variables are restricted to take only nonnegative values, often arise in many applications and are also at the core of most approaches to solve the nonnegative matrix factorization (NMF), a low-rank matrix approximation problem with nonnegativity constraints. NMF is a data analysis technique used in a great variety of applications such as text mining, image processing, hyperspectral data analysis, computational biology, and clustering. In more detail, the nonnegative factors can be interpreted as data e.g., as images described by pixel intensities or texts represented by vectors of word counts. The mathematical formulation for NMF appears as a non-convex optimization problem, and various types of algorithms have been devised to solve the problem. The first goal of this thesis is to propose a new efficient, yet simple to implement, approach to solve nonnegative linear least squares problems for multiple right-hand sides. More precisely, we study and use properties of global algorithms for least squares problems which are then combined with rules that enforce nonnegativity and lead to novel techniques for solving the aforementioned problem by a flexible Krylov subspace method. Comparisons of the state of the art algorithms using datasets and examples that come from real life applications as well as those artificially generated show that the proposed new algorithm presents a satisfactory behaviour and in some cases outperforms existing ones in computational speed and accuracy. Our second goal is to study extensively the NMF, its properties and applications and dive into the existing algorithms and methodologies used in order to approximate a solution for it. Moreover, using our new approach, tuned to solve large scale nonnegative least squares problems for multiple right-hand sides we present a novel algorithm for NMF based on the alternating nonnegative least squares (ANLS) framework. Extensive experiments on document clustering, images and synthetic datasets indicate the effectiveness of our approach.