Information and Decision Systems

PhD Program/Graduate Minor in Information and Decision Systems (IDS)

Shuki Bruck    Mani Chandy    John Doyle    Michelle Effros    Babak Hassibi    Tracey Ho    Andreas Krause    Steven Low    Richard Murray    Joel Tropp    Adam Wierman    Erik Winfree

Contents Motivation Program structure Overall architecture PhD program Graduate minor Postdocs Courses Partner programs Frequently asked questions

Executive Summary

We propose to establish a new graduate program at Caltech in Information and Decision Systems (IDS). The program will consist of both a PhD program intended to attract exceptional students from around the world and graduate minor for students in existing options wishing to concentrate in this area. The intent of both programs is to provide students with a strong education in the mathematical techniques and insights required for the study of large-scale, complex, networked, information and decision systems in a variety of areas of science and engineering. The program is structured to leverage Caltech's strengths in science, mathematics and engineering, and the interests of faculty around the campus to develop fundamental tools for helping unravel the complexity of biological, chemical, economic, information, physical and social systems. The program will be administered by a small, core group of faculty, but students are expected to work with faculty from around the campus to help promote interdisciplinary studies.

Motivation: The Future of Complex Systems Research

Many cutting edge problems in the natural sciences involve understanding aggregate behavior in complex large-scale systems. This behavior "emerges" from the interaction of a large number of simpler systems, with intricate patterns of information flow. Representative examples can be found in fields ranging from embryology to seismology to global climate change. Key features of these new challenges include the (sometimes bewildering) complexity of the underlying phenomena of interest, the increasing ability to collect large amounts of data from sophisticated instruments, and the desire to develop principles that aid in our understanding and allow us to predict future behavior and/or design systems that behave reliably in the presence of large amounts of uncertainty.

While sophisticated theories have been developed by domain experts for the analysis of various complex systems, the development of rigorous methodology that can discover and exploit common features and essential mathematical structure remains a major challenge to the research community; we need new approaches and techniques.

To address this opportunity, we believe that a new PhD program in Information and Decision Systems is timely and would keep Caltech in a leadership position in fundamental research on complex, networked information and decision systems across several areas of applied science and mathematics in which Caltech is already active, as well as enable potentially new thrusts within the sciences. The long term goals of this PhD program are to:

• develop new approaches for understanding and building complex information and decision systems, with an emphasis on the underlying theory and application across a broad variety of the sciences and engineering.

• recruit students, postdocs and faculty to Caltech who will serve as leaders in their respective fields around the world, and who will help develop the theoretical frameworks required to tackle new problems in complex, networked systems.

• develop a curriculum and educational culture that supports the education of broadly-trained scientists, applied mathematicians and engineers who work in and across multiple disciplines over the course of their careers.

A key theme of the program is to help facilitate interaction between a broad variety of application areas in which in a common set of mathematical problems arise. This will be accomplished in part by keeping the program very open and encouraging students to work with faculty from around the campus. Some examples of application areas where we believe IDS students could contribute:

• Next generation infrastructure networks (smart grid, air traffic control)
• Next generation sensor networks (Trinet)

Structure of the Program

The overall structure of the program reflects the interdisciplinary nature of the research that will drive it forward, as well as the multiple channels for students, postdocs and faculty that will make up the program. On the one hand, the program is intended to bring together a network of people that will interact with each other to work on problems of fundamental scientific and mathematical importance. On the other hand, the program reflects an interaction between a variety of different application areas and underlying disciplines and must be structured to facilitate communications across this diverse intellectual backdrop.

Program architecture

In the study of complex systems, a key element is the development of architectures that allow us to understand common principles between different phenomena and also rapidly exploit these principles to facilitate the exchange of ideas and advances in underlying mathematical techniques. The figure to the right shows the basic architecture of the program.

Going from top to bottom is the intellectual "hourglass" that reflects the role of the program in linking mathematical techniques to scientific applications. The intent is not to argue that the \phdabbv program is at the center of the world, but rather to describe the drivers of the program as coming from new mathematical theories and techniques combined with insights and challenges coming from a diverse set of scientific challenges and opportunities. The success of the program will depend on the ability to identify a coherent set of intellectual themes that can help facilitate these interactions and that add value to research in both the mathematical core and the application sciences.

The left to right flow across the diagram represents the flow of people into and out of the program. As we envision it, the program will be rooted in a standard 4-5 year PhD program that brings in students from a variety of external universities and prepares them for intellectual leadership position in academic and industry. In addition, we propose to establish a graduate minor that allows students from other Caltech options to learn the theory and tools that may be relevant for their research interests. Finally, we hope to build off of the successful CMI postdoc program and include postdocs who received their PhDs from other universities who come to Caltech for two years of independent research, working with faculty from around the campus.

PhD program

The PhD program will serve as the core of the educational program and provide a common collection of fundamental tools that can be used as a starting point for research. The following courses will be required of all students enrolled in the PhD program:

• Core courses: IDS 110 (linear algebra and optimization), IDS 120 (stochastic systems), IDS 130 (information systems), IDS 140 (data-driven modeling), IDS 150 (decision making systems)
• Exploratory courses: IDS 210 (Frontiers), IDS 220 (Topics), IDS 230 (Reading)
• Focus requirement: three quarters of graduate course work in any area of science, engineering or mathematics

The core course work will be done in the first year, with a few more specialized courses in the second year. Courses in the first and second term would consist of fundamental course work that would be taken by all PhD students and would provide the common mathematical background required for research in IDS. The third term would be used for teaching more advanced topics that would change from year to year. In addition, the third term would contain two new courses, the ``Frontiers and ``Topics courses.

The "Frontiers" course is modeled on CDS 273, "Frontiers in Control and Dynamical Systems", a course developed by Hideo Mabuchi and Richard Murray in 2000-2006. This course will be organized around small teams consisting of IDS and non-IDS students who work on projects of mutual interest in some faculty member's research area. The main goals are for the participating IDS and science/engineering faculty to become more familiar with each other's work and expertise, and to get our graduate students from different groups interacting with each another. The initial output of the course is a paper that could be submitted to a conference (either in control or the application domain). In addition, we hope to explore new research directions that can lead to collaborations and projects between IDS faculty members and other groups around the campus.

The ``Topics course is roughly modeled on CS 286, a course that was developed as part of the CMI postdoctoral program. In CS 286 CMI postdocs each give a two week mini-course on their research area. In the first week, an introduction to the topic is given, followed by a description of the postdocs research in the second week. In the IDS "Topics" course that we imagine here, second year graduate students would co-teach a course on topics of recent interest. The second-year students, under the guidance of a faculty member, would be responsible for developing the course material, including homework sets, as well as grading the homework. This activity would occur in the second year of graduate studies.

Graduate minor

The IDS minor would allow students in other disciplines who wished to learn more about complex information and decision systems to take courses and obtain recognition on their degrees of extra studies. The minor requirements would be the same as the PhD course requirements (excluding the focus requirements). We anticipate that students CDS, CNS, CS and EE would be able to obtain a minor by taking 4-6 additional quarters of courses (many of the courses that are part of the core are already required for their current PhD programs).

Postdoctoral program

The CMI postdoctoral program would also have natural linkages with this PhD program and we anticipate significant interaction between the two. (CMI postdocs are selected based on applications that are evaluated by the CMI steering committee on behalf of the broader CMI community. In addition to exceptional scholarly achievements, \phdabbv postdocs are selected based on their ability to perform independent research that will link existing faculty interests. CMI postdocs are not be linked to a single faculty member, but rather are housed near each other (and hopefully near the first and second year graduate students in this new program) to facility interaction. CMI postdocs also participate in teaching special topics courses in new subject areas (generally related to their own research), allowing rapid exploration of cutting edge research areas to the participates in the IDS program.

Core Courses

The courses that will be offered as part of the program are shown in the table below. We have structured the curriculum so that it can make use of existing courses as much as possible (only IDS 150 is a new course, which will largely replace the current CDS 212/213 sequence of courses).

Track	Fall	Winter	Spring
Optimization and linear algebra IDS 110ab	Linear Algebra & Applied Operator Theory ACM 104/CDS 201 (Beck, Murray, Owhadi) Vector spaces, including Banach and Hilbert spaces Linear operators, dual spaces, decompositions	Introduction to Optimization ACM 113 (Doyle, Owhadi, Tropp) Convex analysis Linear programming/duality	Decision making IDS 150 (Doyle, Low, Murray) Dynamics and stability Nonlinear discrete time systems, hybrid systems Stability and stability certificates (Lyapunov, SOS) Feedback systems, small gain theorems Uncertainty and robustness Representation of uncertainty Operator bounds; links to small gain Robust performance: discrete time, NL? Need to say all of this in a non-control specific way Fundamental limits: Bode, Shannon, Bode/Shannon Case studies Internet: layering as optimization One more (not the cell)
Stochastic systems IDS 120ab	Introduction to Stochastic Processes and Modeling ACM/EE 116 (Hassibi, Owhadi, Tropp)	Markov Chains, Discrete Stochastic Processes and Applications ACM 216 (Owhadi, Tropp)
Information systems IDS 130ab	Information and complexity CS/EE/Ma 129a (Abu-Mostafa, Winfree) Information theory and coding Finite state automata, Turing machines, computability Data compression Note: EE 126 is an alternative to this course for people who have already seen automata, computability, etc	Information and complexity CS/EE/Ma 129b (Abu-Mostafa, Winfree) Channel coding, capacity and rate theorem Time complexity of algorithms; P vs NP Formal logic and provability
Data-driven modeling IDS 140ab	Learning systems CS/CNS/EE 156 (Abu-Mostafa, Krause)	Graphical models CS 155 (Krause)

External partner programs

In order to broaden the impact of the DS program, we anticipate the establishment of research collaborations with a number of active centers of research with overlapping interests. In this section we list some of the current interactions that we believe will be important to establishing a global network of researches who interact with the program.

Lund Center for Control of Complex Engineering Systems (LCCC) LCCC is a Linnaeus Center at Lund University funded by the Swedish Research Council. The ten principal investigators are from the Department of Automatic Control and the Department of Electrical and Information Technology. The research vision of LCCC is to make fundamental contributions to a general theory and methodology for design and operation of complex systems. This will include language support and tools for modeling, scalable methods for analysis and control synthesis, as well as reliable implementations using networked embedded systems. Our goal is to maintain a leading role in a world-wide effort involving partners of many kinds.

MIT Laboratory of Information and Decision Systems (LIDS) LIDS is an interdepartmental research laboratory at the Massachusetts Institute of Technology. It began in 1939 as the Servomechanisms Laboratory, an offshoot of the Department of Electrical Engineering. Its early work, during World War II, focused on gunfire and guided missile control, radar, and flight trainer technology. Over the years, the scope of its research broadened. Today, the Laboratory's fundamental research goal is to advance the field of systems, communications and control. In doing this, it recognizes the interdependence of these fields and the fundamental role that computation plays in this research. The Laboratory conducts basic theoretical studies in communication and control and is committed to advancing the state of knowledge of technologically important areas such as atmospheric optical communications and multivariable robust control.

Stanford Information Systems Laboratory (ISL) The ISL is an interdisciplinary research group in the Department of Electrical Engineering at Stanford University. Formed in the early 1960s to study the mathematical aspects of EE systems, ISL has grown in size and international reputation. It now includes 21 faculty members, 15 researchers, 4 administrative staff members, and approximately 110 PhD students involved in a diverse set of research projects, many of which are joint with other labs in EE and with other departments and schools, including Computer Science, Statistics, Management Science and Engineering, Aeronautics \& Astronautics, the Institute for Computational and Mathematical Engineering (ICME) Applied Mathematics, Biological Sciences, Psychology, the School of Medicine, and the Graduate School of Business. Research at ISL focuses on the development and application of mathematical models, techniques and algorithms for information processing, communication, and storage, broadly construed.

Frequently Asked Questions

• Isn't IDS a subset of the ABC option?

Several options have indicated that IDS seems to be a subset of their current (or planned) offerings, including ACM, CDS, CNS, CS and EE. The intent of the program is to identify and attract students who would not normally apply to existing Caltech options, thus enhancing the pool of graduate students who might work with Caltech faculty (including faculty in existing options and programs).

• Don't we already have too many options at Caltech?

The intent of this proposal is not to create a new option that is separate from existing options, but rather to create a program that brings together students who might work with faculty in a number of existing options around Caltech. We anticipate that the core faculty who are part of this program would continue to participate in their existing departments while at the same time establishing a culture and identify for the program that enables the students in the option to develop a unique style of research that will be highly visible to the outside world.

• Won't this program increase our teaching load?

Most of the topics listed in the courses are already part of currently existing courses at Caltech. We anticipate that most \phdabbv courses would simply be cross-listed with existing courses. We might need to create a new information systems course (IDS 150), but this would replace 2-3 existing quarters of courses (CDS 110b, CDS 212, CDS 213). In addition, IDS courses could eventually offset teaching in other courses that might an IDS courses as a prerequisite.