**Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?**

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Publication# A Game Theoretic Approach to Expander-based Compressive Sensing

Résumé

We consider the following expander-based compressive sensing (e-CS) problem: Given Φ ∈ ℝM×N (M

Official source

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

Concepts associés (15)

Optimisation (mathématiques)

L'optimisation est une branche des mathématiques cherchant à modéliser, à analyser et à résoudre analytiquement ou numériquement les problèmes qui consistent à minimiser ou maximiser une fonction sur

Sparse approximation

Sparse approximation (also known as sparse representation) theory deals with sparse solutions for systems of linear equations. Techniques for finding these solutions and exploiting them in application

Résolution de problème

vignette|Résolution d'un problème mathématique.
La résolution de problème est le processus d'identification puis de mise en œuvre d'une solution à un problème.
Méthodologie
Dans l'ind

Publications associées (12)

Chargement

Chargement

Chargement

The main goal in network information theory is to identify fundamental limits of communication over networks, and design solutions which perform close to such limits. After several decades of effort, many important problems still do not have a characterization of achievable performance in terms of a finite dimensional description. Given this discouraging state of affairs, a natural question to ask is whether there are systematic approaches to make progress on these open questions. Recently, there has been significant progress on several open questions by seeking a (provably) approximate characterization for these open questions. The main goal of approximation in network information theory is to obtain a universal approximation gap between the achievable and the optimal performance. This approach consists of four ingredients: simplify the model, obtain optimal solution for the simplified model, translate this optimal scheme and outer bounds back to the original model, and finally bound the gap between what can be achieved using the obtained technique and the outer bound. Using such an approach, recent progress has been made in several problems such as the Gaussian interference channel, Gaussian relay networks, etc. In this thesis, we demonstrate that this approach is not only successful in problems of transmission over noisy networks, but gives the first approximation for a network data compression problem. We use this methodology to (approximately) resolve problems that have been open for several decades. Not only do we give theoretical characterization, but we also develop new coding schemes that are required to satisfy this approximate optimality property. These ideas could give insights into efficient design of future network communication systems. This thesis is split into two main parts. The first part deals with the approximation in lossy network data compression. Here, a lossy data compression problem is approximated by a lossless counterpart problem, where all the bits in the binary expansion of the source above the required distortion have to be losslessly delivered to the destination. In particular, we study the multiple description (MD) problem, based on the multi-level diversity (MLD) coding problem. The symmetric version of the MLD problem is well-studied, and we can directly use it to approximate the symmetric MD problem. We formulate the asymmetric multi-level diversity problem, and solve it for three-description case. The optimal solution for this problem, which will be later used to approximate the asymmetric multiple description problem, is based on jointly compressing of independent sources. In both symmetric and asymmetric cases, we derive inner and outer bounds for the achievable rate region, which together with the gap analysis, provide an approximate solution for the problem. In particular, we resolve the symmetric Gaussian MD problem, which has been open for three decades, to within 1 bit. In the second part, we initiate a study of a Gaussian relay-interference network, in which relay (helper) nodes are to facilitate competing information flows over a wireless network. We focus on a two-stage relay-interference network where there are weak cross-links, causing the networks to behave like a chain of Z Gaussian channels. For these Gaussian ZZ and ZS networks, we establish an approximate characterization of the rate region. The outer bounds to the capacity region are established using genie-aided techniques that yield bounds sharper than the traditional cut-set outer bounds. For the inner bound of the ZZ network, we propose a new interference management scheme, termed interference neutralization, which is implemented using structured lattice codes. This technique allows for over-the-air interference removal, without the transmitters having complete access to the interfering signals. We use insights gained from an exact characterization of the corresponding linear deterministic version of the problem, in order to study the Gaussian network. We resolve the Gaussian relay-interference network to within 2 bits. The new interference management technique (interference neutralization) shows the use of structured lattice codes in the problem. We also consider communication from a source to a destination over a wireless network with the help of a set of authenticated relays, and presence of an adversarial jammer who wishes to disturb communication. We focus on a special diamond network, and show that use of interference suppression (nulling) is crucial to approach the capacity of the network. The exact capacity characterization for the deterministic network, along with an approximate characterization (to within 4 bits) for the Gaussian network is provided. The common theme that binds the diverse network communication problems in this thesis is that of approximate characterization, when exact resolutions are difficult. The approach of focusing on the deterministic/lossless problems underlying the noisy/lossy network communication problems has allowed us to develop new techniques to study these questions. These new techniques might be of independent interest in other network information theory problems.

This paper addresses the problem of dense disparity estimation in networks of omnidirectional cameras. We propose to map omnidirectional images on the 2-sphere, and we perform disparity estimation directly on the sphere in order to preserve the geometry of images. We ﬁrst perform rectiﬁcation of the images in the spherical domain. Then we formulate a global energy minimization problem for the estimation of disparity on the sphere. We solve the optimization problem with a graph-cut algorithm, and we show that the proposed solution outperforms common methods based on block matching, for both synthetic scenes with varying complexity and complex natural scenes. Then, we propose a parallel implementation of the graph-cut algorithm that is able to perform dense depth estimation with an improved speed-up, which makes it suitable for realtime applications. Finally, we extend the spherical depth estimation framework to networks of multiple cameras, and we design two methods for dense depth estimation that are based respectively on disparity computation with pairs of images, or computation of inverse depth values. Both methods are shown to provide promising results towards depth estimation in networks of omnidirectional cameras. keywords: disparity estimation depth estimation omnidirectional imaging spherical images camera networks

2009,

The distributed representation of correlated images is an important challenge in applications such as multi-view imaging in camera networks or low complexity video coding. This paper addresses the problem of distributed coding of images whose correlation is driven by the motion of objects or the positioning of the vision sensors. It concentrates on the problem where images are encoded with compressed linear measurements, which are used for estimation of the correlation between images at decoder. We propose a geometry-based correlation model in order to describe the correlation between pairs of images. We assume that the constitutive components of natural images can be captured by visual features that undergo local transformations (e.g., translation) in different images. These prominent visual features are estimated with a sparse approximation of a reference image by a dictionary of geometric basis functions. The corresponding features in the other images are then identified from the compressed measurements. The correlation model is given by the relative geometric transformations between corresponding features. We thus formulate a regularized optimization problem for the estimation of correspondences where the local transformations between images form a consistent motion or disparity map. Then, we propose an efficient joint reconstruction algorithm that decodes the compressed images such that they stay consistent with the quantized measurements and the correlation model. Experimental results show that the proposed algorithm effectively estimates the correlation between images in video sequences or multi-view data. In addition, the proposed reconstruction strategy provides effective decoding performance that compares advantageously to distributed coding schemes based on disparity or motion learning and to independent coding solution based on JPEG-2000.

2010