ITW 2007 (Tahoe) : Day Two

  • Plenary Talk: Source and Channel Coding: Theory, Practice and System Aspects (Giuseppe Caire)

    This focus of this talk was on the benefits of using joint source channel coding for more “practical” systems. The main motivation was the catastrophic behavior of excess channel errors on source reconstruction. If you optimally compress an image and send it over a noisy channel, the reconstruction becomes terrible if the channel is a bit noisier than you expected. Since wireless channel variations are a real problem, this can have a real impact. Can we have a graceful degradation in the reconstruction quality via JSSC? He also gave two more examples, one from beamforming on the MIMO broadcast channel, and one about multicasting a Gaussian source over a Gaussian MAC using a Costa-like layering construction.

  • The Case for Structured Random Codes in Network Communication Theorems (Bobak Nazer and Michael Gastpar)

    This paper focused on giving some motivations for exploiting a structured approach to random codes, rather than the standard information theoretic constructions we all know and love. For problems such as computing over a multiple-access channel, linear network coding, or interference networks, separating source and channel coding can result in performance losses. A simple scheme based on lattices can get better performance in these cases.

  • On Separation in the Presence of Feedback (Haim Permuter and Tsachy Weissman)

    It is well-known that separation is optimal for point-to-point channels and that the directed mutual information gives the capacity of channels with feedback. For ergodic channels, they show that for construction with distortion D the condition CFB > R(D) is necessary and sufficient, which shows that separation is optimal in this setting as well. For certain MACs which can be decomposed into a “multiplexer plus point-to-point” channel, they can show a similar result. In the talk they also looked at a binary MAC with stationary ergodic noise and feedback, and showed that separation is optimal there. Their results extend to mod-additive MACs.

  • Equivalence of LP Relaxation and Max-Product for Weighted Matching in General Graphs (Sujay Sanghavi)

    The problem of maximum weight matching in a graph with edge weights is to find the largest weight set of disjoint edges. One algorithm for doing this is max-product, which is an iterative message passing algorithm. The matching problem can also be posed as an integer program, which has a linear programming relaxation. Sujay shows that the performance of max-product is tied to the tightness of the LP — if the LP is tight then MP converges to the correct answer, and if the LP is loose then MP will not converge. This provides a nice guarantee of when MP will converge that ties together the iterative and linear-programming approaches to optimization on graphs. Clearly this has relations to decoding, but I’ll let Alex comment on those.

  • On the Duality and Difference Between Slepian-Wolf Coding and Channel Coding (Jun Chen, Da-ke He, Ashish Jagmohan, and Luis A. Lastras-Montano)

    This paper explored the similarities between channel coding and Slepian-Wolf coding. The comment made by Jun Chen at the talk was that the “difference” mentioned in the title is actually another kind of duality. By duality, they are referring to a kind of mirror pairing of the error exponents for source and channel coding. Using relations between linear coding strategies shows that nonlinear Slepian Wolf codes can strictly outperform linear codes.

  • On Network Interference Management (Aleksandar Jovicic, Hua Wang, and Pramod Viswanath)

    This paper looked at two basic interference patterns — one long range link causing problems for many short range links, and one long range link experiencing interference from many short links. The question is this — is orthogonalization/degree-of-freedom sharing/reuse optimal? They characterize the high SNR degree-of-freedom range for both scenarios using a multi-layer superposition coding scheme and use genie-aided converse arguments to get a “within one bit” characterization in the spirit of the Etkin/Tse/Wang approach to interference channels. In the latter interference model they also show that power control can get similar performance.

  • Capacity for Classes of Broadcast Channels with Receiver Side Information (Gerhard Kramer and Shlomo Shamai (Shitz))

    The channel model here is a broadcast channel where each user has as side information the other user’s message. The coding schemes used are nested lattice codes, and they show that they can get all capacity points — furthermore they can generalize their scheme to cost-constrained channels and coding for degraded message sets. At the end of the talk there was some very recent work by a student working with Gerhard (Wei Kang, I believe?) who showed a similar result for the case of general correlated sources with a certain kind of degraded side information at one receiver.

  • Successive Refinement of Vector Sources under Individual Distortion Criteria (Jayanth Nayak, Ertem Tuncel, Deniz Gunduz, and Elza Erkip)

    The problem here is to make a successive refinement code (if you get more of the codeword you can decode to lower distortion) for vector sources where we have a distortion constraint on each of the components of the code. If we look at a two sources (vectors of length 2) we can mark achievable distortion pairs (D1, D2) on the plane and ask “what kind of trajectory can we make with successive refinement codes? It turns out the answer is rather complicated — for Gaussian sources we get three regions and there are rules about what paths we can take.

  • On Cognitive Interference Networks (Amos Lapidoth, Shlomo Shamai (Shitz), and Michele A. Wigger)

    This is a follow-up to the ISIT paper, which focused on characterizing the pre-log of the sum-capacity of a certain interference network that looked like a chain. The “cognitive” aspect of the problem is that the transmitters know the message of their interfering neighbors. They can use some linear encoding to zero-force their own interference and then a number of results pop out — conditions on when the pre-log for K users can be K or K-1, necessary and sufficient conditions on the network for achieving K, and the fact that pre-log can be noninteger, unlike the case where no side information is available.

  • Reliable Communication in Networks with Multi-access Interference (Danail Traskov and Gerhard Kramer)

    Danail presented an interesting scheme for generating correlated messages in networks (with an eye to network coding, it seemed). As a simple example, a source transmitter sends rate-constrained messages to two relays who then communicate to the destination. This is similar to the Schein-Gallager network but without the broadcast component at the beginning. The source can correlate the messages at the relays, and in some cases they can get a capacity result. More importantly, the scheme scales to more general networks of MACs and has a nice “flow” interpretation.


2 thoughts on “ITW 2007 (Tahoe) : Day Two

  1. Actually, just to clarify, our result for ITW was both for source-channel and “communicating bits only” scenarios. In both cases, structured random codes are useful. 🙂

    Thanks for documenting all this!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.