CENTER FOR THE MATHEMATICS OF INFORMATION: Information Theory Revisited: Mathematicians and Friends Tackle the Whole Enchilada
A Conversation with Emmanuel Candes, Michelle Effros, and Pietro Perona
Winter 2003

PDF | Table of Contents | Go to Bottom of this Page

From left to right: Emmanuel Candes, Michelle Effros, and Pietro Perona.

EFFROS: There is a lot of excitement in research at the boundaries between traditional areas. The thrusts of ISTI reflect that excitement. One way to cross traditional boundaries is to focus on the applications of information science. Another way is to work on the topics that different information science applications share—which will be our approach. The CMI is focused on understanding the essential nature of information itself, the common properties shared by information in all of its physical forms and applications. We hope to learn how to collect, quantify, communicate, and manipulate information efficiently. In studying the mathematics of information, we will bring together mathematical tools from communications, statistics, signal processing, and computer science with those developed across a wide variety of applications and build a shared foundation for studying information science.

Over the past 50 years, practical problems in communications, controls, and electronics have benefited enormously from breakthroughs in mathematics. The job in the information sciences is by no means done. Roughly, communications looks at bandwidth, controls looks at feedback, and computer science looks at computation. What is needed for today's more complex systems, whether natural or designed by people, is some way of capturing these things together and understanding how they interact.

Representation choice is one example of an area to investigate. Imagine that you have raw bits of data, or raw signal, and you want to extract from that some core meaning. Many fields have looked at the question of how to go from raw signal to information, but so far none have entirely automated the process. Humans are still critical in extracting meaning from data. Whether it's patient statistics collected by the Center for Disease Control in an attempt to identify epidemics early, or weather patterns tracked by the National Weather Service to warn people about impending storms, or genetic information gathered by researchers trying to understand patterns associated with heredity and disease, the quantities of information are enormous and the need for people to be a central part of the information extraction process is a critical bottleneck for advancement.

---

There is...a fundamental need of rethinking the meaning and scope of computation, information gathering, and extraction.

---

PERONA: The more we are able to dig into data and make sense of it, that is, transform data into information, the more powerful we become. The more efficient these processes are, the better we can make all kinds of important decisions—medical, economic, technological, and so on. Humans are built in a way that they spontaneously try to organize information and make sense of it. But machines are not built this way. There is an amazing amount of clutter out there in the world. We need to find out how to automate this process of easily understanding which features are the important ones—and which to ignore.

CANDES: Humans use representations all the time. Look at the history of simply expressing numbers. The Romans came up with a numeration system, but they had to give it up because it was not really efficient for calculating. If you try to add two numbers in the Roman system, it's a complete mess. That's why the Arabic numeration system was adopted, because it's handier to perform more complicated tasks. Now we have digital computers that use a binary system—only 0s and 1s—which makes addition, subtraction, multiplication, and division easy. This concept of representation is really critical to scientific thinking. For a given problem, you really want to find the correct representation—the one that makes a set of specific tasks completely trivial.

PERONA: Representations are not self-contained, they are finalized toward certain tasks. On one side we have the data, on another side we have prior knowledge about the world, and on the third side of the triangle is the task. All three determine which representation should be used for a given problem. This is one of the big themes for the Center. For instance, my colleagues here at Caltech are studying the brain's different representations of the physical space around a person. Photons create an image that is captured by the retina, and then objects in the image are assigned retinal coordinates. Next the objects are expressed in head coordinates, and then in body coordinates. All of these different representations are useful. If I move my eyes, I want to know where the object is in respect to my head or my body, because my eyes have to move with respect to the head but I want my representation to be invariant with respect to that motion. If I move my hand to rub an object, the object has to be represented in world coordinates so that I can find it both with my hands and my eyes. The brain makes at least two different versions of geometric representations of the world. We don't know for sure that these representations are cartesian either. The problem is made more complex in that there may be several representations of the same data that need to be coordinated—this is another big theme for the Center.

Attention and awareness is another related problem—organisms pay attention to only fragments of the sensations transmitted to the brain, because it is the most efficient way to operate. When confronted with practically infinite data, how do we know what to pay attention to? How do we shift our awareness? Several researchers in the Computational and Neural Systems option are dealing with the engineering issues behind awareness and will play a big role in the CMI.

---

There are people all over campus who are thinking deeply about the mathematics of information. The goal in many senses is to bring them all together.

---

EFFROS: Many people on campus are focused on representation choice. Some are concerned with vision, some with attention and awareness questions, and we have computer science people thinking about representation choice for the purpose of being able to do certain kinds of computations. The CMI will bring all these electrical engineers, computer scientists, and applied mathematicians together to tackle the foundations, the fundamentals of representation choice independent of the realm of application.

CANDES: I'd like to emphasize the timeliness of the Center. It's clear that scientists and engineers are engaged in acquiring massive data sets—in many areas of biology, bioengineering, and finance, many people are involved in massive data collection. It's clear that any kind of progress we make in the area of data representation will have a huge impact across many sciences. And though we're not the first ones to think about data representation, we do feel that existing representations are somehow limited. There's a whole world out there of new representations that we would like to explore systematically. Any major advances that we make will be useful to other key players in the other ISTI centers.

EFFROS: What is the smallest amount of computation I can use to perform a particular task? My own field of communications or information theory focuses primarily on the quantity of information, whether you measure that as bandwidth or just as the number of bits that you need to represent some particular piece of information. Controls researchers focus on feedback. To think about how these different resources interact or trade off is fascinating to me. If I'm working on a control system, say a distributed control system where I have a bunch of different devices all trying to work together to perform a particular task, I care about many things. I care about how many computations each one of them needs to do separately. I care about how much communication between them is necessary to make the system work. I care about how best to use feedback. I care about representation choice. And I care about all of these things simultaneously. We are now at a point where it is, I believe, critical to figure out how to put all of these pieces together. So in information theory, the traditional view has been to look at how many bits it takes to communicate or store information, but the computation resource has been considered to be unlimited. You can have as much computation and delay as you want, but feedback is going to be a problem. These other resources were allowed to be unlimited so we could see where the critical points were in the one resource on which we focused. If you look at these other fields, they've done the same kinds of things. However, researchers in each of these fields are now realizing that we really need to take all of the resources into account.

Taking advantage of Caltech's small size and cross-disciplinary nature, we think that we can make real progress in putting these things together. In trying to understand, for example: is there a dynamics of information? What would the dynamics of information look like? Is there a conservation of information? What are the properties of this new resource of information? Do they parallel the properties that we have in the physical sciences?

We have been building on Shannon's work for 50 years. But Shannon made assumptions. He did not constrain the amount of computation and he did not constrain the amount of delay. He just said, “Let's look at how many bits it takes,” either to communicate through a noisy channel, or to store information. He captured one resource with incredible clarity and beauty by abstracting away many of the other resources that are critical.

ENGENIOUS: Could this Center reinvent the fundamentals of information theory, in a sense?

CANDES: If you allow me, I would like to formulate a more modest mission.

Every single field of scientific research is called upon to develop novel tools to process the information contained in massive datasets. While many aspects of these advances are going to be field-specific, it is clear that these challenges cannot be answered only in a peripheral manner. There is, in fact, a fundamental need of rethinking the meaning and scope of computation, information gathering, and extraction. From many endpoints of scientific research comes the solicitation to redefine our approach to information processing. Such fundamental paradigm change can, however, happen only if we invest a considerable amount of resources in theoretical thinking centered around information. In short, our Center will create an environment, a home if you will, where these things can happen.

First, the Center will create the opportunity to deploy mathematical ideas, theories, and algorithms in information technology; to import new challenges into mathematics; and to create new mathematical theories and new mathematical tools via these interactions. Second, the Center will strengthen existing interactions and create new bridges between mathematical science and key areas in information technology. And third, the Center will help train a new generation of scientists in this emerging interdisciplinary area.

EFFROS: It's not that there's something wrong with the pieces that are there. But it's as if we have a few pieces of the puzzle that only give us focused pictures in certain realms. We're missing the big picture that puts it all together into a unified whole.

PERONA: You could take a more top-down view and notice how, in the past century, technology delivered systems that were extremely effective at doing one thing. Think telephones, personal computers, automobiles, airplanes. All of these things are well designed and deliver the goods. They have changed our lives. Nowadays, things are being integrated and connected so you have telephone sets that become PDAs and computers; and automobiles that include telecommunications. And this is just the beginning of ubiquitous networking. These systems are increasingly complex. However, they're completely stocked with software that was designed 30 years ago. Unfortunately, we don't know how to design these integrated systems; we cannot guarantee that they will be robust to viruses and software glitches or that they will be stable and will perform according to plan.

A big theme in this Center is coming up with key mathematical ideas that will allow us to think about large, complex, distributed systems that include computation, include control, include communications, and still be able to deal gracefully with the inevitable software bugs, hardware problems of all sorts, and human errors. They have to keep working. Humanity depends on these systems. We are far past the point of simply needing the water well and the chicken and a tree hanging with fruit to live. If the internet goes down for a week, I think the world will stop. So the design of complex, robust systems will be another important research area for the CMI. To do this, scientists from different disciplines will have to come together, transcend their respective disciplines, and broaden the scope of their research.

---

....this is the place where we destroy all the boundaries between disciplines and even the concept that the disciplines need to exist...

---

CANDES: Absolutely, and at the same time we want to rethink computation, particularly large-scale computation. A trivial answer to the large-scale problems is: give me more flops. Here is an area where mathematics could play a role by providing a more efficient data structure through more efficient representations of operators for calculation.

There's another very interesting avenue that we will explore—while the world we live in is continuous, and we have the laws of physics formulated in a continuous way, computers are only able to handle equations and sets of data that are discrete and digitized. So if you're looking at numerical schemes, or if you digitize an equation, you have violated a lot of physical conservation laws that nature prefers to be preserved. How can you think really discrete all the way through without violating physical laws in your end results? That's a topic people will gravitate around, and that scientists at Caltech have already started attacking. Squarely addressing this challenge will be critical for moving beyond this limited, digitized computational view, to one that takes into account that the real world is continuous, multi-scale, dynamic, and complex.

PERONA: We hope the Center will bring the pure mathematicians at Caltech in contact with the technologists. We will be working very closely with the theorists in the physics center [CPI] as well.

EFFROS: Making that connection between pure mathematics and applied mathematics is critical. You would be amazed how broadly our theme sweeps. There are people in economics, humanities, and social sciences who are worrying about the mathematics of information. There are people all over campus who are thinking deeply about the mathematics of information. The goal in many senses is to bring them all together.

CANDES: I'd also like to emphasize that the CMI will provide a real link to and between the other ISTI centers. ISTI will bring the divisions of Caltech together in profound ways, and this particular Center will be the glue for ISTI.

PERONA: At the beginning, creating this Center felt like a construction. But now it feels like an inevitable fact. It seems impossible not to have thought about it a little bit earlier and it seems impossible that it will not exist. I see signs, all over the country, that the best, young creative people in every area that deals with information are just bursting out of the seams of existing fields. And this Center is going to capture them. We hope to attract the best talent in the country, both at the level of graduate students and at the level of young faculty. They will want to come to Caltech because this is the place where we destroy all the boundaries between disciplines and even the concept that the disciplines need to exist—we're focusing on the real problems of today. ENG