Riduzione della dimensionalità tramite proiezioni casuali: fondamenti teorici e analisi pratica del lemma di Johnson-Lindestrauss

L'analisi moderna dei dati ad alta dimensionalità è sistematicamente ostacolata dalla cosiddetta "Maledizione della Dimensionalità", un fenomeno che fa collassare le metriche di similarità spaziale e rende algoritmi deterministici guidati dai dati, come l'Analisi delle Componenti Principali (PCA), computazionalmente proibitivi su larga scala. Questo elaborato esplora un paradigma alternativo oblivious basato sul Metodo Probabilistico: la riduzione della dimensionalità tramite Proiezioni Casuali, fondata sul Lemma di Johnson-Lindenstrauss. Nella prima parte, la tesi ricostruisce il rigoroso impianto teorico che garantisce il funzionamento del Teorema, smontando le dinamiche della Concentrazione della Misura. Attraverso l'analisi delle variabili sub-Gaussiane e l'applicazione della disuguaglianza di Bernstein per le code miste, si dimostra formalmente come una matrice popolata da variabili casuali indipendenti possa proiettare i dati in uno spazio a dimensione radicalmente inferiore, preservandone quasi interamente le distanze euclidee reciproche. Nella seconda parte, l'impianto teorico viene validato empiricamente sul dataset di immagini MNIST (D=784), confrontando le Proiezioni Casuali con la PCA tramite l'addestramento di un classificatore K-Nearest Neighbors (K=3). I risultati confermano l'esistenza di un netto compromesso dimensionale: a bassissima dimensionalità (k=20), la natura data-driven della PCA garantisce prestazioni superiori. Tuttavia, superata la soglia necessaria all'innesco del fenomeno geometrico del Thin Shell ( K>= 100), le Proiezioni Casuali annullano il divario. Per k=200, il metodo probabilistico recupera la struttura geometrica originaria raggiungendo un'accuratezza di classificazione del 93-94% in frazioni centesimali di secondo, dimostrandosi una soluzione altamente scalabile ed efficiente per l'elaborazione di dati massivi.