Graph Laplacians for Rotation Equivariant Convolutional 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 \cite{DeepSphere} 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 different 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.

Scalable Low-rank Matrix and Tensor Decomposition on Graphs

Nauman Shahid

In many signal processing, machine learning and computer vision applications, one often has to deal with high dimensional and big datasets such as images, videos, web content, etc. The data can come in various forms, such as univariate or multivariate time series, matrices or high dimensional tensors. The goal of the data mining community is to reveal the hidden linear or non-linear structures in the datasets. Over the past couple of decades matrix factorization, owing to its intrinsic association with dimensionality reduction has been adopted as one of the key methods in this context. One can either use a single linear subspace to approximate the data (the standard Principal Component Analysis (PCA) approach) or a union of low dimensional subspaces where each data class belongs to a different subspace. In many cases, however, the low dimensional data follows some additional structure. Knowledge of such structure is beneficial, as we can use it to enhance the representativity of our models by adding structured priors. A nowadays standard way to represent pairwise affinity between objects is by using graphs. The introduction of graph-based priors to enhance matrix factorization models has recently brought them back to the highest attention of the data mining community. Representation of a signal on a graph is well motivated by the emerging field of signal processing on graphs, based on notions of spectral graph theory. The underlying assumption is that high-dimensional data samples lie on or close to a smooth low-dimensional manifold. Interestingly, the underlying manifold can be represented by its discrete proxy, i.e. a graph. A primary limitation of the state-of-the-art low-rank approximation methods is that they do not generalize for the case of non-linear low-rank structures. Furthermore, the standard low-rank extraction methods for many applications, such as low-rank and sparse decomposition, are computationally cumbersome. We argue, that for many machine learning and signal processing applications involving big data, an approximate low-rank recovery suffices. Thus, in this thesis, we present solutions to the above two limitations by presenting a new framework for scalable but approximate low-rank extraction which exploits the hidden structure in the data using the notion of graphs. First, we present a novel signal model, called

Multilinear low-rank tensors on graphs (MLRTG)' which states that a tensor can be encoded as a multilinear combination of the low-frequency graph eigenvectors, where the graphs are constructed along the various modes of the tensor. Since the graph eigenvectors have the interpretation of \textit{non-linear} embedding of a dataset on the low-dimensional manifold, we propose a method called

Graph Multilinear SVD (GMLSVD)' to recover PCA based linear subspaces from these eigenvectors. Finally, we propose a plethora of highly scalable matrix and tensor based problems for low-rank extraction which implicitly or explicitly make use of the GMLSVD framework. The core idea is to replace the expensive iterative SVD operations by updating the linear subspaces from the fixed non-linear ones via low-cost operations. We present applications in low-rank and sparse decomposition and clustering of the low-rank features to evaluate all the proposed methods. Our theoretical analysis shows that the approximation error of the proposed framework depends on the spectral properties of the graph Laplacians

EPFL2017

Non-linear Recovery of Sparse Signal Representations with Applications to Temporal and Spatial Localization

Zafer Dogan

Foundations of signal processing are heavily based on Shannon's sampling theorem for acquisition, representation and reconstruction. This theorem states that signals should not contain frequency components higher than the Nyquist rate, which is half of the sampling rate. Then, the signal can be perfectly reconstructed from its samples. Increasing evidence shows that the requirements imposed by Shannon's sampling theorem are too conservative for many naturally-occurring signals, which can be accurately characterized by sparse representations that require lower sampling rates closer to the signal's intrinsic information rates. Finite rate of innovation (FRI) is a new theory that allows to extract underlying sparse signal representations while operating at a reduced sampling rate. The goal of this PhD work is to advance reconstruction techniques for sparse signal representations from both theoretical and practical points of view. Specifically, the FRI framework is extended to deal with applications that involve temporal and spatial localization of events, including inverse source problems from radiating fields. We propose a novel reconstruction method using a model-fitting approach that is based on minimizing the fitting error subject to an underlying annihilation system given by the Prony's method. First, we showed that this is related to the problem known as structured low-rank matrix approximation as in structured total least squares problem. Then, we proposed to solve our problem under three different constraints using the iterative quadratic maximum likelihood algorithm. Our analysis and simulation results indicate that the proposed algorithms improve the robustness of the results with respect to common FRI reconstruction schemes. We have further developed the model-fitting approach to analyze spontaneous brain activity as measured by functional magnetic resonance imaging (fMRI). For this, we considered the noisy fMRI time course for every voxel as a convolution between an underlying activity inducing signal (i.e., a stream of Diracs) and the hemodynamic response function (HRF). We then validated this method using experimental fMRI data acquired during an event-related study. The results showed for the first time evidence for the practical usage of FRI for fMRI data analysis. We also addressed the problem of retrieving a sparse source distribution from the boundary measurements of a radiating field. First, based on Green's theorem, we proposed a sensing principle that allows to relate the boundary measurements to the source distribution. We focused on characterizing these sensing functions with particular attention for those that can be derived from holomorphic functions as they allow to control spatial decay of the sensing functions. With this selection, we developed an FRI-inspired non-iterative reconstruction algorithm. Finally, we developed an extension to the sensing principle (termed eigensensing) where we choose the spatial eigenfunctions of the Laplace operator as the sensing functions. With this extension, we showed that eigensensing principle allows to extract partial Fourier measurements of the source functions from boundary measurements. We considered photoacoustic tomography as a potential application of these theoretical developments.

EPFL2015

MULAN: A Blind and Off-Grid Method for Multichannel Echo Retrieval

Rémi Gribonval, Helena Peic Tukuljac

This paper addresses the general problem of blind echo retrieval, i.e., given M sensors measuring in the discrete-time domain M mixtures of K delayed and attenuated copies of an unknown source signal, can the echo locations and weights be recovered? This problem has broad applications in fields such as sonars, seismology, ultrasounds or room acoustics. It belongs to the broader class of blind channel identification problems, which have been intensively studied in signal processing. Existing methods in the literature proceed in two steps: (i) blind estimation of sparse discrete-time filters and (ii) echo information retrieval by peak-picking on filters. The precision of these methods is fundamentally limited by the rate at which the signals are sampled: estimated echo locations are necessary on-grid, and since true locations never match the sampling grid, the weight estimation precision is impacted. This is the so-called basis-mismatch problem in compressed sensing. We propose a radically different approach to the problem, building on the framework of finite-rate-of-innovation sampling. The approach operates directly in the parameter-space of echo locations and weights, and enables near-exact blind and off-grid echo retrieval from discrete-time measurements. It is shown to outperform conventional methods by several orders of magnitude in precision.

NEURAL INFORMATION PROCESSING SYSTEMS (NIPS)2018