Hua Li

Ph.D. PreliminaryApr 12, 2007, 12:00-2:00pm

ECE Conference room

Information Theoretic Problems in Decision Making and Networks

Abstract: This report covers three related topics. The first two, one on tracking and one on searching, represent our previous work, while the third, on network information theory, represents ongoing and future work.

<br>

For the first topic, we propose an information theoretic formulation for the problem of target tracking via sensor querying. Our goal is to study the fundamental limits of trackability. The target motion is modeled by a finite state-space Markov chain. We show that for a target to be trackable the minimum query quota required is no less than the entropy rate H of the Markov chain, but no more than the ceiling of H+1. Subsequently, we consider the adaptive case where the target motion law, namely the probability transition function of the Markov chain, is unknown to the tracker a priori. In this case, the tracker is expected to learn the target motion law and track the target simultaneously. We show that for a target to be trackable the minimum query quota required is no more than the ceiling of H+2.

<br>

For the second topic, we study a class of search problems. The general setup models the ubiquitous situation where a searcher aims to find an immobile target with minimum expected latency and the location of the target is a discrete random variable distributed over a set of possible locations. Both bounded and unbounded search problems are considered. We first consider the Bounded Discrete Linear Search Problem (BDLSP)---the distribution of the target location has a finite support on the integer line---and show that the BDLSP is quadratic-time solvable by formulating it as a Markov Decision Problem (MDP). However, the graph search problem (GSP)---the target is located on the vertices of a graph---is shown to be NP-complete. The errornous BDLSP (EBDLSP)---the searcher may miss the target with a probability when the target location is visited---is formulated as a Partially Observable Markov Decision Problem (POMDP) and connected to the well known ``Bayesian Search Theory.'' In the second part, we consider the Unbounded Discrete Linear Search Problem (UDLSP)---the distribution of the target location has an infinite support on the integer line. Theoretically, we show that an optimal search strategy exists if and only if the double-side mean of the distribution is finite. Algorithmically, we propose a procedure effectively approximating the optimal values of UBDLSPs. To investigate the convergence rate of the procedure, we study the growth rate of the turning points of optimal strategies. We show that for heavy-tailed target location distributions the growth rate is super-linear, and that for thin-tailed target location distributions the growth rate is linear.

<br>

For the third topic, we focus on characterizing the range of the entropy function, essential to multi-terminal information theory. We have obtained some preliminary results. We disprove certain potentially valid non-Shannon-type inequalities with a computer-aided search for counterexamples and show that none of the three extra conditional mutual information terms in the Zhang-Yeung inequality can be dropped for it to remain valid. A general condition, subsuming all the previously known conditions, is obtained for the Ingleton inequality---we show that quasi-Hamilton groups, including Hamiltonian groups as a subclass, satisfy the Ingleton inequality. To our best knowledge, this is the first time that certain classes of non-abelian groups are found to satisfy the Ingleton inequality. Recently, we have uncovered an obscure note written by Shannon, in which the notions of information elements and information lattices were proposed to build a general theory for multi-terminal network communication. We formalize these two notions and establish an isomorphism between information lattices and certain subgroup lattices.

<br>

We propose the following two topics for the remainder of this research.

<br>

The first is to establish a quantitative parallelism between subgroup lattices and information lattices. This line of work will extend an approximation result by Chan and Yeung from joint information elements to both joint and common information elements.

<br>

The second topic is to investigate one special network coding problem---to characterize the capacity region of the one-source--three-sink network under certain information flow demands. This network coding capacity problem has remained unresolved for some time. We believe that our insights developed through studying information lattices will help make progress on this problem.

<br>

For the first topic, we propose an information theoretic formulation for the problem of target tracking via sensor querying. Our goal is to study the fundamental limits of trackability. The target motion is modeled by a finite state-space Markov chain. We show that for a target to be trackable the minimum query quota required is no less than the entropy rate H of the Markov chain, but no more than the ceiling of H+1. Subsequently, we consider the adaptive case where the target motion law, namely the probability transition function of the Markov chain, is unknown to the tracker a priori. In this case, the tracker is expected to learn the target motion law and track the target simultaneously. We show that for a target to be trackable the minimum query quota required is no more than the ceiling of H+2.

<br>

For the second topic, we study a class of search problems. The general setup models the ubiquitous situation where a searcher aims to find an immobile target with minimum expected latency and the location of the target is a discrete random variable distributed over a set of possible locations. Both bounded and unbounded search problems are considered. We first consider the Bounded Discrete Linear Search Problem (BDLSP)---the distribution of the target location has a finite support on the integer line---and show that the BDLSP is quadratic-time solvable by formulating it as a Markov Decision Problem (MDP). However, the graph search problem (GSP)---the target is located on the vertices of a graph---is shown to be NP-complete. The errornous BDLSP (EBDLSP)---the searcher may miss the target with a probability when the target location is visited---is formulated as a Partially Observable Markov Decision Problem (POMDP) and connected to the well known ``Bayesian Search Theory.'' In the second part, we consider the Unbounded Discrete Linear Search Problem (UDLSP)---the distribution of the target location has an infinite support on the integer line. Theoretically, we show that an optimal search strategy exists if and only if the double-side mean of the distribution is finite. Algorithmically, we propose a procedure effectively approximating the optimal values of UBDLSPs. To investigate the convergence rate of the procedure, we study the growth rate of the turning points of optimal strategies. We show that for heavy-tailed target location distributions the growth rate is super-linear, and that for thin-tailed target location distributions the growth rate is linear.

<br>

For the third topic, we focus on characterizing the range of the entropy function, essential to multi-terminal information theory. We have obtained some preliminary results. We disprove certain potentially valid non-Shannon-type inequalities with a computer-aided search for counterexamples and show that none of the three extra conditional mutual information terms in the Zhang-Yeung inequality can be dropped for it to remain valid. A general condition, subsuming all the previously known conditions, is obtained for the Ingleton inequality---we show that quasi-Hamilton groups, including Hamiltonian groups as a subclass, satisfy the Ingleton inequality. To our best knowledge, this is the first time that certain classes of non-abelian groups are found to satisfy the Ingleton inequality. Recently, we have uncovered an obscure note written by Shannon, in which the notions of information elements and information lattices were proposed to build a general theory for multi-terminal network communication. We formalize these two notions and establish an isomorphism between information lattices and certain subgroup lattices.

<br>

We propose the following two topics for the remainder of this research.

<br>

The first is to establish a quantitative parallelism between subgroup lattices and information lattices. This line of work will extend an approximation result by Chan and Yeung from joint information elements to both joint and common information elements.

<br>

The second topic is to investigate one special network coding problem---to characterize the capacity region of the one-source--three-sink network under certain information flow demands. This network coding capacity problem has remained unresolved for some time. We believe that our insights developed through studying information lattices will help make progress on this problem.

Adviser: Edwin K. P. Chong

Co-Adviser:

Non-ECE Member: Donald Estep

Member 3: Louis L. Scharf

Addional Members:

Co-Adviser:

Non-ECE Member: Donald Estep

Member 3: Louis L. Scharf

Addional Members:

Publications:

Program of Study: