On the optimal sampling design for the Graph Total Variation decoder: recovering piecewise-constant graph signals from a few vertex measurements

Rodrigo Cerqueira Gonzalez Pena
EPFL, 2020
Thèse EPFL

Résumé

Compressed Sensing teaches us that measurements can be traded for offline computation if the signal being sensed has a simple enough representation. Proper decoders can exactly recover the high-dimensional signal of interest from a lower-dimensional vector of that signal's observations. In graph domains -- like social, similarity, or interaction networks -- the relevant signals often have to do with the network's cluster structure. Partitioning a graph into different communities induces a piecewise-constant signal, an object that can be decoded via Graph Total Variation (G-TV) minimization even if it is not fully observed. In fact, assume that such a signal can only be accessed by querying vertices at random. Then, we could sensibly ask: what are the sampling probabilities that minimize the number of queries required for a successful G-TV recovery? This thesis is an attempt to answer this question through the study of the success conditions in G-TV minimization programs. I show that the recovery error in these programs undergoes a phase transition in terms of the number of measurements, with a threshold that explicitly depends on the vertex-sampling probabilities. It suffices to minimize this threshold to obtain an optimal sampling design. Yet, sampling optimally in practice has problems of its own. While numerical experiments reveal that it is important to focus on the places of the graph where the signal varies, implementing the optimal design without actually knowing the signal-to-be-sampled remains an open issue.

Official source

https://infoscience.epfl.ch/record/273708?ln=fr

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Rodrigo Cerqueira Gonzalez Pena
EPFL, 2020
Thèse EPFL

Résumé

Official source

https://infoscience.epfl.ch/record/273708?ln=fr

À propos de ce résultat

Concepts associés (10)

Concepts associés

Chargement

Publications associées (1)

Publications associées

Chargement

Compressive Sampling Strategies for Multichannel Signals

Mohammad Golbabaee

Over the past decade researches in applied mathematics, signal processing and communications have introduced compressive sampling (CS) as an alternative to the Shannon sampling theorem. The two key observations making CS theory widely applicable to numerous areas of signal processing are: i) due to their structural properties, natural signals typically have sparse representations in properly chosen orthogonal bases, ii) the number of linear non-adaptive measurements required to acquire high-dimensional data with CS is proportional to the signal’s sparsity level in the chosen basis. In multichannel signal applications the data of different channels is often highly correlated and therefore the unstructured sparsity hypothesis deployed by the classical CS theory results in suboptimal measurement rates. Meanwhile, the wide range of applications of multichannel signals and the extremely large and increasing flow of data in those applications motivates the development of more comprehensive models incorporating both inter and intra-channel data structures in order to achieve more efficient dimensionality reduction. The main focus of this thesis is on studying two new models for efficient multichannel signal compressed sensing. Our first approach proposes a simultaneous low-rank and joint-sparse matrix model for multichannel signals. As a result, we introduce a novel CS recovery scheme based on Nuclear-l2/l1 norm convex minimization for low-rank and joint-sparse matrix approximation. Our theoretical analysis indicates that using this approach can achieve significantly lower sampling rates for a robust multichannel data CS acquisition than state-of-the-art methods. More remarkably, our analysis confirms the near-optimality of this approach: the number of CS measurements are nearly proportional to the few degrees of freedom of such structured data. Our second approach introduces a stronger model for multichannel data synthesized by a linear mixture model. Here we assume that the mixture parameters are given as side information. As a result, multichannel data CS recovery turns into a compressive source separation problem, where we propose a novel decorrelating scheme to exploit the knowledge of mixture parameters for a robust and numerically efficient source identification. Our theoretical guarantees explain the fundamental limits of this approach in terms of the number of CS measurements, the sparsity level of sources, the sampling noise, and the conditioning of the mixture parameters. We apply these two approaches to compressive hyperspectral image recovery and source separation, and compare the efficiency of our methods to state-of-the-art approaches for several challenging real-world hyperspectral datasets. Note that applications of these methods are not limited to hyperspectral imagery and it can have a broad impact on numerous multichannel signal applications. As an example, for sensor network applications deploying compressive sampling schemes, our results indicate a tight tradeoff between the number of available sensors (channels) and the complexity/cost of each sensor. Finally, in a different multichannel signal application, we deal with a simple but very important problem in computer vision namely the detection and localization of people given their multi-view silhouettes captured by networks of cameras. The main challenge in many existing solutions is the tradeoff between robustness and numerical efficiency. We model this problem by a boolean (non-linear) inverse problem where, by penalizing the sparsity of the solution, we achieve accurate results comparable to state-of-the-art methods. More remarkably, using boolean arithmetics enables us to propose a real-time and memory efficient approximation algorithm that is mainly rooted in the classical literature of group testing and set cover.

EPFL2012

Chargement

Compressive Sampling Strategies for Multichannel Signals

Mohammad Golbabaee

EPFL2012