Graph Laplacians on the sphere for rotation equivariant neural networks

A fundamental problem in signal processing is to design computationally efficient algorithms to filter signals. In many applications, the signals to filter lie on a sphere. Meaningful examples of data of this kind are weather data on the Earth, or images of the sky. It is then important to design filtering algorithms that are computationally efficient and capable of exploiting the rotational symmetry of the problem. In these applications, given a continuous signal $f: \mathbb S^2 \rightarrow \mathbb R$ on a 2-sphere $\mathbb S^2 \subset \mathbb R^3$, we can only know the vector of its sampled values $\mathbf f \in \mathbb R^N:\ (\mathbf f)_i = f(\mathbf x_i)$ in a finite set of points $\mathcal P \subset \mathbb S^2,\quad \mathcal P = \{\mathbf x_i\}_{i=0}^{n-1}$ where our sensors are located. Perraudin et al. in "DeepSphere: Efficient spherical Convolutional Neural Network with HEALPix sampling for cosmological applications" construct a sparse graph $G$ on the vertex set $\mathcal P$ and then use a polynomial of the corresponding graph Laplacian matrix $\mathbf L \in \mathbb R^{n\times n} $ to perform a computationally efficient - $\mathcal O (n)$ - filtering of the sampled signal $\mathbf f$. In order to study how well this algorithm respects the symmetry of the problem - i.e it is equivariant to the rotation group SO(3) - it is important to guarantee that the spectrum of $\mathbf L$ and spectrum of the Laplace-Beltrami operator $\Delta_\mathbb S^2$ are somewhat ``close''. We study the spectral properties of such graph Laplacian matrix in the special case of \cite{DeepSphere} where the sampling $\mathcal P$ is the so called HEALPix sampling (acronym for \textbf Hierarchical \textbf Equal \textbf Area iso\textbf Latitude \textbf {Pix}elization) and we show a way to build a graph $G'$ such that the corresponding graph Laplacian matrix $\mathbf L'$ shows better spectral properties than the one presented in \cite{DeepSphere}. We investigate other methods of building the matrix $\mathbf L$ better suited to non uniform sampling measures. In particular, we studied the Finite Element Method approximation of the Laplace-Beltrami operator on the sphere, and how FEM filtering relates to graph filtering, showing the importance of non symmetric discrete Laplacians when it comes to non uniform sampling measures. We finish by showing how the graph Laplacian $\mathbf L'$ proposed in this work improved the performances of DeepSphere in a well known classification task using different sampling schemes of the sphere, and by comparing the different Discrete Laplacians introduced in this work in terms of equivariance error and filtering computational cost.

Un problema fondamentale in signal processing è progettare algoritmi efficienti per filtrare segnali. In molte applicazioni, i segnali da filtrare sono definiti su una sfera. Esempi di dati di questo tipo sono i dati meteo sulla Terra, o immagini del cielo. É importante progettare algoritmi di filtraggio che siano computazionalmente efficaci e capaci di sfruttare la simmetria rotazionale del problema. In tali applicazioni, dato un segnale continuo $f: \mathbb S^2 \rightarrow \mathbb R$ sulla 2-sfera $\mathbb S^2 \subset \mathbb R^3$, possiamo solo conoscere il vettore dei suoi valori samplati $\mathbf f \in \mathbb R^N:\ (\mathbf f)_i = f(\mathbf x_i)$ in un insieme finito di punti $\mathcal P \subset \mathbb S^2,\quad \mathcal P = \{\mathbf x_i\}_{i=0}^{n-1}$ dove sono locati i sensori. Perraudin et. al. in "DeepSphere: Efficient spherical Convolutional Neural Network with HEALPix sampling for cosmological applications" costruiscono un grafo $G$ sull'insieme dei vertici $\mathcal P$ e usano un polinomio della matrice grafo Laplaciano $\mathbf L \in \mathbb R^{n\times n}$ per filtrare efficacemente - $\mathcal O(n)$ - il segnale $\mathbf f$. Per studiare quanto tale algoritmo rispetti la simmetria del problema - i.e., è equivariante rispetto al gruppo di rotazioni $SO(3)$ - è importante garantire che gli autovettori di $\mathbf L$ e gli autovettori dell'operatore di Laplace-Beltrami $\Delta_\mathbb S^2$ siano ``vicini''. In questo lavoro vengono studiate le proprietà spettrali di tale matrice grafo Laplaciano nel caso speciale di DeepSphere, dove lo schema di sampling $\mathbf P$ è il cosiddetto HEALPix sampling (acronimo di Hierarchical Equal Area isoLatitude Pixelization) e viene mostrata una maniera di costruire un grafo $G'$ tale che la corrispondente matrice grafo Laplaciano $\mathbf L'$ mostra proprietà spettrali migliori che quelle del grafo presentato in DeepSphere. Vengono investigati successivamente altri metodi di costruire tale matrice $\mathbf L$, meglio adatti a schemi di sampling meno uniformi di HEALPix. In particolare, viene studiata la matrice fornita dal Metodo agli Elementi Finiti, e come il filtraggio ottenuto con il FEM si rapporta con il filtraggio definito sul grafo $G'$, mostrando l'importanza di avere un Laplaciano discreto non simmetrico nel caso di sampling non uniformi. Infine viene dimostrato come il grafo Laplaciano proposto in questo lavoro migliori le prestazioni di DeepSphere in un noto problema di classificazione usando differenti sampling della sfera, e vengono comparati i differenti Laplaciani discreti introdotti in questo lavoro in termini di errore di equivarianza e costo computazionale del corrispondente filtraggio.