ENG SC500 A1 Spring 2007
(Statistical Theory of Communication)
Project presentations:
Presentation time: 20 mins (hard limit) + 5 mins for questions and to change to the next presentation.
Speakers, titles,
and abstracts
Zeyu Wu
Performance Analysis of LDPC Codes
Abstract
LDPC codes, which were originally developed by Robert Gallager in his
doctoral dissertation, have attracted more and more attention due to the
rapid development of high-speed processors and new analytic combinatorial
tools. During the last twenty years many researchers have been working on
the different topics and challenges of this area. Theoretical researches
on
capacity achievement, density of parity-check matrices, performance
comparisons with other techniques and so on have been discussed. Also
different approaches of code construction, decoding algorithms and
implementations have been provided. In this project I will briefly go
through the error correction coding, linear block code and LDPC code,
followed by the theoretical analysis about its capacity-approaching
property. Furthermore, we will also discuss the decoding algorithms.
Specifically we will cover the near-optimal performance and tradeoff
between
complexities of the well-known message-passing decoding algorithm. Finally,
we will bring out some prospective applications of LDPC code.
[Talk viewgraphs]
Ajay Bangla
Distributed Compression in Sensor Networks
Abstract
A major challenge in sensor networks is the integrated design of local
signal processing operations and strategies for intersensor communication
and networking so as to strike a desirable tradeoff among energy efficiency,
simplicity, and overall system performance. Spatially proximal sensor
measurements are likely to be correlated and distributed compression can
help in reducing the communication cost while achieving the desired level of
inference performance. More than 30 years ago, Slepian and Wolf laid the
theoretical foundations of lossless distributed source coding. Wyner and Ziv
partially extended the results to lossy coding. Driven by applications like
sensor networks, distributed source coding has become a very active area of
research. In this project we will explore the basic principles of Slepian-
Wolf and Wyner-Ziv coding theory.
[Talk viewgraphs]
Gardar Hauksson
Network-Coding for Multicasting in Mobile Ad-hoc Networks
Abstract
The advent of network coding poses significant changes of how modern
communications networks are viewed. The classical approach of network theory
is to look at each node of a communications graph as a simple switch which
only routes or replicates data to other nodes. Network coding exploits the
fact that each node in such a graph has computational power and can in fact
employ coding to save bandwidth.
In particular, this can be very beneficial to wireless networks, where the
energy cost of communications is high relative to the cost of computation.
Therefore minimizing the energy-per-bit in wireless transmissions is vital
and trading it off for increased computational complexity of the nodes is
feasible.
In this project we will explore how network coding is beneficial to
multicasting in Mobile Ad Hoc Networks. This will be done by surveying both
the fundamental analysis of network coding and the more focused work on
wireless multicast applications.
[Talk viewgraphs]
Stephen Chao
Network-Coding in P2P Networks
Abstract
Network coding has generated much interested since its inception, showing
potential for gains in throughput and robustness within computer networks.
One particular application for which network coding seems a good fit is
content distribution in large sized networks, specifically P2P networks.
However, there has been much disagreement in the literature as to whether
network coding actually offers benefits over existing content distribution
schemes, such as those based on push/pull piece selection. In this project,
I analyze some of the hidden costs (assumptions) associated with network
coding, as well as provide simulations to compare the performance of two
content distribution schemes, one of which is based on network coding and
the other on push/pull.
[Talk viewgraphs]
Ankur Sakhuja
The Expectation-Maximization Algorithm
Abstract
A simplified exposition is presented for the Expectation-Maximization
algorithm, which is a powerful statistical technique for obtaining maximum
likelihood estimates of parameters of probability distributions of observed
data sets having missing information. The observed data are represented by
the n x 1 random vector X which represents an IID sample sequence. The
random vector Y represents the missing information – this may arise either
as actually missing values in the data sequence, or as additional
information to supplement the density associated with X. An example of this
latter case is when each data sample has the distribution of a linear
mixture of unrelated densities wherein the corresponding Y -sample gives
information about which component density "generated" the X -value.
An essential assumption of the algorithm is the existence of densities or
distributions of the missing value random sequence Y. Obviously, since Y
represents the missing information in the context of a sequence of
observations, it will exhibit a joint distribution with the observed
sequence X as p(x, y). The model parameters of the joint density of X and Y
– the quantity that the algorithm aims to optimize - are represented by the
n x 1 random vector Ө. For example, if Xi has a multivariate Gaussian
distribution, then Өi will encapsulate the mean vector μi and covariance
matrix Σi. The aim of the algorithm then is to determine the parameter set Ө
that maximizes the value of a defined "expected likelihood" function of the
complete data sequence. For the "maximum likelihood" case, estimation theory
precisely defines the objective function as L = p(X, Y/ Ө). It is clear that
since Y, being the missing information, is a random variable, L will be a
function of the random variable Y, and so the expectation of L will be
computed with respect to Y. Further, as explained earlier, since the density
of Y is available as conditioned on X and Ө, it will result in a conditional
expectation of L.
To accomplish its objective, the algorithm executes a sequence of
iterations, each comprising an ‘E’ and an ‘M’ step. Given a current estimate
of Ө (say өi-1), the E step computes the conditional expectation of L as a
function of Ө (this instance of Ө being the conditioning random variable of
L). The M step then maximizes this expectation over all possible values of
Ө, thereby obtaining a better estimate of Ө (say өi). The algorithm executes
the next iteration using the new estimate as the current one and the process
continues. Finally, it can be shown that iteration process converges in
finite time to the global optimum - which is the output of the algorithm.
The analytical formulations for the optimized values of the parameter set Ө
will be presented for two specializations of the algorithm: where the
observed data is characterized by the (1) Gaussian mixture density model and
(2) Hidden Markov Model.
[Talk viewgraphs]
Gudrun Stefansdottir
Universal Portfolio Selection: Application of Information Theory in Finance
Abstract
The relationship between gambling and information theory was first noted
over fifty years ago and has subsequently developed into a theory of
investment. In this project we focus on exploring these connections and
introduce relevant concepts, such as the growth rate of wealth, log-optimal
portfolios and financial value of side information. It turns out that there
exists a strong duality between the growth rate of wealth in the stock
market and the entropy rate of the market. In particular, we will look at
universal portfolio selection and compare it to the investment strategy of
maintaining a constant rebalanced portfolio. The mathematics of growth-rate
optimal investments are parallel to the mathematics of optimal data
compression. Universal investment algorithms are thus a counterpart of
universal data compression algorithms. Simulations are performed using an
efficient implementation of the universal portfolio algorithm to show its
performance on real stock market data.
[Talk viewgraphs]
Yue Yin
VaR and CVaR models in Log-Optimal Portfolio
Abstract
For an investment on stock market, it is significant to seek an optimal
balance between two objectives: maximizing the expected return and
minimizing investment risk. In the project, the classic mean-variance model
and log-optimal portfolio are introduced at first. VaR(Value at Risk) and
CVaR(Conditional Value at Risk) are good measurements of risk in the
finance area. On the foundation of the definitions of VaR, the log-optimal
portfolio models with the risk control of VaR is proposed. Two models of
risk control, mean-variance and VaR are compared and the conclusion is that
VaR model is more applicable in the portfolio theory. CVaR is described by
definition and some properties.
[Talk viewgraphs]
Mike McHugh
Classification Using Compression-Based Approximate Information-Theoretic Measures
Abstract
The challenge of detection is commonly solved by means of minimum distance
classifiers. These deterministic decision rules are usually generated from
probabilistic models of the data itself or of the processes by which the
data is created. In many cases, the probabilistic models are unknown and
approximate methods must be used. In this project, I investigate the use of
approximate mutual information as a distance metric for classification. The
approximation is based on the use of universal compressors to estimate the
entropy of a source. This method of classification is applied to a speaker
recognition task with successful results.
[Talk viewgraphs]
Kevin Burek
Measurement of Information-Distance in Real-World Sources
Abstract
[Yet to be received]
[Talk viewgraphs]
Sonal Ambwani
An Information-Theoretic Approach to Image Segmentation using Curve Evolution
Abstract
In this project we study an image segmentation algorithm that is motivated
by the maximization of the mutual information between the region labels and
the corresponding pixel intensities. It is based on the work by Junmo Kim et
al. Unlike some other popular techniques for segmentation, this method is
non-parametric and thus applicable to most classes of images. Also, no prior
training data is required for the success of the algorithm. This method
involves the minimization of an energy cost functional cast in a regularized
framework. It is driven by a mutual information term and a term that
penalizes the length of the curve. This optimization problem is solved by
calculating the associated gradient flows and applying curve evolution. We
use a variational formulation of the level-set method to implement the
evolution. Simulations are carried out in MATLAB and the experimental
results confirm the robustness of the scheme for both synthetic and real
images.
[Talk viewgraphs]