Subscription Schedule Abstracts
 |
When: Friday, May 26 |
|
Where: Moore 70 |
| Speaker: Yuval Cassuto |
Fridays at 12:00 pm (Noon) in Moore 70
Date |
Speaker |
Title |
| Oct 14 | Ali Vakili | The effect of SNR estimation error on the sum-rate of broadcast channels |
| Oct 28 | Sidharth Jaggi | Network Coding: Mixin' it up |
| Nov 11 | Edwin Soedarmadji | The Gas Station Problem |
| Nov 18 | Xiaojie Gao | Real-Time Coding for Multiple Access Channels |
| Dec 2 | Marco Andreetto | Automatic scene classification using the Latent Dirichlet Allocation model |
Fridays at 12:00 pm (Noon) in Moore 70
Date |
Speaker |
Title |
| Jan 20 | Farzad Parvaresh | On the algebraic list decoding of error-correcting codes |
| Feb 3 | Chaitanya Kumar Rao | The diversity order of wireless systems |
| Feb 10 | Edwin Soedarmadji | A Dynamic Graph Algorithm for the Highly Dynamic Network Problem |
| Feb 24 | Mihailo Stojnic | Speeding up the Sphere Decoder with $SDP$ and $H^{\infty}$ inspired lower bounds |
| Mar 10 | Byung-Jun Yoon | Profile context-sensitive HMMs for probabilistic modeling of sequences with complex correlations |
Fridays at 12:00 pm (Noon) in Moore 70
Date |
Speaker |
Title |
| Apr 21 | Chun-Yang Scott Chen | A Novel Beamformer Robust to Steering Vector Mismatch |
| May 5 | Borching Su | A Generalized Algorithm for Blind Channel Identification with Linear Redundant Precoders |
| May 26 | Yuval Cassuto | Cyclic Array-Codes |
|
Date: Oct 14, 2005 |
|
Speaker: Ali Vakili |
|
Title: "The effect of SNR estimation error on the sum-rate of broadcast channels," Ali Vakili, Masoud Sharif, Babak Hassibi. |
|
Abstract: |
In a broadcast channel in which one transmitter serves $n$ receivers, the capacity region highly depends on the amount of channel state information at the transmitter. Assuming that the transmitter knows the SNR of all the receivers, opportunistic strategy which transmits to the user with the best channel condition at each channel use, maximizes the throughput (sum-rate) of the system. Evaluating the SNR is basically an estimation problem which cannot be done without error. In this paper, we analyze the effect of this noisy estimation on the throughput. We consider a scheduling scheme similar to the opportunistic transmission with the only difference that the transmitter backs off on the transmit rate based on the variance of the estimation error. We obtain the optimum amount of back off and compute the throughput for our scheduling as a function of the estimation noise. Clearly, the estimation can be improved by using a longer training phase; however, longer training would deteriorate the throughput. In the final part of the paper, we obtain the optimum training that maximizes the throughput of the system. Simulation results compare the throughput of the system in the presence of different amounts of estimation error.
|
Date: Oct 28, 2005 |
| Speaker: Sidharth Jaggi |
|
Title: "Network Coding: Mixin' it up," Sidharth Jaggi |
|
Abstract: |
The information theoretic aspects of large networks with many terminals presents several interesting and non-intuitive phenomena. One such phenomenon was first explored in a detailed manner in excellent work by Ahlswede et al., who proved that for a large class of network problems, allowing internal nodes to perform non-trivial arithmetic operations on information on incoming links to generate information on outgoing links could substantially improve throughput, compared to the more traditional scenario where such nodes were restricted to only copying and forwarding incoming messages on outgoing links. Further work by various authors showed how to design codes (called network codes) to transmit under this new paradigm, and also demonstrated exciting new phenomena for such coding techniques such as robustness against network failures, distributed design, and increased security.
We consider the low-complexity design and analysis of network codes, with a focus on codes for multicasting information. We examine both centralized and decentralized design of such codes, and also randomized versus deterministic design algorithms. We compare different notions of linearity and show the interplay between these notions in the design of linear network codes. We determine bounds on the complexity of network codes. We also consider the problem of error-correction and secrecy for network codes when a malicious adversary controls some subset of the network resources.
|
Date: Nov 11, 2005 |
| Speaker: Edwin Soedarmadji |
|
Title: "The Gas Station Problem," Edwin Soedarmadji and Robert J. McEliece |
|
Abstract: |
We introduce the ``gas station problem'' (GSP), the problem of finding the shortest travel path for a vehicle with a limited fuel capacity operating in a transportation network with refueling nodes. The GSP is specified by the vehicle's maximum onboard fuel capacity and its starting fuel level, as well as the network's refueling nodes and its edge weights expressed in fuel consumption units. We develop an algorithm that provides an answer in $O(V^3)$ time complexity.
|
Date: Nov 18, 2005 |
| Speaker: Xiaojie Gao |
|
Title: "Real-Time Coding for Multiple Access Channels," Xiaojie Gao |
|
Abstract: |
We consider a multiple access channel shared by two sources. The channel is noiseless but there is interference between the transmissions of the sources. Because of applications to distributed control we are interested in the real-time version of this problem, in which the receiver must act immediately upon received information.
Block coding is therefore not possible, and error probability cannot generally be made to tend to 0 in the interior of the multiple access capacity region.
We study code design for a simple class of XOR channels. We provide several computationally efficient design methods. Under an assumption on the form of the correlation among the sources, one of these algorithms provides codes whose success probability is within $2/3$ of optimal. In the absence of assumptions on the correlation, optimal code design is NP-hard.
|
Date: Dec 2, 2005 |
| Speaker: Marco Andreetto |
| Title: Automatic scene classification using the Latent Dirichlet Allocation model |
|
Abstract: |
In this talk I will introduce the Latent Dirichlet Allocation
(LDA),a probabilistic model for the description of set of discrete observation. The LDA model is a hierarchical Bayesian model which describes each set of observations as a mixture of a "topics" or "aspects". After illustrating the model characteristics and possible techniques for inference and learning on this model, I will show the LDA can be used to solve a visual recognition problem: the automatic classification of scenes.
|
Date: Jan 20, 2006 |
| Speaker: Farzad Parvaresh |
| Title: On the algebraic list decoding of error-correcting codes |
|
Abstract: |
There has been a lot of progress in the area of algebraic list decoding. The first real breakthrough on the list-decoding problem was achieved by Sudan and Guruwami-Sudan in the late 1990s. The groundbreaking work of Guruwami-Sudan shows that using Reed-Solomon (and later algebraic) codes, it is possible to list-decode in polynomial time a fraction of $1-\epsilon$ errors with a code of rate $\epsilon2$. Recently, Parvaresh and Vardy come up with a new class of codes that can efficiently list decoded up to $1 - \epsilon$ fraction of errors with rate $\Omega(\epsilon / \log(1 / \epsilon))$. The new codes are based on two key ideas. The first is the transition form bivariate polynomial interpolation, pioneered by Sudan and Guruswami-Sudan, to multivariate interpolation decoding. The second idea is to part ways with Reed-Solomon codes. Later, Guruswami and Rudra show that a specific class of PV codes can be compressed in a very clever way into a "Folded" Reed-Solomon code. This compression increases the transmission rate and so improves the decoding radius. However, the decoder can decompress the received word and use the PV algorithm for recovery of the transmitted codeword. Using folded RS codes we can correct up to $1 - \epsilon$ fraction of errors with rate $\ep^{(M-1) / M}$. This bound can get close to capacity of adversarial channel when the alphabet size is large. I will briefly address these algorithms and I will talk about the open problems that still remains in this area.
|
Date: Feb 3, 2006 |
| Speaker: Chaitanya Kumar Rao |
| Title: The diversity order of wireless systems |
|
Abstract: |
Wireless systems are subject to multipath fading, a randomness in the channel that can severely limit the rates of reliable communication. One performance measure for such systems is the diversity order - if error probability decays as 1/(SNR^d) for high SNR, it is said to have diversity order d. This can be increased by exploiting fading, through the use of multiple antennas or relay nodes.
In this talk I will describe some setups whose diversity order can be found, as a function of rate. These include multiple antenna systems, simple relay networks, and recent work on the interference channel with cooperating nodes. In the latter case the diversity can be as high as three, but at the expense of a reduced data rate.
|
Date: Feb 10, 2006 |
| Speaker: Edwin Soedarmadji |
| Title: "A Dynamic Graph Algorithm for the Highly Dynamic Network Problem," Edwin Soedarmadji and Robert J. McEliece |
|
Abstract: |
A recent flooding algorithm by O'Dell and Wattenhofer guaranteed correctness for networks with dynamic edges and fixed nodes. The algorithm provided a partial answer to the highly dynamic network (HDN) problem, defined as the problem of devising a reliable message-passing algorithm over a HDN, a network mobility model where edges and nodes can enter and leave the network almost arbitrarily. In this paper, we relax the flooding algorithms assumptions by removing the requirement that the network stays connected at all time, and extend the algorithm to solve the HDN problem where dynamic nodes are also involved.
The extended algorithm is reliable: it guarantees message- passing to all the destination nodes and terminates within a time bounded by a polynomial function of the maximum message transit time between adjacent nodes, and the maximum number of nodes in the network.
|
Date: Feb 24, 2006 |
| Speaker: Mihailo Stojnic |
| Title: Speeding up the Sphere Decoder with $SDP$ and $H^{\infty}$ inspired lower bounds |
|
Abstract: It is well known that
maximum-likelihood (ML) decoding in many digital communication schemes reduces
to solving an integer least-squares problem, which is NP hard in the
worst-case. On the other hand, it has recently been shown that, over a wide
range of dimensions $N$ and signal-to-noise ratios (SNRs), the sphere decoding
algorithm can be used to find the exact ML solution with an expected
complexity that is often no more than $N^3$. However, the computational
complexity of sphere decoding becomes prohibitive if the SNR is too low and/or
if the dimension of the problem is too large. In this paper, we target these
two regimes and attempt to find faster algorithms by pruning the search tree
beyond what is done in the standard sphere decoding algorithm. The search tree
is pruned by computing lower bounds on the optimal solution as the algorithm
proceeds to descend down the search tree. We observe a trade-off between the
computational complexity required to compute a lower bound and the size of the
pruned tree: the more effort we spend in computing a tight lower bound, the
more branches that can be eliminated in the tree. Using ideas from SDP-duality
theory and $H^\infty$ estimation theory, we propose general frameworks for
computing lower bounds on integer least-squares problems. We then show how in
several special cases these bounds can be efficiently incorporated in the
sphere decoding algorithm, resulting in significant improvement of the
expected complexity of solving the ML decoding problem, while maintaining the
exact ML-performance. |
|
Date: March 10, 2006 |
| Speaker: Byung-Jun Yoon |
| Title: Profile context-sensitive HMMs for probabilistic modeling of sequences with complex correlations |
|
Abstract: The profile
hidden Markov model is a specific type of HMM that is well suited for
describing the common features of a set of related sequences. It has been
extensively used in computational biology, where it is still one of the most
popular tools. In this talk, we introduce a new model called the profile
context-sensitive HMM. Unlike traditional profile-HMMs, the proposed model is
capable of describing complex long-range correlations between distant symbols
in a consensus sequence. We also describe a general algorithm that can be used
for finding the optimal state sequence of an observed symbol sequence based on
the given profile-csHMM. The proposed algorithm can be viewed as a
generalization of the Viterbi algorithm and the Cocke-Younger-Kasami (CYK)
algorithm |
|
Date: April 21, 2006 |
| Speaker: Chun-Yang Scott Chen |
| Title: A Novel Beamformer Robust to Steering Vector Mismatch |
|
Abstract: One of the main problems in beamforming applications is the mismatch of the assumed and actual directions of the steering vector. For example the performance of the Capon beamformer is known to be very sensitive to steering vector mismatch. When the mismatch happens, the linear constraint fails to ensure a constant gain for the signal. The signal is therefore interpreted as an interference and is attenuated. Recently, some approaches based on an uncertainty set of steering vectors have been proposed. Instead of imposing a linear constraint, these approaches minimize the output variances subject to the constraint that the magnitude responses of a set of steering vectors exceed unity. However, these methods include too many unnecessary constraints to minimize the output variances properly. In this paper, a new robust beamformer is proposed. Instead of confining the magnitude responses of all possible steering vectors, our method constrains the magnitude responses of only two steering vectors. Then a diagonal loading method is used to force the magnitude responses at a range of the arrival angles to exceed unity. The diagonal loading factor can be computed systematically by a proposed algorithm. Numerical examples show that this method has a significantly better SINR performance compared to previously published methods and a complexity comparable to the standard Capon beamformer. |
|
Date: May 5, 2006 |
| Speaker: Borching Su |
| Title: A Generalized Algorithm for Blind Channel Identification with Linear Redundant Precoders |
|
Abstract: It is well-known that redundant filter bank
precoders can be used for blind identification as well as equalization of FIR
channels. Several algorithms have been proposed in the literature exploiting
trailing zeros in the transmitter. In this talk we propose a generalized
algorithm of which the previous algorithms are special cases. By carefully
choosing system parameters, we can jointly optimize the system performance and
computational complexity. Simulation results show that the proposed algorithm
outperforms the previous ones when the parameters are optimally chosen,
especially in time-varying channel environments. |
|
Date: May 26, 2006 |
| Speaker: Yuval Cassuto |
| Title: Cyclic Array-Codes |
|
Abstract: Array codes are error correcting codes that
use simple operations over the binary field to obtain good error correction
properties over large extension fields. As a result, they are very useful for
dynamic data storage applications. In such applications, failures occur in the
device level (thus the large field), but the need for fast encoding, decoding
and updates allows only for simple binary operations.
|
This page is maintained by Mostafa El-Khamy