# Réunion

## Dernières avancées en théorie de l'information

**Date :**6-04-2012

**Lieu :**Télécom ParisTech, 6 avril 2012

**Thèmes scientifiques :**

- D - Télécommunications : compression, protection, transmission

Nous vous rappelons que, afin de garantir l'accès de tous les inscrits aux salles de réunion, **l'inscription aux réunions est gratuite mais obligatoire**.

### Inscriptions

14 personnes membres du GdR ISIS, et 0 personnes non membres du GdR, sont inscrits à cette réunion.

Capacité de la salle : 100 personnes.

### Annonce

Cette journée thématique organisée par le GdR ISIS est consacrée aux dernières recherches dans le domaine de la théorie de Shannon et de ses applications.

Dès sa naissance en 1948, la théorie de l'information a produit une révolution dans la compréhension des systèmes de communication et des réseaux de données. Depuis, cette théorie a trouvé de nombreuses applications dans domaines aussi divers que la cryptographie, l'analyse combinatoire, la biologie, la thermodynamique, l'économie, ou l'analyse du langage.

Au cours de cette journée, certaines parmi les thématiques de recherche les plus actuelles en théorie de l'information seront abordées.

**Organisateurs :**

- Walid Hachem (walid.hachem@telecom-paristech.fr)
- Aslan Tchamkerten (aslan.tchamkerten@telecom-paristech.fr)
- Michèle Wigger (michele.wigger@telecom-paristech.fr)

### Programme

9h30-9h40 : Accueil

9h40-10h20 : Emre Telatar (Ecole Polytechnique Fédérale de Lausanne), Polar Codes

10h20-11h00 : Matthieu Bloch (Georgia Tech Lorraine), Physical-Layer Security: Information Theory and Secure Communications

11h00-11h10 : Pause

11h10-11h50 : Giuseppe Caire (University of Southern California), Information theoretic bounds and statistical physics analysis of sparse signals support recovery.

11h50-12h30 : Aslan Tchamkerten (Télécom ParisTech), The Price of Asynchronism in Bursty Communication

12h30-14h00 : Déjeuner

14h00-14h40 : Abdellatif Zaidi (Université Paris Est Marne-la-Vallée), On Optimal Compressions for a State-Dependent Multiaccess Channel: Wyner-Ziv Type Versus Noisy Network Coding

14h40-15h20 : Janos Korner ("Sapienza" University of Rome), Information theory and combinatorics: from strings to graphs

15h20-16h00 : Mari Kobayashi (Supélec), Degrees of Freedom of Time Correlated MISO Broadcast Channel with Delayed CSIT.

16h00-16h10 : Pause

16h10-16h50 : François Baccelli (INRIA et ENS), Error Exponents for Stationary and Ergodic Additive Noise.

16h50-17h30 : Michèle Wigger (Télécom ParisTech), Benefits of Feedback for Memoryless Multi-Access and Broadcast Channels

### Résumés des contributions

### Error Exponents for Stationary and Ergodic Additive Noise

**François Baccelli (INRIA et ENS).**

We will revisit some of the most basic capacity and error exponent questions of information theory in terms of random geometric objects living in Euclidean spaces with dimensions tending to infinity.

This approach allows one to use the theory of large deviations to evaluate random coding error exponents in channels with additive stationary and ergodic noise.

### Physical-Layer Security: Information Theory and Secure Communications

**Matthieu Bloch (Georgia Tech Lorraine)**

While information-theory is often recognized for its foundational role in the development of reliable communications, there has recently been a renewed interest for the analysis of secure communications. The study of security from a information-theoretic perspective breaks away from traditional approaches by explicitly accounting for imperfections in the communication medium and exploiting them to jointly handle confidentiality and reliability. Since the noise of the physical-layer plays a central-role, the area is now colloquially known as "physical-layer security".

In this talk, we will discuss the opportunities and challenges for future research in physical-layer security. We will use the example of key generation over wireless channels to highlight how mathematical tools and techniques from information theory, coding theory, wireless communications, and cryptography can be leveraged to develop secure communication schemes for the next generation of wireless networks.

### Information theoretic bounds and statistical physics analysis of sparse signals support recovery.

**Giuseppe Caire (University of Southern California)**

We consider the support recovery of a sparse signal observed through a rank-deficient linear transformation in Gaussian background noise. This problem is similar to the classical noisy compressed sensing problem, with the difference that we care only about the support estimation (i.e., the position of the non-zero signal components).

In addition, we consider the support recovery error rate, i.e., the Hamming distance between the binary vector indicating the support of the original signal and the binary vector indicating the estimated support, normalized by the signal block length. We consider a rather general class of ''sensing matrices'' satisfying a given freeness condition.

For such problem, we develop an information theoretic rate-distortion lower bound on the achievable support recovery error rate. Also, we use the replica method of statistical physics to analyze the performance of the optimal MAP estimator (not implementable in practice) and of some practical estimators, such as a thresholded linear MMSE estimator and the Lasso estimator (L1 reconstruction with L2 norm bias) widely studied in the compressed sensing literature. The results of the replica analysis match very well with the information theoretic bounds.

Joint work with Antonia Tulino, Sergio Verdu and Shlomo Shamai.

### Degrees of Freedom of Time Correlated MISO Broadcast Channel with Delayed CSIT

**Mari Kobayashi (Supélec)**

We consider the time correlated MISO broadcast channel where the transmitter has imperfect knowledge on the current channel state, in addition to delayed channel state information. By representing the quality of the current channel state as $P^{-\alpha}$ for the signal-to-noise ratio $P$ and some constant $\alpha \geq 0$, we characterize the optimal degree of freedom region for this more general two-user MISO broadcast correlated channel. The essential ingredients of the proposed scheme lie in the quantization and multicasting of the overheard interferences, while broadcasting new private messages. Our proposed scheme smoothly bridges between the scheme recently proposed by Maddah-Ali and Tse with no current state information and a simple zero-forcing beamforming with perfect current state information.

### Information theory and combinatorics: from strings to graphs

**Janos Körner ("Sapienza" University of Rome)**

A huge part of extremal combinatorics can be interpreted as formally information–theoretic problems about optimal codes for various channels. From a purely mathematical point of view similar problems emerge about "very different graphs" instead of very different strings from a finite alphabet. We present some recent and even unpublished results within this framework.

### The Price of Asynchronism in Bursty Communication

**Aslan Tchamkerten (Télécom ParisTech)**

The traditional information theory approach to reliable communication ignores issues related to synchronization and assumes that the receiver is cognizant of the message transmission period.

However, in a growing number of applications, such as many involving sensor networks, transmissions are very bursty, with very small amounts of data to be transmitted once in a long while. And for such settings, the cost of acquiring synchronization can be very significant because the number of bits transmitted per burst is relatively small.

What are the fundamental limitations due to the lack of a priori synchrony between the transmitter and the receiver in bursty communication? We will provide answers to this questions when the performance criterion is either the delay or the energy needed to convey a message. A practical implication of these results is that training based architectures where synchronization and information transmission are treated separately perform suboptimally in general.

### Polar Codes

**Emre Telatar (Ecole Polytechnique Fédérale de Lausanne)**

Polar coding is a technique discovered by Arikan to construct error correcting codes for binary input channels. These codes are provably capable of achieving the 'symmetric capacity' of any channel, have low encoding and decoding complexity, and are constructed in a completely explicit fashion. They remain the only family of codes which possess all these qualities. The talk will describe the codes, explain their qualities, and discuss some open questions.

### Benefits of Feedback for Memoryless Multi-Access and Broadcast Channels

**Michèle Wigger (Télécom ParisTech)**

In this talk, we analyze the benefits in capacity that feedback can afford for memoryless multi-access channels (MAC) and broadcast channels (BC). We will show that while for memoryless MACs perfect(noise-free) feedback provides only a bounded cooperation-gain, for some memoryless BCs the gain thanks to perfect feedback can be unbounded. We will also study how these gains persist under noisy or partial feedback.

In the first part of the talk, we focus on discrete memoryless MACs and BCs. We present coding schemes for these channels with perfect feedback. The schemes illustrate the benefits of feedback for memoryless MACs and BCs, and moreover achieve capacity for specific classes or examples of channels. We also discuss extensions of these schemes to noisy or partial feedback.

In the second part, we consider Gaussian memoryless MACs and BCs. We present Ozarow's capacity-achieving scheme for the Gaussian MAC with perfect feedback, and show how it can be robustified to perform well also under noisy or partial feedback. It turns out that for this setup: noisy feedback is always useful, no matter how noisy; and "almost noise-free" feedback is almost as useful as noise-free feedback. For the Gaussian BC with perfect feedback the capacity is still unknown. We present different schemes for this latter setup, and show that the schemes achieve the sum-capacity in the asymptotic high-SNR regime. The schemes also exhibit that for the Gaussian BC perfect feedback can provide unbounded gain in capacity. We conclude the talk by discussing duality relationships between Ozarow's capacity-achieving scheme for the Gaussian MAC and a family of linear-feedback schemes for the Gaussian BC.

The talk is based on joint work with Michael Gastpar, Amos Lapidoth, Yossef Steinberg, and Ofer Shayevitz.

### On Optimal Compressions for a State-Dependent Multiaccess Channel: Wyner-Ziv Type Versus Noisy Network Coding

**Abdellatif Zaïdi (Université Paris Est Marne-la-Vallée)**

The study of channels that are controlled by random states has spurred much interest, due to its importance from both information-theoretic and communications aspects. For example, state-dependent channels may model communication in random fading environments or in the presence of interference imposed by adjacent users. The channel states may be known in a strictly-causal, causal or noncausal manner, to all or only a subset of the encoders.

There is a connection between the role of states known strictly causally at an encoder and that of output feedback given to that encoder. In single-user channels, it is now well known that strictly causal feedback does not increase the capacity. In multiuser channels or networks, however, the situation changes drastically, and output feedback can be beneficial --- but its role is still highly missunderstood. One has a similar picture with strictly causal states at the encoder. In single-user channels, independent and identically distributed states available only in a strictly causal manner at the encoder have no effect on the capacity. In multiuser channels or networks, however, like feedback, strictly causal states in general increase the capacity.

In this talk, we consider a two-user state-dependent multiaccess channel with degraded message sets, and show that outdated states are of some utility. We find explicit characterizations of the capacity region of this communication model in both discrete memoryless and memoryless Gaussian cases. The analysis also reveals optimal ways of exploiting the knowledge of the state only strictly causally at the encoder that sends only the common message when such a knowledge is beneficial. The encoders collaborate to convey to the decoder a lossy version of the state, in addition to transmitting the information messages through a generalized Gel'fand-Pinsker binning. Particularly important in this problem are the questions of 1) optimal ways of performing the state compression and 2) whether or not the compression indices should be decoded uniquely. We show that both compression \`a-la noisy network coding, i.e., with no binning, and compression using Wyner-Ziv binning are optimal. The scheme that uses Wyner-Ziv binning shares elements with Cover and El Gamal original compress-and-forward, but differs from it mainly in that backward decoding is employed instead of forward decoding and the compression indices are not decoded uniquely.