La Fattorizzazione di matrici (MF) mira a decomporre una matrice di dati $X \in \mathbb{R}^{m \times n}$, dove le $n$ colonne rappresentano dei campioni di dimensione $m$, nel prodotto di due matrici più piccole, $W \in \mathbb{R}^{m \times r}$ e $H \in \mathbb{R}^{r \times n}$ , per cui $X \approx WH$. Spesso è cruciale imporre vincoli aggiuntivi ai fattori, come sparsità o non-negatività, per migliorare per esempio l’interpretabilità dei risultati.

Quando $W$ ha tante colonne quanto la sua dimensione affine più uno e tutte le colonne di $H$ sono stocastiche, si parla di fattorizzazione di matrici con struttura di simplesso (SSMF). Questo problema cerca un simplesso che racchiuda o approssimi al meglio i dati a disposizione. Il modello ha diverse applicazioni nel machine learning, con due esempi prominenti che includono l'”unmixing” di immagini iperspettrali e l’estrazione di topic nell’ambito dell’analisi testuale.

Nell’illustrare la teoria della SSMF, ci concentreremo sulle proprietà (separabilità, SSC) che rendono la fattorizzazione “unica”, e sui suoi legami con la Fattorizzazione di Matrici Non Negative (NMF). Presenteremo dunque alcuni degli algoritmi classici per calcolare la SSMF esatta quando esiste, e come si comporta in presenza di rumore. In particolare, discuteremo dell’Algoritmo delle Proiezioni Successive (SPA), delle sue varianti, e del metodo del Simplesso di Volume Minimo (MVES).

Introdurremo poi il concetto di dualità e lavoreremo sulla corrispondenza tra gli spazi primali e duali per fornire una nuova prospettiva sul come trovare un simplesso che modelli al meglio i dati. Dato una qualsiasi insieme $\mathcal S \subseteq \mathbb R^d$, il suo polare, denotato $\mathcal S^*$, è definito come
\[
\mathcal S^* := \left\{ \theta \in \mathbb R^d \, \big| \, \theta^\top x \le 1\,\, \text{ for all } x\in \mathcal S \right\}.
\]
\noindent Se $\mathcal S$ è un simplesso, allora $\mathcal S^*$ è un simplesso i cui vertici corrispondono alle facce di $\mathcal S$, e le relazioni di inclusione tra insiemi convessi sono invertite. Dopo un preprocessing, possiamo ridurre il problema a trovare una decomposizione per una matrice $$Y \in \mathbb R^{r-1 \times n}$$ che soddisfi $Y = P H$, con $H$ stocastica, o in maniera equivalente $\text{conv}(P)^* \subseteq \text{conv}(Y)^*$, che può essere scritto come $Y^\top \Theta \leq 1_{n \times r}$ dove $\text{conv}(\Theta) = \{ x \ | \ P^\top x \leq e \} = \text{conv}(P)^*$.

L’idea è dunque di massimizzare il volume di $\text{conv}(\Theta)$ nello spazio duale, legandoci così al metodo MVES che invece si proponeva di minimizzare il volume di $\text{conv}(P)^*$ nello spazio primale. Il problema finale sarà dato dal seguente modello
: dato $Y \in \mathbb{R}^{r-1 \times n}$, risolvere
\begin{equation} \label{eq:firstformupolar}
\max_{\Theta \in \mathbb{R}^{r-1 \times r}} \text{vol}\big( \text{conv}(\Theta) \big) \quad \text{ tale che } \quad Y^\top \Theta \leq 1_{n \times r}. \hspace{1cm} (1) \end{equation}
Discuteremo in dettaglio come risolvere (1) e delle sue garanzie di identificabilità quando i dati sono separabili, o quando la SSC (Condizione di Sufficiente Dispersione) è soddisfatta. Introduciamo anche il concetto di $\eta$-espansione dei dati per studiare anche cosa succede nei casi intermedi. Concludiamo fornendo degli esperimenti numerici su set di dati sia sintetici che reali, comparando il metodo sviluppato con SPA, MVES e altri algoritmi, e mostrando così che l’algoritmo proposto compete favorevolmente con lo stato dell’arte.