La decomposizione ai valori singolari (SVD) è uno strumento fondamentale dell’algebra lineare numerica, ma per matrici di enormi dimensioni il suo costo computazionale è proibitivo. L’approssimazione dei valori singolari è quindi cruciale in vari campi della matematica, dell’ingegneria e data science. Questa operazione è spesso parte di processi più ampi nei quali è possibile ottenere un’approssimazione dei sottospazi singolari tramite metodi come la bi-diagonalizzazione di Golub-Kahan, iterazioni sui sottospazi o tecniche randomizzate.
In questa presentazione introdurremo strumenti per estrarre valori singolari da approssimazioni ortonormali di sottospazi singolari, esaminando tecniche classiche come Rayleigh-Ritz e la proiezione SVD (su un lato), confrontandole con approcci più recenti come la SVD randomizzata (HMT) e il metodo di Nyström generalizzato (GN), che forniscono approssimazioni sorprendentemente significamente più accurate. Includeremo la necessaria introduzione alle approssimazioni di basso rango, un altro grande problema legato alla SVD, e alla randomizzazione, tecnica di grande impatto nell’algebra lineare numerica.
Analizzeremo infine l’accuratezza di queste tecniche utilizzando la teoria delle perturbazioni di matrice, per confrontare i vari metodi e giustificare le osservazioni dedotte da esperimenti numerici.
Siamo interessati alla soluzione numerica del problema ai minimi quadrati sia in forma matriciale
$$\min\limits_{X \in \mathbb{R}^{m \times m}} \Vert C_1C_2^T \, – \, A_1XB_1 \, – \, A_2XB_2\Vert_F$$
sia in forma tensoriale
$$\min\limits_{X \in \mathbb{R}^{m \times m\times \ldots \times m}} \Vert \mathcal{D} \,- \sum\limits_{i=1}^p \mathcal{X} \times_1 A^{(i)} \times_2 B^{(i)} \times_3 C^{(i)}\Vert_F$$
dove $C = C_1C_2^T$ e $\mathcal{D}$ hanno rango basso. Per chiarezza ci concentreremo sul caso p = 2,3, osservando che la generalizzazione a un numero maggiore di termini avviene in maniera naturale. Ci concentreremo inizialmente sulla derivazione dell’algoritmo LSQR in forma matriciale e tensoriale. Successivamente, deriveremo le rispettive versioni troncate, mostrando come, nei casi in cui la soluzione abbia basso rango, il troncamento influenzi l’algoritmo. Nel caso matriciale è particolarmente interessante il confronto con il metodo dei Gradienti Coniugati (CG), già studiato nella sua versione matriciale e troncata. Sempre nel caso matriciale, mostreremo un’applicazione al problema del Dictionary Learning. Per il caso tensoriale, mostreremo un’applicazione per la soluzione numerica di PDE.
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.
