Promoteur : Prof. Nicolas Gillis

Abstract: In many fields, such as linear algebra, computational geometry, combinatorial optimization, analytical chemistry and geoscience, nonnegativity of the solution is required, which is either due to the fact that the data is physically nonnegative, or the mathematical modeling of the problem requires nonnegativity. Image and audio processing are two examples for which the data are physically nonnegative. Probability and graph theory are examples for which the mathematical modeling requires nonnegativity.
This thesis is about the nonnegative factorization of matrices and tensors: namely nonnegative matrix factorization (NMF) and nonnegative tensor factorization (NTF). NMF problems arise in a wide range of scenarios such as the aforementioned fields, and NTF problems arise as a generalization of NMF. As the name suggests, the contributions of this thesis are centered on NMF and NTF over three aspects: modeling, algorithms and applications.
On the modeling aspect, we study two specific classes of NMF problems, namely the Minimumvolume NMF (minvol NMF) and the Nonnegative Unimodal Matrix Factorization (NuMF). Minvol NMF generalizes other classes of NMF problems and it can be shown that, it leads to identifiability under some mild conditions, that is, the solution of minvol NMF is unique. On the NuMF we provide an efficient algorithm for solving the problem. Both minvol NMF and NuMF are then applied on realworld datasets to demonstrate their effectiveness on solving some real-world machine learning tasks, namely hyperspectral imaging, audio blind source separation and analytical chemistry.
On the algorithmic side, we improve existing algorithms on solving NMF and NTF problems by introducing an acceleration framework, namely the Heuristic Extrapolation with Restarts (HER). Being a general acceleration framework, HER can be used to accelerate various Block Coordinate Descent (BCD) methods for solving NMF and NTF problems. The effectiveness of HER on accelerating the convergence of various BCDs are illustrated by experiments on synthetic and real datasets under different experimental settings.
On the application side, we used minvol NMF on hyperspectral imaging and audio source separation problems, and NuMF on chemistry data to demonstrate that NMF can produce meaningful decomposition of nonnegative data