Michelle Effros - US grants

The goal of this project is to develop reasonable complexity, source independent coding algorithms. Source independent algorithms are crucial to the design of robust systems for applications such as image coding and mobile communications. In applications of this type, the statistics of the source and channel in operation are typically unknown a priori, and the performance of the strategy employed is sensitive to those unknown statistics. The approach taken is the two-stage approach developed in the source coding literature. Given a space of possible sources and a particular coding strategy (e.g., VQ, DCT-based transform codes, etc.), for each source in the space there exists an optimal code. Designing a single code is equivalent to quantizing the space of possible codes to 0 bits; the entire space of optimal codes is approximated by a single code that does well on average across the data. The two-stage coding literature demonstrates that in general we should quantize the space of possible codes more finely. Some of the rate should be spent on describing which code, in a family of codes, should be used on the source in operation. Specific projects being completed in this research include the development of a universal DCT code compatible with existing JPEG and MPEG image and video coding standards, a universal KLT code, a universal wavelet packet code, and a universal channel code. The main objectives of the education plan are to develop and maintain an exciting atmosphere of active learning for undergraduate and graduate students. This objective is being accomplished through innovative programs geared at helping students to participate fully in their own education and by developing an atmosphere that encourages the maximum possible exchange between students, faculty, and members of local industry.

Network systems and applications, including both established technologies
like wireless voice networks, the internet, and video services and emerging
technologies like wireless multimedia, distributed computing, and ubiquitous
computing, are undergoing explosive growth. While these systems differ in
many ways, a key bottleneck is common to all of them: The utility of each
of these technologies is limited by the amount of information that can be
sent through the corresponding network. Since bandwidth is scarce, making
the best use possible of the data rates available is critical. Thus use of
efficient data representations, or source codes, is imperative for maximizing
system performance in network technologies.


This research considers new paradigms for source coding in network systems
and compares those paradigms to existing approaches. The analysis involves
theoretical proof of concept, demonstration of practically achieved gains on
real data sets, and development of efficient codes to achieve those gains.
Current work focuses on source coding for broadcast systems. Broadcast
systems play a central role in all of the above network technologies, where
one system node ``broadcasts'' both common information (intended for all
users) and specific information (intended for a subset of the users) to the
other nodes in the network. Existing methods for source coding in broadcast
systems use collections of traditional (single-transmitter, single-receiver)
source codes within the (single-transmitter, multiple-receiver) broadcast
system. Current work aims to demonstrate and quantify the gains achieved by
abandoning this approach in favor of source codes optimized for broadcast
systems.

This workshop is intended to bring together a group of researchers to discuss and recommend future directions in the field of source-channel coding.
Specifically, the goals of the workshop are:
Provide a contextual basis for understanding the array of applications in which source-channel coding can play a central role;
Assess the potential impact of source-channel coding technology in those applications;
Identify and characterize the major research issues associated with the design, development, and deployment of source-channel coding technology;
Develop a conceptual framework for future crosscutting research activities in this inherently interdisciplinary area.

ITR: Information Representation for Cooperation Across Networks

We define cooperation among the nodes of a network to include any activity
where the action of a single individual relies on information from other
individuals in a shared environment. Using this broad definition,
information aggregation in sensor networks, group activities performed by
autonomous robotic devices, internet exploration and modeling, and
establishment of ad hoc networks are all examples of tasks involving
cooperation among the nodes of a network. An essential feature common to
cooperative tasks is the need to share information across a distributed
system. Thus cooperation requires the flow of information. In environments
limited by constraints on power, bandwidth, time, or memory, efficient
information flow requires efficient data representation. We are currently
studying strategies for efficient information representation in network
systems. When we speak of information representation for a network,
we consider the network as a whole, asking questions about where information
resides in the network, where it is needed, and how to most efficiently
represent the information to make it accessible where it is needed.
Current topics of investigation include network data compression, functional
source coding for networks, and joint source-channel coding for networks.

ABSTRACT
0325324
Michelle Effors
California Instit. Of Tech

Network Coding --- From Theory to Practice

The efficient use of network resources is a central objective in making information available in today's society. Despite an enormous effort in understanding the modes in which networks can, do, and should operate, a unified and concise theory of networking has remained elusive. Before this backdrop, this research aims at developing and leveraging a combined view of a number of traditionally separate, network-related issues. In this context, the research team will investigate issues varying from fundamental questions about the structure of networks employing network coding over an array of specific network scenarios, network robustness, network information theoretic aspects to questions involving practical aspects of networks.
This ambitious project is driven by the notion of "Network Coding", a recent discovery that is central to this proposal. Not only is network coding a fresh and sharp tool that has the potential to open up stagnant fundamental areas of research, but due to its cross-cutting nature it naturally suggests a unified treatment of previously segmented areas. In particular, the research addresses the interplay of network coding in the context of network management, network information theory, compression and channel codes in networks and distributed scheduling and routing algorithms. The understanding of intrinsic fundamental performance limits of networks across different tasks, holds the potential to not only create a cornerstone in the theory of networks but also to build new and robust bridges between previously unconnected areas.

This project is developing a new framework for investigating the dynamics of
information in complex, interconnected systems. The key technical thrusts
of the project are: (1) real-time information theory, (2) robust control of
networks, (3) packet-based control theory,and (4) computational complexity
of network systems. Each of these thrusts explores aspects of information
systems that must interact with the real-world in a manner that requires
careful control of the timing of the computation and the evolution of the
information state of the system. While diverse in application, these
thrusts represent a common core of intellectual thrusts that integrate
computer science, control, and communications.

The results of the proposed research are being evaluated on two testbeds
already at Caltech. The first is the Multi-Vehicle Wireless Testbed, which
provides a distributed environment for control of 8-10 vehicles performing
cooperative tasks in a real-time environment. The second is the WAN in Lab,
a wide area network consisting of high speed servers, programmable routers,
electronic crossconnects, and long haul fibers with associated optical
amplifiers, dispersion compensation modules and optical multiplexers.

The project is also developing elements of a curriculum that will provide
training to students in information systems that blends communications,
computation, and control. This includes integration our the research
framework into a recently created course at Caltech on the principles of
feedback and control, CDS 101, as well as development a second course, IST
201, aimed at bringing together faculty and students interested in working
on problems at the boundaries of these traditional disciplines.

----
Communication networks are, increasingly, the backbone upon which the world's financial, educational, and governmental institutions rely. Surprisingly, very little is known about how much information current communication networks can carry. The absence of tools for characterizing the "capacities" of large, complex networks makes it difficult to determine how to improve the capabilities of current communication networks or to design better networks for the future. This research involves the development of new systematic strategies for building computational tools for characterizing the capacities of large networks.

This research involves bounding the capacity of a complex network by first factoring the network into individual components, then replacing those components by simpler models, and finally employing computational tools to bound the capacities of the modeling networks. Researchers create a library of component models by deriving both upper and lower bounding models for each component studied. Unlike prior mechanisms for characterizing the behaviors of individual channels, these upper and lower bounding models capture the full range of behaviors of an individual component. Thus the capacity of any network is bounded from above by the capacity of another network where each component is replaced by its upper bounding model and bounded from below by the capacity of a distinct network where each component is replaced by its lower bounding model. Researchers are developing models for both individual transmission devices like broadcast, multiple access, and interference channels and sub-networks built from component models. Modeling sub-networks allows networks to be analyzed hierarchically, yielding a technique that scales to very large networks.

This project addresses the study of cooperation in distributed networks, first through the study of simple structures that isolate dedicated resources for global or local cooperation and then directly in general networks. The work is organized into three thrusts. The first thrust employs a global facilitator that has access to all messages in the network and can transmit a rate-R description of these messages to all nodes. Bounding the capacity of such a network as a function of R gives a first-order estimate of the minimal cost and maximal benefit of cooperation in a given network. In the second thrust, we move from global to local models of cooperation to understand how much of the cooperative advantage can be achieved using smaller groups of cooperators. The final thrust studies the implementation and approximation of the most successful cooperation strategies from the earlier thrusts for use in wireless, sensor, and wired networks; here the rate employed to enable cooperation shares the same network resources as the capacity it aims to increase.

Example networks demonstrate large potential benefits in communication system performance through the use of strategies that employ cooperation among the communicating devices. Performance improvement is here measured as an increase in the amount of information that can be reliably delivered through a communication network. Increasing rate through cooperation may allow more users to simultaneous communicate or each user to communicate at an increased rate in a given network. This project aims to develop the theoretical foundations of cooperation-based communication strategies and to help guide the design of communication protocols that realize the benefits of cooperation in practice.

Advances in modern society are increasingly intertwined with those of our communication systems. Everything from entertainment to business to transportation to healthcare itself relies on our ability to communicate efficiently and reliably. With progress in all of these domains come increasing communication demands. The key to meeting those demands is an ever increasing and growing understanding of how to build better communication networks and how to operate the ones that we have more effectively. While much is known about small parts of our communication networks, surprisingly little is known about how to operate the network as a whole more efficiently. This project sets out to tackle that monumental and critical goal, by seeking to uncover the implications of network design choices, understand the commonalities and differences among these implications, and expand the theory and techniques needed both to operate these systems efficiently and to understand the limits of their performance.

The network information theory literature considers code design and performance limits for communication systems under a wide variety of system models and constraints. While a careful reading of the literature reveals many common tools and strategies, each new problem engenders its own new theory. This work takes a systematic approach towards uncovering the hidden underlying commonalities that connect the solutions of information theoretic problems. Central to this approach are reduction arguments that derive relationships between the solutions to different information theoretic problems. In such, our framework shifts attention from the traditional focus on solving example networks to a focus on building connections between problem solutions. The work is organized in three thrusts. The first examines network modeling assumptions with the goal of determining how much each assumption impacts the information theoretic solvability of networks, distilling out aspects that have little or no impact on solvability, and simplifying broad classes of communication problems down to their essential representative core. The second thrust moves from individual network characteristics to comparisons between characteristics in order to understand the common, unsolved challenges that lie at the heart of a wide range of network information theoretic questions and use these commonalities to develop a taxonomy of problems and solutions. Finally, as the first two thrusts steer attention towards representative examples and common challenges, existing tools for code design and capacity calculation are enhanced and amplified by applying them to new communication scenarios for which reductive arguments demonstrate a connection.

Many goals motivate scientific interest in human memory. The brain's ability to create, store, and access memories helps enable vision, speech, learning, thought, and identity; understanding memory elucidates both the functions of remembering and the functions that rely on them. Injury and illness can suppress or overstimulate memory function, with extreme cases causing ailments like Alzheimer's disease and dementia on the one hand and PTSD and addiction on the other; a theory explaining how biological mechanisms create memory phenomena may help pinpoint the mechanistic changes responsible for memory failures. This project outlines a path to a fundamentally new theory for how the microscopic behavior of individual neurons generates the macroscopic phenomena of memory performance. The potential outcomes of this project can shed greater light on the understanding of human memory and the processes that influence it.

This project seeks to create models for brain behavior and memory phenomena and applies mathematical tools to investigate whether the brain model can generate those memory phenomena. Brain behavior is structured here as a Markov process derived from models of individual neurons, their connectivity, and stimuli. Markov processes, which capture the assumption that the past affects the future only through its effects on the present, exhibit a characteristic behavior called stochastic convergence, where the Markov process trends toward a predictable steady-state behavior over time. The memory model seeks to capture memory retrieval, formation, and storage as phenomena where the brain state converges to desired outcomes under corresponding stimuli, creates new convergence relationships through neuronal plasticity, and protects old convergence relationships from damage caused by that same plasticity.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.