A source coding scheme using sparse graphs: Modern Coding Theory Course Exam 2008

This is the report that submitted towards the final examination evaluation of the doctoral course \textit{Modern Coding theory} by Ruediger Urbanke at EPFL during Spring 2008. The problem studied can be roughly stated as source coding or compression using sparse graphs. We discuss a simple source coding problem and analyze its performance using an analytical tool formulated by \textit{Wormald}, usually employed to describe the expected behaviour of a suitably conditioned stochastic process on graph. A simulation investigation of the chosen scheme is also presented to verify the theoretical analysis.

An optimal prediction problem in financial modelling

Violetta Bernyk

The subject of the present thesis is an optimal prediction problem concerning the ultimate maximum of a stable Lévy process over a finite interval of time. Such "optimal prediction" problems are of both theoretical and practical interest, in particular they have applications in finance. For instance, suppose that an investor has a long position in one financial asset, whose price is modelled by some stochastic process. The investor's objective is to determine a "best moment" at which to close out the position and to sell the asset at the highest possible price. This optimal decision must be based on continuous observations of the asset price performance and only on the information accumulated to date. Hence, the investor should use a prediction (forecasting) of the future evolution of the price of the financial security. We examine this problem in the case where the asset price is modelled by a Lévy process. Indeed, during the last several years, the application of Lévy processes in the modelling financial asset returns has become one of the active research directions in quantitative finance. Thus, this thesis contains suitable new results concerning Lévy processes. We derive the law of the supremum process associated with a strictly stable Lévy process with no negative jumps which is not a subordinator. We note that the latter problem dates back to 1973. In particular, we show that the probability density function of the supremum process can be expressed using an explicit power series representation or via an integral representation. We also derive the infinitesimal generator of the reflected process associated with a general strictly stable Lévy process. Throughout this thesis, we apply the theory of optimal stopping, the methods of fractional differential calculus, and some results from fluctuation theory. Implementing these theories in the context of Lévy processes requires the development of specific analytical results. In the case where the asset price is modelled by a spectrally positive stable Lévy process, we describe the optimal strategy under certain conditions on the model parameters. The optimal strategy is of the following form: the investor must stop the observation of the price process and sell the asset as soon as the associated reflected process crosses for the first time a particular stopping boundary. We also provide numerical estimates and simulation examples of the results obtained by using this strategy.

EPFL2007

Polar codes for channel and source coding

Satish Babu Korada

The two central topics of information theory are the compression and the transmission of data. Shannon, in his seminal work, formalized both these problems and determined their fundamental limits. Since then the main goal of coding theory has been to find practical schemes that approach these limits. Polar codes, recently invented by Arikan, are the first "practical" codes that are known to achieve the capacity for a large class of channels. Their code construction is based on a phenomenon called "channel polarization". The encoding as well as the decoding operation of polar codes can be implemented with O(N log N) complexity, where N is the blocklength of the code. We show that polar codes are suitable not only for channel coding but also achieve optimal performance for several other important problems in information theory. The first problem we consider is lossy source compression. We construct polar codes that asymptotically approach Shannon's rate-distortion bound for a large class of sources. We achieve this performance by designing polar codes according to the "test channel", which naturally appears in Shannon's formulation of the rate-distortion function. The encoding operation combines the successive cancellation algorithm of Arikan with a crucial new ingredient called "randomized rounding". As for channel coding, both the encoding as well as the decoding operation can be implemented with O(N log N) complexity. This is the first known "practical" scheme that approaches the optimal rate-distortion trade-off. We also construct polar codes that achieve the optimal performance for the Wyner-Ziv and the Gelfand-Pinsker problems. Both these problems can be tackled using "nested" codes and polar codes are naturally suited for this purpose. We further show that polar codes achieve the capacity of asymmetric channels, multi-terminal scenarios like multiple access channels, and degraded broadcast channels. For each of these problems, our constructions are the first known "practical" schemes that approach the optimal performance. The original polar codes of Arikan achieve a block error probability decaying exponentially in the square root of the block length. For source coding, the gap between the achieved distortion and the limiting distortion also vanishes exponentially in the square root of the blocklength. We explore other polar-like code constructions with better rates of decay. With this generalization, we show that close to exponential decays can be obtained for both channel and source coding. The new constructions mimic the recursive construction of Arikan and, hence, they inherit the same encoding and decoding complexity. We also propose algorithms based on message-passing to improve the finite length performance of polar codes. In the final two chapters of this thesis we address two important problems in graphical models related to communications. The first problem is in the area of low-density parity-check codes (LDPC). For practical lengths, LDPC codes using message-passing decoding are still the codes to beat. The current analysis, using density evolution, evaluates the performance of these algorithms on a tree. The tree assumption corresponds to using an infinite length code. But in practice, the codes are of finite length. We analyze the message-passing algorithms for this scenario. The absence of tree assumption introduces correlations between various messages. We show that despite this correlation, the prediction of the tree analysis is accurate. The second problem we consider is related to code division multiple access (CDMA) communication using random spreading. The current analysis mainly focuses on the information theoretic limits, i.e., using Gaussian input distribution. However in practice we use modulation schemes like binary phase-shift keying (BPSK), which is far from being Gaussian. The effects of the modulation scheme cannot be analyzed using traditional tools which are based on spectrum of large random matrices. We follow a new approach using tools developed for random spin systems in statistical mechanics. We prove a tight upper bound on the capacity of the system when the user input is BPSK. We also show that the capacity depends only on the power of the spreading sequences and is independent of their exact distribution.

EPFL2009

Stochastic Control and Free Boundary Problems for Sailboat Trajectory Optimization

Laura Vinckenbosch

The topic of this thesis is the study of several stochastic control problems motivated by sailing races. The goal is to minimize the travel time between two locations, by selecting the fastest route in face of randomly changing weather conditions, such as wind direction. When a sailboat is travelling upwind, the key is to decide when to tack. Since this maneuver slows down the yacht, it is natural to model this time lost by a "tacking penalty" which places the problem in the context of optimal stochastic control problems with switching costs. An objective of this work is to propose and to study mathematical models that capture some of the features of a sailing race, but which remain amenable to an explicit rigorous solution that can be proved to be optimal. We consider three different models in which the wind direction is described by a stochastic process. In the first model, we consider a wind that changes randomly only once. In the second model, the wind oscillates between two possible directions according to a continuous-time Markov chain. We exhibit a free boundary problem for the value function involving hyperbolic partial differential equations of Klein-Gordon type. The last model considers the wind direction as a Brownian motion. We prove the existence of a finite value function and exhibit a free boundary problem involving parabolic partial differential equations with non-constant coefficients. In these three models, the optimal solution consists of a partition of the state space into a region where it is optimal to tack immediately and a region where it is optimal to continue on the current tack. The boundaries between these regions are given by one or more "switching curves" and in the cases where we have been able to exhibit them, the optimality of the solution is established by a verification theorem based on the martingale method. We also solve two other control problems in which a player tries to minimize or maximize the exit time from an interval of a Brownian particle by controlling its drift and subject to a switching penalty. In each problem, the value function is written as the solution of a second order ordinary differential equations problem whose unknown boundaries are found by applying the principle of smooth fit. For both problems, we exhibit a candidate strategy as a function of the switching cost and we prove its optimality as well as its generic uniqueness.

EPFL2012