Best nonnegative rank-2 matrix approximations
Loading...
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Author
Date
2024-06-18
Department
Major/Subject
Mathematics
Mcode
SCI3054
Degree programme
Master’s Programme in Mathematics and Operations Research
Language
en
Pages
61+1
Series
Abstract
A nonnegative rank-$r$ matrix factorization (NMF) of $X \in \RRp^{m\times n}$ takes the form $X= WH$, where $W \in \RRp^{m\times r}$, $H \in \RRp^{r\times n}$, and the matrices $W$ and $H$ are nonnegative. The nonnegative rank of the matrix $X$, denoted by $\nrnk{X}$, is the smallest $r$ for which such a decomposition exists. When the nonnegative matrix $X$ has rank two, we have $\rnk{X} = \nrnk{X}$. In the NMF-$r$ problem, one approximates a given datamatrix $U\in \RRp^{m\times n}$ with a matrix of nonnegative rank-$r$. The best approximation is the closest point among the nonnegative rank-$r$ matrices. The NMF problem has a variety of applications in data analysis, including image processing, data mining, and signal processing. The nonnegativity of the components $W$ and $H$ naturally highlights repeating features from the data, since the terms in the product cannot cancel out. In this thesis, I inspect the NMF-2 problem for small matrices of size $3\times 4$ and $4\times 4$. The problem is approached algebraically to ensure the optimality of the solution: when the number of critical points (Euclidean distance degree) is known in advance, one may ensure that all the critical points have been successfully found in the numerical computations. We redefine the NMF-2 problem as multiple rank-2 optimization problems with forced zeros. The zeros of the matrix are called the zero pattern. The NMF-2 problem has been previously studied, and a connection between the rank-2 optimum and the NMF-2 optimum through sampling matrices of size $3\times 3$ was witnessed. Furthermore, some zero patterns were never encountered as the optimum in the sampling. In this thesis, I continue the experiments for $3\times 4$ and $4\times 4$ matrices to see whether these observations still hold in the larger setting. To find the best nonnegative rnak-2 matrix approximation, we first identify the relevant zero patterns, compute the ED degrees for the corresponding algebraic varieties, and finally solve the problem numerically for uniformly random integer matrices. We were able to characterize the relevant zero patterns to three types of patterns, and prove that no other patterns may occur as an optimum in the $3\times 3$, $3\times 4$, and $4\times 4$ cases. We also investigated further the connection between the negative entries of the rank-2 optimum and the optimum pattern, but based on the numerical results, the optimum pattern cannot be directly read from the negative entries of the rank-2 optimum as witnessed in the sampling of $3\times 3$ matrices.Matriisin $X\in \RR^{m\times n}$ epänegatiivinen asteen $r$ matriisihajotelma (EMH) on muotoa $X = WH$, missä $W \in \RR^{m\times r}$, $H \in \RR^{r\times n}$ ja $W$ sekä $H$ ovat epänegatiivisia matriiseja Matriisin epänegatiivinen aste, $\nrnk{X}$, on pienin $r$, jolle tällainen hajotelma voidaan muodostaa. Jos matriisi $X$ on epänegatiivinen toisen asteen matriisi, niin $\rnk{X} = \nrnk{X}$. EMH-$r$-ongelmassa tavoitteena on arvioida annettua datamatriisia $U\in \RR^{m\times n}$ matriisilla, jonka epänegatiivinen aste on korkeintaan $r$. Paras EMH-arvio on matriisia $U$ lähin piste epänegatiivisten asteen $r$ matriisien joukossa. EMH-ongelmalla on sovellutuksia monentyyppisissä data-analyysin tehtävissä, kuten kuvankäsittelyssä, tekstinlouhinnassa sekä signaalinkläsittelyssä. Koska EMH:n matriisikomponentit ovat epänegatiivisia, ei matriisitulossa tapahdu termien kumoutumista, ja matriisin EMH pääsee luonnostaan korostamaan tärkeitä, toistuvia piirteitä datassa. EMH-ongelman laskennallista haastavuutta ei vielä tunneta edes toisen asteen matriisiarvioille. EMH-1-ongelma sen sijaan on todistetusti ratkaistavissa polynomisessa ajassa. EMH-ongelma voidaan suurpiirteisesti ratkaista käyttäen polynomista ANLS-algoritmia, mutta algoritmi ei takaa parhaan arvion löytymistä. Tässä tutkielmassa käsittelemme ongelman ratkaisua pienille matriiseille ($3\times 4$, $4\times 4$). Lähestymme onglemaa algebrallisesti, jotta voimme taata löytämämme pisteen optimaalisuuden. Kun tunnemme ongelman kriittisten pisteiden lukumäärän (euklidisen etäisyyden aste, EE-aste) etukäteen, ratkaistessamme ongelmaa voimme varmistaa, että kaikki kriittiset pisteet on löydetty onnistuneesti. Uudelleenmäärittelemme ongelman toisen asteen arviointitehtävänä, jossa matriisin tiettyjen kohtien on oltava nollaa. Näitä kohtia kutsumme matriisin {\it nollakuvioksi}. EMH-2-onglemaa on aiemmin tutkittu artikkelissa \cite{kubjas2022exact}, jossa tutkijat havaitsivat yhteyden toisen asteen matriisiarvioinnin ja EMH-2:n välillä. Ratkaistessaan EMH-2-ongelman satunnaisille $3\times 3$ matriiseille, tiettyjä nollakuvioita ei koskaan tavattu. Tässä tutkielmassa tavoite on jatkaa kokeita $3\times 4$ ja $4\times 4$ matriiseille, jotta selviäisi, toistuvatko artikkelin \cite{kubjas2022exact} havainnot yleisemmin. Löytääksemme parhaan EMH-arvion, määrittelemme ensin tarvittavat nollakuviot, laskemme niiden EE-asteen ja lopuksi ratkaisemme ongelman numeerisesti satunnaisille tasajakautuneille matriiseille. Onnistuimme rajaamaan mahdolliset nollakuviot kolmentyyppisiin nollakuvioihin, ja todistamme, että muuntyyppisiä nollakuvioita ei voi esiintyä $3\times 4$ ja $4\times 4$ tapauksissa. Lisäksi tutkimme tarkemmin toisen asteen arvion yhteyttä ongelmaan, ja toteamme numeeristen tulosten perusteella, ettei parasta toisen asteen arviota voi suoraan käyttää parhaan nollakuvion tunnistamiseksi.Description
Supervisor
Kubjas, KaieThesis advisor
Sodomaco, LucaKeywords
NMF, Euclidean distance degree, low-rank matrix approximations, homotopy continuation
